第五章?tīng)顟B(tài)空間搜索策略PPT課件

1、第五章 狀態(tài)空間搜索策略S0Sg問(wèn)題全狀態(tài)空間問(wèn)題的搜索空間解路徑 主要內(nèi)容：狀態(tài)空間的搜索問(wèn)題5.1 搜索的概念及種類(lèi)5.2 盲目搜索5.3 啟發(fā)式搜索5.1 搜索的概念及種類(lèi)搜索的概念：找到從初始事實(shí)到問(wèn)題最終答案的一條推理路線，找到的這條路線是時(shí)間和空間復(fù)雜度最小的求解路線搜索種類(lèi)：“盲目搜索” ，即系統(tǒng)根據(jù)事先確定好的某種固定排序（依次或隨機(jī)）調(diào)用規(guī)則?！皢l(fā)式搜索”，即考慮問(wèn)題領(lǐng)域可應(yīng)用的知識(shí)，根據(jù)具體情況動(dòng)態(tài)地確定規(guī)則的排序，優(yōu)先調(diào)用較合適的規(guī)則使用。搜索例子：回溯搜索算法BACKTRACK（DATA）DATA：當(dāng)前狀態(tài)。返回值： 成功：返回從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形

2、式表示） 失敗：返回FAIL。四皇后問(wèn)題皇后問(wèn)題 在一個(gè)4*4的國(guó)際象棋棋盤(pán)上，一次一個(gè)地?cái)[布四枚棋子，擺好后滿(mǎn)足每行、每列和對(duì)角線上只允許出現(xiàn)一枚棋子，即棋子之間不許相互攻擊。四皇后問(wèn)題（續(xù)） 綜合數(shù)據(jù)庫(kù)：DATA=L(表），L的元素屬于ij，1i,j4。DATA非空，其表元素表示棋子所在的行和列 規(guī)則集：if 1 i 4 且在i-1行上有一個(gè)皇后 then 在第ij位置放上皇后。搜索策略 固定次序：R11, R12, R13, , R21, R22,R44( )( )Q(1,1)( )QQ(1,1)(1,1) (2,3)( )Q(1,1)(1,1) (2,3)( )QQ(1,1)(1,1)

3、 (2,3)(1,1) (2,4)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1)

4、(2,4) (3.2)Q(1,2)Q(1,2) (2,4)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)Q(1,2) (2,4) (3,1) (4,3)5.1 搜索的概念及種類(lèi)5.2 盲目搜索5.3 啟發(fā)式搜索5.2.1 狀態(tài)空間圖的一般搜索算法5.2.2 寬度優(yōu)先搜索策略5.2.3 深度優(yōu)先搜索策略5.2.4

5、代價(jià)樹(shù)的寬度優(yōu)先搜索策略5.2.5 代價(jià)樹(shù)的深度優(yōu)先搜索策略5.2 盲目搜索策略5.2.1 狀態(tài)空間圖的一般搜索算法狀態(tài)空間表示法：用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法。(P62)主要構(gòu)成：（1）狀態(tài)，描述問(wèn)題求解過(guò)程中不同時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu)；（2）算符：使問(wèn)題由一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作。（3）狀態(tài)空間：一個(gè)問(wèn)題的全部狀態(tài)及一切可用算符構(gòu)成的集合。一般包括3部分（初始狀態(tài)集合S，算符集合F，目標(biāo)狀態(tài)集合G）（4）問(wèn)題的求解：從S出發(fā)經(jīng)過(guò)一系列的算符運(yùn)算，到達(dá)目標(biāo)狀態(tài)。由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列構(gòu)成了問(wèn)題的一個(gè)求解狀態(tài)空間圖： 把狀態(tài)空間的問(wèn)題求解過(guò)程用圖的形式表示出來(lái)。 節(jié)點(diǎn)代表狀態(tài)

6、，弧代表算符5.2.1 狀態(tài)空間圖的一般搜索算法幾個(gè)概念：擴(kuò)展：用合適的算符對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行操作，生成一組后繼節(jié)點(diǎn)，擴(kuò)展過(guò)程就是求后繼節(jié)點(diǎn)的過(guò)程。已擴(kuò)展節(jié)點(diǎn)：已經(jīng)求出了其后繼節(jié)點(diǎn)的節(jié)點(diǎn)。未擴(kuò)展節(jié)點(diǎn)：尚未求出后繼節(jié)點(diǎn)的節(jié)點(diǎn)。OPEN表：存放未擴(kuò)展的節(jié)點(diǎn)，記錄當(dāng)前節(jié)點(diǎn)及其父節(jié)點(diǎn)。CLOSED表：存放已擴(kuò)展節(jié)點(diǎn)，記錄編號(hào)、當(dāng)前節(jié)點(diǎn)及其父節(jié)點(diǎn)。圖2.26的節(jié)點(diǎn)（1，1）能生成兩個(gè)后繼節(jié)點(diǎn)（2，1）（3，1）狀態(tài)空間的一般搜索算法一般搜索算法的描述：建立一個(gè)只含有初始節(jié)點(diǎn)S0的搜索圖G，把S0放入OPEN表中建立CLOSED表，且置為空表判斷OPEN表是否為空表，若為空，則問(wèn)題無(wú)解，退出選擇OPEN表中的

