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

1、第五章 形狀空間搜索戰(zhàn)略S0Sg問(wèn)題全形狀空間問(wèn)題的搜索空間解途徑 主要內(nèi)容：形狀空間的搜索問(wèn)題5.1 搜索的概念及種類(lèi)5.2 盲目搜索5.3 啟發(fā)式搜索5.1 搜索的概念及種類(lèi)搜索的概念：找到從初始現(xiàn)實(shí)到問(wèn)題最終答案的一條推理道路，找到的這條道路是時(shí)間和空間復(fù)雜度最小的求解道路搜索種類(lèi)：“盲目搜索 ，即系統(tǒng)根據(jù)事先確定好的某種固定排序依次或隨機(jī)調(diào)用規(guī)那么?！皢l(fā)式搜索，即思索問(wèn)題領(lǐng)域可運(yùn)用的知識(shí)，根據(jù)詳細(xì)情況動(dòng)態(tài)地確定規(guī)那么的排序，優(yōu)先調(diào)用較適宜的規(guī)那么運(yùn)用。搜索例子：回溯搜索算法BACKTRACKDATADATA：當(dāng)前形狀。前往值： 勝利：前往從當(dāng)前形狀到目的形狀的途徑以規(guī)那么表的方式表示

2、 失?。呵巴鵉AIL。四皇后問(wèn)題皇后問(wèn)題 在一個(gè)4*4的國(guó)際象棋棋盤(pán)上，一次一個(gè)地?cái)[布四枚棋子，擺好后滿(mǎn)足每行、每列和對(duì)角線(xiàn)上只允許出現(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位置放上皇后。搜索戰(zhàn)略 固定次序：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) (2,3)

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) (2,4)

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 形狀空間圖的普通搜索算法5.2.2 寬度優(yōu)先搜索戰(zhàn)略5.2.3 深度優(yōu)先搜索戰(zhàn)略5.2.4 代價(jià)樹(shù)的寬度

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

6、圖的普通搜索算法幾個(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，13，1形狀空間的普通搜索算法普通搜索算法的描畫(huà)：建立一個(gè)只含有初始節(jié)點(diǎn)S0的搜索圖G，把S0放入OPEN表中建立CLOSED表，且置為空表判別OPEN表能否為空表，假設(shè)為空，那么問(wèn)題無(wú)解，退出選擇OPEN表中的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出，并放入

7、CLOSED表中，將此節(jié)點(diǎn)記為節(jié)點(diǎn)n調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)，假設(shè)是，那么問(wèn)題有解，勝利退出。問(wèn)題的解就是沿著n到S0的途徑得到。假設(shè)不是轉(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)的指針。按某一恣意方式或某種戰(zhàn)略重排OPEN表中節(jié)點(diǎn)的順序轉(zhuǎn)特例圖的一些概念

8、：1節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0，其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+12途徑 設(shè)一節(jié)點(diǎn)序列為(n0, n1,nk)，對(duì)于i=1,k，假設(shè)節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，那么該序列稱(chēng)為從n0到nk的途徑。3途徑的耗費(fèi)值一條途徑的耗費(fèi)值等于銜接這條途徑各節(jié)點(diǎn)間一切耗費(fèi)值的總和。用C(ni, nj)表示從ni到nj的途徑的耗費(fèi)值。0123節(jié)點(diǎn)類(lèi)型闡明.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)1S12645修正2和4的前往指針5.2 無(wú)信

9、息圖搜索過(guò)程盲目搜索戰(zhàn)略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、定義假設(shè)搜索是以接近起始節(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)先搜索戰(zhàn)略3、寬度優(yōu)先搜索算法(1) 把起始節(jié)點(diǎn)放到OPEN表中(假設(shè)該起始節(jié)點(diǎn)為一目的節(jié)點(diǎn)，那么求得一個(gè)解答)。(2) 假設(shè)OPEN是個(gè)空表，那么沒(méi)有解，失敗退出；否那么繼續(xù)。(3) 把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放

10、入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (4) 擴(kuò)展節(jié)點(diǎn)n。假設(shè)沒(méi)有后繼節(jié)點(diǎn)，那么轉(zhuǎn)向上述第(2)步。 (5) 把n的一切后繼節(jié)點(diǎn)放到OPEN表末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。 (6) 假設(shè)n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目的節(jié)點(diǎn)，那么找到一個(gè)解答，勝利退出；否那么轉(zhuǎn)向第(2)步。例：把寬度優(yōu)先搜索運(yùn)用于八數(shù)碼難題時(shí)所生成的搜索樹(shù)，這個(gè)問(wèn)題就是要把初始棋局變?yōu)槿缦履康钠寰值膯?wèn)題： 1 2 3 8 4 7 6 55.2.2 寬度優(yōu)先搜索戰(zhàn)略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

