第六講狀態(tài)空間搜索策略

第六章 問題求解與搜索戰(zhàn)略6.1根本概念6.2形狀空間的搜索戰(zhàn)略6.3與/或樹的搜索戰(zhàn)略6.4搜索的完備性與效率問題求解問題求解是人工智能的中心問題之一問題求解的目的機(jī)器自動(dòng)找出某問題的正確處理戰(zhàn)略更進(jìn)一步，可以舉一反三，具有處理同類問題的才干是從人工智能初期的智力難題、棋類游戲等問題的研討中開場(chǎng)構(gòu)成和開展起來的一大類技術(shù)，搜索技術(shù)是問題求解的主要手段之一問題表示解的搜索例如——八數(shù)碼難題在3×3的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。12384567初始形狀81324567目的形狀如何將棋盤從某一初始形狀變成最后的目的形狀？問題例如4怎樣找到兩點(diǎn)之間的最短途徑呢？6.1.2形狀空間表示法〔1〕很多問題的求解過程都可以看作是一個(gè)搜索過程。問題及其求解過程可以用形狀空間表示法來表示。〔2〕形狀空間用“形狀〞和“算符〞來表示問題。形狀 形狀用以描畫問題在求解過程中不同時(shí)辰的形狀，普通用一個(gè)向量表示：SK=(Sk0,Sk1,…)算符 使問題從一個(gè)形狀轉(zhuǎn)變?yōu)榱硪粋€(gè)形狀的操作稱為算符。在產(chǎn)生式系統(tǒng)中，一條產(chǎn)生式規(guī)那么就是一個(gè)算符。形狀空間由一切能夠出現(xiàn)的形狀及一切可用算符所構(gòu)成的集合稱為問題的形狀空間?！?〕采用形狀空間求解問題，可以用下面的一個(gè)三元組表示：(S,F,G)其中S是問題初始形狀的集合；F是算符的集合；G是目的形狀的集合。傳教士野人問題〔Missionaries&Cannibals，MC問題〕有三個(gè)傳教士M和三個(gè)野人C過河，只需一條能裝下兩個(gè)人的船，在河的一方或者船上，假設(shè)野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會(huì)有危險(xiǎn)，他能不能提出一種平安的渡河方法呢？形狀：?jiǎn)栴}在某一時(shí)辰所處的“位置〞，“情況〞等根據(jù)問題所關(guān)懷的要素，普通用向量方式表示，每一位表示一個(gè)要素0：右岸1：左岸初始形狀：(0,0,0)目的形狀：(3,3,1)形狀可有多種表示方法：(左岸傳教士數(shù),右岸傳教士數(shù),左岸野人數(shù),右岸野人數(shù),船的位置)或(左岸傳教士數(shù),左岸野人數(shù),船的位置)算子〔算符，操作符〕——使形狀發(fā)生改動(dòng)的操作MC問題中的算子將傳教士或野人運(yùn)到河對(duì)岸Move-1m1c-lr：將一個(gè)傳教士(m)一個(gè)野人(c)從左岸(l)運(yùn)到右岸(r)一切能夠操作Move-1m1c-lrMove-1m1c-rlMove-2c-lrMove-2c-rl Move-2m-lr Move-2m-rlMove-1c-lr Move-1c-rl Move-1m-lrMove-1m-rl