7、第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出，并放入CLOSED表中，將此節(jié)點(diǎn)記為節(jié)點(diǎn)n考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則問(wèn)題有解，成功退出。問(wèn)題的解就是沿著n到S0的路徑得到。若不是轉(zhuǎn)擴(kuò)展節(jié)點(diǎn)n生成一組不是n的祖先的后繼節(jié)點(diǎn)，并將它們記為集合M，將M中的這些節(jié)點(diǎn)作為n的后繼節(jié)點(diǎn)加入圖G中對(duì)未在G中出現(xiàn)過(guò)的（OPEN和CLOSED表中未出現(xiàn)過(guò)的）集合M中的節(jié)點(diǎn)，設(shè)置一個(gè)指向父節(jié)點(diǎn)n的指針，并把這些節(jié)點(diǎn)放入OPEN表中；對(duì)于已在G中出現(xiàn)過(guò)的M中的節(jié)點(diǎn)，確定是否需要修改指向父節(jié)點(diǎn)的指針；對(duì)于已在G中出現(xiàn)過(guò)并已在closed表中的M中的節(jié)點(diǎn)，確定是否需要修改通向他們后繼節(jié)點(diǎn)的指針。按某一任意方式或某種策略重排O

8、PEN表中節(jié)點(diǎn)的順序轉(zhuǎn)特例圖的一些概念：（1）節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0，其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1（2）路徑 設(shè)一節(jié)點(diǎn)序列為(n0, n1,nk)，對(duì)于i=1,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱(chēng)為從n0到nk的路徑。（3）路徑的消耗值一條路徑的消耗值等于連接這條路徑各節(jié)點(diǎn)間所有消耗值的總和。用C(ni, nj)表示從ni到nj的路徑的消耗值。0123節(jié)點(diǎn)類(lèi)型說(shuō)明.mkmjmln擴(kuò)展點(diǎn)n，產(chǎn)生mk：沒(méi)在OPEN和CLOSED表中出現(xiàn)過(guò)mj：在OPEN表中出現(xiàn)過(guò)ml：在CLOSED表中出現(xiàn)過(guò)S123645將要擴(kuò)展節(jié)點(diǎn)6S126453修改4節(jié)點(diǎn)的返回指針S126453將要擴(kuò)展節(jié)點(diǎn)

9、1S12645修改2和4的返回指針5.2 無(wú)信息圖搜索過(guò)程盲目搜索策略5.2.2 寬度優(yōu)先搜索5.2.3 深度優(yōu)先搜索5.2.4 代價(jià)樹(shù)的寬度優(yōu)先5.2.5 代價(jià)樹(shù)的深度優(yōu)先1、定義如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-first search)。2、特點(diǎn)這種搜索是逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。5.2.2 寬度優(yōu)先搜索策略3、寬度優(yōu)先搜索算法(1) 把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。(2) 如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。(3) 把第一個(gè)

10、節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (4) 擴(kuò)展節(jié)點(diǎn)n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。 (5) 把n的所有后繼節(jié)點(diǎn)放到OPEN表末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。 (6) 如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹(shù)，這個(gè)問(wèn)題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問(wèn)題： 1 2 3 8 4 7 6 55.2.2 寬度優(yōu)先搜索策略2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52

11、 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 54寬度優(yōu)先搜索的性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解。當(dāng)問(wèn)題為單位消耗值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解。算法與問(wèn)題無(wú)關(guān)，具有通用性。時(shí)間效率和空間效率都比較低。1、定義 在此搜索中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。 這種盲目(無(wú)

12、信息)搜索叫做深度優(yōu)先搜索(depth-first search)。2、特點(diǎn) 首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。3、深度界限 為了避免考慮太長(zhǎng)的路徑(防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去)，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將把它們作為沒(méi)有后繼節(jié)點(diǎn)處理。 5.2.3 深度優(yōu)先搜索策略3、深度優(yōu)先搜索算法(1) 把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。(2) 如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。(3)

13、把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (4) 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則找到問(wèn)題的解，用回溯法求解路徑，退出 （5）如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。 (6) 擴(kuò)展節(jié)點(diǎn)n，把n的所有后繼節(jié)點(diǎn)放到OPEN表前端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。轉(zhuǎn)向第(2)步。2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1