11、 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目的82 3 41 8 7 6 54寬度優(yōu)先搜索的性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解。當(dāng)問(wèn)題為單位耗費(fèi)值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解。算法與問(wèn)題無(wú)關(guān)，具有通用性。時(shí)間效率和空間效率都比較低。1、定義 在此搜索中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以恣意陳列。 這種盲目(無(wú)信息)搜索叫做深度優(yōu)先搜索(dep

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

13、EN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (4) 調(diào)查節(jié)點(diǎn)n能否為目的節(jié)點(diǎn)，假設(shè)是，那么找到問(wèn)題的解，用回溯法求解途徑，退出 5假設(shè)沒(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 47 6 52 81 4

14、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目的深度優(yōu)先搜索的性質(zhì)普通不能保證找到最優(yōu)解。當(dāng)深度限制不合理時(shí)，能夠找不到解。最壞情況時(shí)，搜索空間等同于窮舉。1、定義 形狀空間圖中各節(jié)點(diǎn)之間有向邊的代價(jià)是不同的，有向邊上標(biāo)有代價(jià)的搜索樹(shù)成為代價(jià)搜索樹(shù)。2、特點(diǎn) 每次從OPEN表中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)，移入CLOSED表。3、C(

15、i,j):從節(jié)點(diǎn)i到其后繼節(jié)點(diǎn)j的連線(xiàn)代價(jià)； gx:從初始節(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) 假設(shè)OPEN是個(gè)空表，那么沒(méi)有解，失敗退出；否那么繼續(xù)。(3) 把OPEN表中代價(jià)最小的節(jié)點(diǎn)即排在最前端的節(jié)點(diǎn)n，移入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (4) 假設(shè)n是目的節(jié)點(diǎn)，問(wèn)題得解，退出。否那么繼續(xù)。 (5) 判別節(jié)點(diǎn)n能否可擴(kuò)展。假設(shè)否那么轉(zhuǎn)向第(2)步，假設(shè)是那么轉(zhuǎn)向(6)。 (6) 對(duì)節(jié)點(diǎn)n進(jìn)展擴(kuò)展，將他們的一切后繼節(jié)點(diǎn)放到OPEN表中，并對(duì)每個(gè)

16、后繼節(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)移入CLOSED表進(jìn)展擴(kuò)

17、展或判別。代價(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) 假設(shè)OPEN是個(gè)空表，那么沒(méi)有解，失敗退出；否那么繼續(xù)。(3) 把OPEN表中的第一個(gè)節(jié)點(diǎn)代價(jià)最小的節(jié)點(diǎn)n，移入CLOSED表。 (4) 假設(shè)n是目的節(jié)點(diǎn)，問(wèn)題得解，退出。否那么繼續(xù)。 (5) 判別節(jié)點(diǎn)n能否可擴(kuò)展。假設(shè)否那么轉(zhuǎn)向第(2)步，假設(shè)是那么轉(zhuǎn)向(6)。 (6) 對(duì)節(jié)點(diǎn)n進(jìn)展擴(kuò)展，并將其后繼節(jié)點(diǎn)按有向邊代價(jià)C(i,j)從小到大排序后放到OPEN表

18、前端，并為每個(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ā)信息與估價(jià)函數(shù)5.

19、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ùn)用，啟發(fā)才干度量和如何獲得啟發(fā)信息。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索任務(wù)量，但能夠?qū)е抡也坏阶顑?yōu)解。弱：普通導(dǎo)致任務(wù)量加大，極限情況下變?yōu)槊つ克阉?，但能夠可以找到最?yōu)解。希望：引入啟發(fā)知識(shí)，在保證找到最正確解的前提下，盡能夠減少搜索范圍，提高搜索效率。搜索算法的效果：可以用啟發(fā)才干的強(qiáng)弱來(lái)度量。思索解途徑的耗費(fèi)值和求得途徑所需搜索的耗費(fèi)值兩者的某種組合最小。思索搜索方法對(duì)求解一

20、切能夠遇見(jiàn)的問(wèn)題，其平均的組合耗費(fèi)最小。問(wèn)題的關(guān)鍵如何尋覓最有希望的節(jié)點(diǎn) 啟發(fā)搜索過(guò)程中，要對(duì)OPEN表進(jìn)展排序，這就需求有一種方法來(lái)計(jì)算待擴(kuò)展節(jié)點(diǎn)有希望通向目的節(jié)點(diǎn)的不同程度。 我們總希望能找到最有希望通向目的節(jié)點(diǎn)的待擴(kuò)展節(jié)點(diǎn)優(yōu)先擴(kuò)展。根本思想定義一個(gè)估價(jià)函數(shù)fEvaluation Function，對(duì)當(dāng)前的搜索形狀進(jìn)展評(píng)價(jià)，找出一個(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到目的節(jié)點(diǎn)的最優(yōu)途徑的估計(jì)代價(jià)5.3.2 最正確優(yōu)先搜索部分最正確優(yōu)先搜索全局最正

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

22、函數(shù)f(S0)。(2) 假設(shè)OPEN是個(gè)空表，那么沒(méi)有解，失敗退出；否那么繼續(xù)。(3) 把OPEN表中的第一個(gè)節(jié)點(diǎn)股價(jià)函數(shù)最小的節(jié)點(diǎn)n，移入CLOSED表。(4) 假設(shè)n是目的節(jié)點(diǎn)，問(wèn)題得解，退出。否那么繼續(xù)。(5) 判別節(jié)點(diǎn)n能否可擴(kuò)展。假設(shè)否那么轉(zhuǎn)向第(2)步，假設(shè)是那么轉(zhuǎn)向(6)。(6) 對(duì)節(jié)點(diǎn)n進(jìn)展擴(kuò)展，并對(duì)其一切后繼節(jié)點(diǎn)計(jì)算估價(jià)函數(shù)fn的值，并為每個(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)的耗費(fèi)值；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 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 3