傳教士野人問題形狀空間圖MC6.2形狀空間的搜索戰(zhàn)略求解過程轉(zhuǎn)化為在形狀空間圖中搜索一條從初始節(jié)點(diǎn)到目的節(jié)點(diǎn)的途徑問題必需記住哪些點(diǎn)走過了必需記住下一步還可以走哪些點(diǎn)必需記住從目的前往的途徑OPEN表(記錄還沒有擴(kuò)展的點(diǎn))CLOSED表(記錄曾經(jīng)擴(kuò)展的點(diǎn))每個(gè)形狀的節(jié)點(diǎn)構(gòu)造中必需有指向父節(jié)點(diǎn)的指針6.2.1形狀空間的普通搜索過程OPEN表和CLOSE表OPEN表用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索戰(zhàn)略，節(jié)點(diǎn)在OPEN表中的陳列順序是不同的。CLOSE表用于存放將要擴(kuò)展的節(jié)點(diǎn)。對(duì)一個(gè)節(jié)點(diǎn)的擴(kuò)展是指：用一切可適用的算符對(duì)該節(jié)點(diǎn)進(jìn)展操作，生成一組子節(jié)點(diǎn) OPEN表 CLOSE表狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)搜索的普經(jīng)過程把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表能否為空，假設(shè)為空那么問題無解，退出；把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表，并計(jì)該節(jié)點(diǎn)為n；調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出；擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)參與G中；對(duì)于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)〔即節(jié)點(diǎn)n〕的指針，并把它們放入OPEN表；〔不在OPEN表〕按某種搜索戰(zhàn)略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)展排序；轉(zhuǎn)第2步。一些闡明一個(gè)節(jié)點(diǎn)經(jīng)一個(gè)算符操作后普通只生成一個(gè)子節(jié)點(diǎn)。但適用于一個(gè)節(jié)點(diǎn)的算符能夠有多個(gè)，此時(shí)就會(huì)生成一組子節(jié)點(diǎn)。這些子節(jié)點(diǎn)中能夠有些是當(dāng)前擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等，此時(shí)不能把這些先輩節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)。一個(gè)新生成的節(jié)點(diǎn)，它能夠是第一次被生成的節(jié)點(diǎn)，也能夠是先前已作為其它節(jié)點(diǎn)的子節(jié)點(diǎn)被生成過，當(dāng)前又作為另一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)被再次生成。此時(shí)，它終究應(yīng)選擇哪個(gè)節(jié)點(diǎn)作為父節(jié)點(diǎn)？普通由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的代價(jià)來決議，處于代價(jià)小的路途上的那個(gè)節(jié)點(diǎn)就作為該節(jié)點(diǎn)的父節(jié)點(diǎn)。在搜索過程中，一旦某個(gè)被調(diào)查的節(jié)點(diǎn)是目的節(jié)點(diǎn)就得到了一個(gè)解。該解是由從初始節(jié)點(diǎn)到該目的節(jié)點(diǎn)途徑上的算符構(gòu)成。假設(shè)在搜索中不斷找不到目的節(jié)點(diǎn)，而且OPEN表中不再有可供擴(kuò)展的節(jié)點(diǎn)，那么搜索失敗。經(jīng)過搜索得到的圖稱為搜索圖，搜索圖是形狀空間圖的一個(gè)子集。由搜索圖中的一切節(jié)點(diǎn)及反向指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹。根據(jù)搜索樹可給出問題的解。盲目搜索不同的搜索戰(zhàn)略其搜索的效率是不同的盲目搜索又稱無信息搜索寬度優(yōu)先搜索深度優(yōu)先搜索特點(diǎn)搜索過程中不運(yùn)用與問題有關(guān)的閱歷信息采用固定戰(zhàn)略對(duì)OPEN表排序搜索效率低不適宜大空間的實(shí)踐問題求解6.2.2廣度優(yōu)先搜索根本思想： 從初始節(jié)點(diǎn)S0開場(chǎng)，逐層地對(duì)節(jié)點(diǎn)進(jìn)展擴(kuò)展并調(diào)查它能否為目的節(jié)點(diǎn)。在第n層的節(jié)點(diǎn)沒有全部擴(kuò)展并調(diào)查之前，不對(duì)第n＋1層的節(jié)點(diǎn)進(jìn)展擴(kuò)展。OPEN表中節(jié)點(diǎn)總是按進(jìn)入的先后順序陳列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。廣度優(yōu)先搜索過程把初始節(jié)點(diǎn)S0放入OPEN表。假設(shè)OPEN表為空，那么問題無解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)〔記為節(jié)點(diǎn)n〕取出放入CLOSE表。調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出。假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。重排九宮的廣度優(yōu)先搜索