14、47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789101112131 2 3 8 47 6 5目標(biāo)深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解。當(dāng)深度限制不合理時(shí)，可能找不到解。最壞情況時(shí)，搜索空間等同于窮舉。1、定義 狀態(tài)空間圖中各節(jié)點(diǎn)之間有向邊的代價(jià)是不同的，有向邊上標(biāo)有代價(jià)的搜索樹(shù)成為代價(jià)搜索樹(shù)。2、特點(diǎn) 每次從OPEN表中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)，移

15、入CLOSED表。3、C(i,j):從節(jié)點(diǎn)i到其后繼節(jié)點(diǎn)j的連線代價(jià)； g（x）:從初始節(jié)點(diǎn)到任意節(jié)點(diǎn)x的路徑代價(jià)； g(j)=g(i)+C(i,j).5.2.4 代價(jià)樹(shù)的寬度優(yōu)先搜索4、代價(jià)樹(shù)的寬度優(yōu)先搜索算法(1) 把起始節(jié)點(diǎn)放到OPEN表中，令g(S0)=0。(2) 如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。(3) 把OPEN表中代價(jià)最小的節(jié)點(diǎn)（即排在最前端的節(jié)點(diǎn)n），移入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (4) 如果n是目標(biāo)節(jié)點(diǎn)，問(wèn)題得解，退出。否則繼續(xù)。 (5) 判斷節(jié)點(diǎn)n是否可擴(kuò)展。若否則轉(zhuǎn)向第(2)步，若是則轉(zhuǎn)向(6)。 (6) 對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展，將他們的所有后繼節(jié)點(diǎn)放到O

16、PEN表中，并對(duì)每個(gè)后繼節(jié)點(diǎn)j計(jì)算其總代價(jià)g(j)=g(j)+C(i,j),為每個(gè)后繼節(jié)點(diǎn)指向n節(jié)點(diǎn)的指針，然后根據(jù)節(jié)點(diǎn)的代價(jià)大小對(duì)OPEN表中的所有節(jié)點(diǎn)進(jìn)行從小到大的排序。 (7) 轉(zhuǎn)向第(2)步。例子：推銷(xiāo)員旅行問(wèn)題P193ACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)AACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)A66BA77CAACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)A66BA71175CDABACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)A66BA71114157578CDDEABCC節(jié)點(diǎn)擴(kuò)展順序：A，B，C，D，D，E路線：A-C-E代價(jià)樹(shù)的寬度優(yōu)先搜索每次從OPEN表中的全體節(jié)點(diǎn)中選擇代價(jià)最小的節(jié)點(diǎn)移入

17、CLOSED表進(jìn)行擴(kuò)展或判斷。代價(jià)樹(shù)的深度優(yōu)先搜索從剛剛擴(kuò)展的節(jié)點(diǎn)的后繼節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)移入CLOSED表中，并進(jìn)行擴(kuò)展或判斷。5.2.5 代價(jià)樹(shù)的深度優(yōu)先搜索4、代價(jià)樹(shù)的深度優(yōu)先搜索算法(1) 把起始節(jié)點(diǎn)放到OPEN表中，令g(S0)=0。(2) 如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。(3) 把OPEN表中的第一個(gè)節(jié)點(diǎn)（代價(jià)最小的節(jié)點(diǎn)n），移入CLOSED表。 (4) 如果n是目標(biāo)節(jié)點(diǎn)，問(wèn)題得解，退出。否則繼續(xù)。 (5) 判斷節(jié)點(diǎn)n是否可擴(kuò)展。若否則轉(zhuǎn)向第(2)步，若是則轉(zhuǎn)向(6)。 (6) 對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展，并將其后繼節(jié)點(diǎn)按有向邊代價(jià)（C(i,j)）從小到大排序后

18、放到OPEN表前端，并為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向n節(jié)點(diǎn)的指針。 (7) 轉(zhuǎn)向第(2)步。ACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)AACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)A66BA77CAACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)A66BA71175CDABACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)A66BA71117187578CDECABDD節(jié)點(diǎn)擴(kuò)展順序：A，B，C，D，E路線：A-B-D-EACBDE768765gC節(jié)點(diǎn)n父節(jié)點(diǎn)A66BA71114157578CDDEABCC節(jié)點(diǎn)擴(kuò)展順序：A，B，C，D，D，E路線：A-C-E5.1 搜索的概念及種類(lèi)5.2 盲目搜索5.3 啟發(fā)式搜索5.3.1 啟發(fā)信息