操作符：空格左移、上移、右移、下移在上述廣度優(yōu)先算法中需求留意兩個(gè)問題：1、對(duì)于恣意一個(gè)可擴(kuò)展的節(jié)點(diǎn)，總是按照固定的操作符的順序?qū)ζ溥M(jìn)展擴(kuò)展〔空格左移、上移、右移、下移〕。2、在對(duì)任一節(jié)點(diǎn)進(jìn)展擴(kuò)展的時(shí)候，假設(shè)所得的某個(gè)子節(jié)點(diǎn)〔形狀〕前面曾經(jīng)出現(xiàn)過，那么立刻將其放棄，不再反復(fù)畫出〔不送入OPEN表〕。因此，廣度優(yōu)先搜索的本質(zhì)是，以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在形狀空間圖中按照廣度優(yōu)先的原那么，生成一棵搜索樹。廣度優(yōu)先搜索的特點(diǎn)優(yōu)點(diǎn)： 只需問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是途徑最短的解。缺陷： 廣度優(yōu)先搜索盲目性較大，當(dāng)目的節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無用節(jié)點(diǎn)，搜索效率低。6.2.3深度優(yōu)先搜索深度優(yōu)先搜索與廣度優(yōu)先搜索的獨(dú)一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到OPEN表的首部。深度優(yōu)先搜索過程把初始節(jié)點(diǎn)S0放入OPEN表。假設(shè)OPEN表為空，那么問題無解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)〔記為節(jié)點(diǎn)n〕取出放入CLOSE表。調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出。假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。重排九宮的深度優(yōu)先搜索深度優(yōu)先搜索的特點(diǎn)在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支不斷向下搜索。假設(shè)目的節(jié)點(diǎn)恰好在此分支上，那么可較快地得到解。但是，假設(shè)目的節(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無窮分支，那么就不能夠得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。本質(zhì)：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在形狀空間圖中按照深度優(yōu)先的原那么，生成一棵搜索樹。6.2.4有界深度優(yōu)先搜索根本思想：對(duì)深度優(yōu)先搜索引入搜索深度的界限〔設(shè)為dm〕，當(dāng)搜索深度到達(dá)了深度界限，而仍未出現(xiàn)目的節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)展搜索。搜索過程：把初始節(jié)點(diǎn)S0放入OPEN表中，置S0的深度d(S0)=0。假設(shè)OPEN表為空，那么問題無解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)〔記為節(jié)點(diǎn)n〕取出放入CLOSE表。調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出。假設(shè)節(jié)點(diǎn)n的深度d(n)=dm，那么轉(zhuǎn)第2步〔此時(shí)節(jié)點(diǎn)n位于CLOSE表，但并未進(jìn)展擴(kuò)展〕。假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，將每一個(gè)子節(jié)點(diǎn)的深度設(shè)置為d(n)+1，然后轉(zhuǎn)第2步。假設(shè)問題有解，且其途徑長(zhǎng)度≤dm，那么上述搜索過程一定能求得解。但是，假設(shè)解的途徑長(zhǎng)度>dm,那么上述搜索過程就得不到解。這闡明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。有界深度優(yōu)先搜索的一些改良方法先恣意設(shè)定一個(gè)較小的數(shù)作為dm，然后進(jìn)展上述的有界深度優(yōu)先搜索，當(dāng)搜索到達(dá)了指定的深度界限dm仍未發(fā)現(xiàn)目的節(jié)點(diǎn)，并且CLOSE表中仍有待擴(kuò)展節(jié)點(diǎn)時(shí)，就將這些節(jié)點(diǎn)送回OPEN表，同時(shí)增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只需問題有解，就一定可以找到它。但此時(shí)找到的解不一定是最優(yōu)解。為了找到最優(yōu)解，可增設(shè)一個(gè)表R，每找到目的節(jié)點(diǎn)Sg后，就把它放入到R的前面，并令dm等于該目的節(jié)點(diǎn)所對(duì)應(yīng)的途徑長(zhǎng)度，然后繼續(xù)搜索。由于后求得的解的途徑長(zhǎng)度不會(huì)超越先求得的解的途徑長(zhǎng)度，所以后求得的解一定是最優(yōu)解。重排九宮的有界深度優(yōu)先搜索設(shè)深度界限dm＝46.2.5代價(jià)樹的廣度優(yōu)先搜索邊上標(biāo)有代價(jià)(或費(fèi)用)的樹稱為代價(jià)樹。用g(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià)，用c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià)，那么有：g(x2)=g(x1)+c(x1,x2)根本思想： 每次從OPEN表中選擇節(jié)點(diǎn)往CLOSE表傳送時(shí)，總是選擇其中代價(jià)最小的節(jié)點(diǎn)。也就是說，OPEN表中的節(jié)點(diǎn)在任一時(shí)辰都是按其代價(jià)從小到大排序的。代價(jià)小的節(jié)點(diǎn)排在前面，代價(jià)大的節(jié)點(diǎn)排在后面。假設(shè)問題有解，代價(jià)樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。該算法運(yùn)用的條件:該算法是針對(duì)代價(jià)樹的算法。為了采用該算法對(duì)圖進(jìn)展搜索，必需先將圖轉(zhuǎn)換為代價(jià)樹。轉(zhuǎn)換方法見例6.7。代價(jià)樹廣度優(yōu)先搜索過程把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。假設(shè)OPEN表為空，那么問題無解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)〔記為節(jié)點(diǎn)n〕取出放入CLOSE表。調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出。假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，計(jì)算各子節(jié)點(diǎn)的代價(jià)，并將各子節(jié)點(diǎn)放入OPEN表中。按各節(jié)點(diǎn)的代價(jià)對(duì)OPEN表中的全部節(jié)點(diǎn)進(jìn)展排序(按從小到大的順序)，然后轉(zhuǎn)第2步。代價(jià)樹例如(例6.7)6.2.6代價(jià)樹的深度優(yōu)先搜索搜索過程：把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。假設(shè)OPEN表為空，那么問題無解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)〔記為節(jié)點(diǎn)n〕取出放入CLOSE表。調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出。假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)按代價(jià)從小到大的順序放到OPEN表中的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。代價(jià)樹的深度有限搜索是不完備的?？偨Y(jié)1、上述各種搜索方法的本質(zhì)是，以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，按照既定的戰(zhàn)略對(duì)形狀空間圖進(jìn)展遍歷，并希望可以盡早發(fā)現(xiàn)目的節(jié)點(diǎn)。2、由于對(duì)形狀空間圖遍歷的戰(zhàn)略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。有信息搜索搜索過程中利用與問題有關(guān)的閱歷信息〔啟發(fā)式信息〕引入估價(jià)函數(shù)來估計(jì)節(jié)點(diǎn)位于解途徑上的“希望〞，函數(shù)值越小“希望〞越大搜索過程中按照估價(jià)函數(shù)的大小對(duì)OPEN表排序每次選擇估價(jià)函數(shù)值最小的節(jié)點(diǎn)作為下一步調(diào)查的節(jié)點(diǎn)6.2.7啟發(fā)式搜索A算法在圖搜索算法中，假設(shè)能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)Open表中的節(jié)點(diǎn)進(jìn)展排序，那么該搜索算法為A算法。由于估價(jià)函數(shù)中帶有問題本身的啟發(fā)性信息，因此，A算法又稱為啟發(fā)式搜索算法。對(duì)啟發(fā)式搜索算法，又可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將其分為全局擇優(yōu)搜索算法和部分擇優(yōu)搜索算法。A算法估價(jià)函數(shù) f(x)=g(x)+h(x)從起始形狀到當(dāng)前形狀x的代價(jià)從當(dāng)前形狀x到目的形狀的估計(jì)代價(jià)〔啟發(fā)函數(shù)〕g(x)有利于搜索的完備性，但影響搜索的效率。h(x)有利于提高搜索的效率，但影響搜索的完備性。設(shè)有如下構(gòu)造的挪動(dòng)將牌游戲：該游戲規(guī)那么：當(dāng)一個(gè)牌移入相鄰的空位置時(shí)，費(fèi)用為一個(gè)單位。一個(gè)牌至多可跳過兩個(gè)牌進(jìn)入空位置，其費(fèi)用等于跳過的牌數(shù)加1。要求：把一切的B都移至W的右邊，請(qǐng)?jiān)O(shè)計(jì)啟發(fā)函數(shù)h(x)。解：根據(jù)要求可知，W左邊的B越少越接近目的，因此可用W左邊B的個(gè)數(shù)作為h(x),即h(x)=3×(每個(gè)W左邊B的個(gè)數(shù)的總和)這里乘以系數(shù)3是為了擴(kuò)展h(x)在f(x)中的比重。啟發(fā)函數(shù)例如BBBWWWE部分擇優(yōu)搜索根本思想： 當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展以后，按f(x)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要調(diào)查的節(jié)點(diǎn)。搜索過程：把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)。假設(shè)OPEN表為空，那么問題無解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)〔記為節(jié)點(diǎn)n〕取出放入CLOSE表。調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出。假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并按估價(jià)值從小到大的順序放到OPEN表中的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。深度優(yōu)先搜索、代價(jià)樹的深度優(yōu)先搜索均為部分擇優(yōu)搜索的特例。全局擇優(yōu)搜索根本思想： 每當(dāng)要選擇下一個(gè)節(jié)點(diǎn)進(jìn)展調(diào)查時(shí)，全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。搜索過程：把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)。假設(shè)OPEN表為空，那么問題無解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)〔記為節(jié)點(diǎn)n〕取出放入CLOSE表。調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)。假設(shè)是，那么求得了問題的解，退出。假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。把這些子節(jié)點(diǎn)都送入OPEN表中，然后對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)值從小至大的順序進(jìn)展排序，然后轉(zhuǎn)第2步。廣度優(yōu)先搜索、代價(jià)樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的特例。1968年，彼得.哈特對(duì)A算法進(jìn)展了很小的修正，并證明了當(dāng)估價(jià)函數(shù)滿足一定的限制條件時(shí)，算法一定可以找到最優(yōu)解估價(jià)函數(shù)滿足一定限制條件的算法稱為A*算法f(x)=g(x)+h(x)A*算法的限制條件大于0不大于x到目的的實(shí)踐代價(jià)彼得.哈特6.2.8A*算法利用A*算法求解八數(shù)碼問題估價(jià)函數(shù)的定義f(x)=g(x)+h(x)g(x)：從初始形狀到x需求進(jìn)展的挪動(dòng)操作的次數(shù)h(x)：=x形狀下錯(cuò)放的棋子數(shù)滿足限制條件123845671238456781324567h(x)=1h(x)=2h(x)=445631238456712384567123845671+31+51+51238456712384567123845672+42+32+312384567123845673+23+412384567123845673+33+4123845674+181324567123845675+05+25711238460+4752OPEN表CLOSED表估價(jià)函數(shù)對(duì)算法的影響不同的估價(jià)函數(shù)對(duì)算法的效率能夠產(chǎn)生極大的影響不同的估價(jià)函數(shù)甚至產(chǎn)生不同的算法 f(x)=g(x)+h(x)h(x)=0：Dijkstra算法，非啟發(fā)式算法g(x)=0：貪婪搜索，無法保證找到解即使采用同樣的方式f(x)=g(x)+h(x)，不同的定義和不同的值也會(huì)影響搜索過程估價(jià)函數(shù)對(duì)算法的影響例如例：八數(shù)碼問題f(x)=g(x)+h(x)g(x)：從初始形狀到x需求進(jìn)展的挪動(dòng)操作的次數(shù)h(x)：一切棋子與目的位置的曼哈頓間隔之和曼哈頓間隔：兩點(diǎn)之間程度間隔和垂直間隔之和仍滿足估價(jià)函數(shù)的限制條件12384567h(x)=2+1+1+2=63451238456712384567123845671+41+61+61238456712384567123845672+52+52+312384567123845673+23+4123845674+181324567123845675+05+20+5571123846752例：途徑規(guī)劃SG4G4G56445566A*算法被廣泛運(yùn)用于靜態(tài)路網(wǎng)中的最短途徑規(guī)劃用間隔表示代價(jià)每一步可以往相鄰的8個(gè)無妨礙格子挪動(dòng)，挪動(dòng)間隔為1g(x)：從出發(fā)點(diǎn)S到當(dāng)前點(diǎn)x的間隔h(x)：從當(dāng)前點(diǎn)x到目的點(diǎn)G的間隔4G56455665644G564455666564G564466575