19、與估價(jià)函數(shù)5.3.2 最佳優(yōu)先搜索5.3.3 A*搜索算法5.3 啟發(fā)式圖搜索 5.3.1啟發(fā)信息與估價(jià)函數(shù)定義利用與問(wèn)題有關(guān)的知識(shí)（即：?jiǎn)l(fā)信息）來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的搜索過(guò)程稱(chēng)為啟發(fā)式搜索方法。核心問(wèn)題：?jiǎn)l(fā)信息應(yīng)用，啟發(fā)能力度量和如何獲得啟發(fā)信息。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解。弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解。希望：引入啟發(fā)知識(shí)，在保證找到最佳解的前提下，盡可能減少搜索范圍，提高搜索效率。搜索算法的效果：可以用啟發(fā)能力的強(qiáng)弱來(lái)度量?？紤]解路徑的消耗值和求得路徑所需搜索的消耗值兩者的某種組合最小?？紤]搜

20、索方法對(duì)求解所有可能遇見(jiàn)的問(wèn)題，其平均的組合消耗最小。問(wèn)題的關(guān)鍵如何尋找最有希望的節(jié)點(diǎn) 啟發(fā)搜索過(guò)程中，要對(duì)OPEN表進(jìn)行排序，這就需要有一種方法來(lái)計(jì)算待擴(kuò)展節(jié)點(diǎn)有希望通向目標(biāo)節(jié)點(diǎn)的不同程度。 我們總希望能找到最有希望通向目標(biāo)節(jié)點(diǎn)的待擴(kuò)展節(jié)點(diǎn)優(yōu)先擴(kuò)展?；舅枷攵x一個(gè)估價(jià)函數(shù)f（Evaluation Function），對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)“最有希望”的節(jié)點(diǎn)來(lái)擴(kuò)展。估價(jià)函數(shù)的格式：f(n) = g(n) + h(n)f(n)：估價(jià)函數(shù)g(n)：代價(jià)函數(shù)， 初始節(jié)點(diǎn)到節(jié)點(diǎn)n已實(shí)際付出的代價(jià) h(n)：?jiǎn)l(fā)函數(shù)， 從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的估計(jì)代價(jià)5.3.2 最佳優(yōu)先搜索局部最佳

21、優(yōu)先搜索全局最佳優(yōu)先搜索局部最佳優(yōu)先搜索：(1) 把起始節(jié)點(diǎn)放到OPEN表中，并計(jì)算估價(jià)函數(shù)f(S0)。(2) 如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。(3) 把OPEN表中的第一個(gè)節(jié)點(diǎn)（股價(jià)函數(shù)最小的節(jié)點(diǎn)n），移入CLOSED表。(4) 如果n是目標(biāo)節(jié)點(diǎn)，問(wèn)題得解，退出。否則繼續(xù)。(5) 判斷節(jié)點(diǎn)n是否可擴(kuò)展。若否則轉(zhuǎn)向第(2)步，若是則轉(zhuǎn)向(6)。(6) 對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展，并對(duì)其所有后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)f（n）的值，并按其值從小到大排序后放到OPEN表前端，并為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向n節(jié)點(diǎn)的指針。(7) 轉(zhuǎn)向第(2)步。全局最佳優(yōu)先搜索：(1) 把起始節(jié)點(diǎn)放到OPEN表中，并計(jì)算

22、估價(jià)函數(shù)f(S0)。(2) 如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。(3) 把OPEN表中的第一個(gè)節(jié)點(diǎn)（股價(jià)函數(shù)最小的節(jié)點(diǎn)n），移入CLOSED表。(4) 如果n是目標(biāo)節(jié)點(diǎn)，問(wèn)題得解，退出。否則繼續(xù)。(5) 判斷節(jié)點(diǎn)n是否可擴(kuò)展。若否則轉(zhuǎn)向第(2)步，若是則轉(zhuǎn)向(6)。(6) 對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展，并對(duì)其所有后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)f（n）的值，并為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向n節(jié)點(diǎn)的指針。把這些后繼節(jié)點(diǎn)都送入OPEN表，然后對(duì)OPEN表中的全部節(jié)點(diǎn)按照估價(jià)函數(shù)值從小到大的順序排序。(7) 轉(zhuǎn)向第(2)步。例子定義評(píng)價(jià)函數(shù)：f(n) = g(n) + h(n)= d(n)+h(n)；d(n)：代表節(jié)點(diǎn)的深度，表示從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的消耗值；h(n)：為當(dāng)前節(jié)點(diǎn)“不在位”的牌數(shù)。2 8 31 6 47 51 2 38 47 6 5h計(jì)算舉例h(n) =4 2 8 31 6 47 51 2 3457 6 82 8 31 6 47 52 8