第五章 狀態(tài)空間的搜索策略

1、狀態(tài)空間的搜索策略北京師范大學(xué)信息科學(xué)與技術(shù)學(xué)院王醒策概述n教學(xué)內(nèi)容n搜索的概念及種類n盲目搜索策略n啟發(fā)式搜索策略n教學(xué)重點n寬度優(yōu)先搜索、深度優(yōu)先搜索及代價樹的搜索算法，A*搜索算法n教學(xué)難點n利用各種搜索算法解決實際問題，尤其是估價函數(shù)的選取概述n有哪些常用的搜索算法。n問題有解時能否找到解。n找到的解是最佳的嗎？n什么情況下可以找到最佳解？n求解的效率如何。概述n搜索是人工智能中的基本問題n搜索中的知識表示n狀態(tài)空間表示法n與/或樹表示法n很多問題可以轉(zhuǎn)化為搜索問題搜索的概念以及分類n搜索的概念n根據(jù)問題的實際情況，按照一定的策略或者規(guī)劃，從知識庫中尋找可以利用的知識，從而構(gòu)造出一條使

2、得問題獲得解決的推理路線的過程n搜索的兩層含義n要找到從初始事實到問題最終答案的一條推理路線n找到的這條路線是時間和空間復(fù)雜度最小的求解路線搜索的種類n搜索可以分為盲目搜索和啟發(fā)式搜索兩種n盲目搜索n又稱為無信息搜索。也就是在搜索的過程中只按預(yù)先的搜索控制策略進行搜索，而沒有任何中間信息來改變這些控制策略n啟發(fā)式搜索n稱為有信息搜索。它是指在問題搜索過程中，根據(jù)問題本身的特征或者搜索過程中產(chǎn)生出來的一些信息來不斷地改變或者調(diào)整搜索方向，使搜索朝著最有希望的方向前進，加速問題的求解，并找到最優(yōu)解。人工智能領(lǐng)域中已有搜索方法 n（1）求任一解路的搜索策略n回溯法（Backtracking）n爬山法

3、（Hill Climbing）n寬度優(yōu)先法（Breadth-first）n深度優(yōu)先法（Depth-first）n限定范圍搜索法（Beam Search）n好的優(yōu)先法（Best-first）人工智能領(lǐng)域中已有搜索方法n（2）求最佳解路的搜索策略n大英博物館法（British Museum）n分枝界限法（Branch and Bound）n動態(tài)規(guī)劃法（Dynamic Programming）n最佳圖搜索法（A）人工智能領(lǐng)域中已有搜索方法n（3）求與或關(guān)系解圖的搜索法n一般與或圖搜索法（AO）n極小極大法（Minimax）n剪枝法（Alpha-beta Pruning）n啟發(fā)式剪枝法（Heurist

4、ic Pruning）回溯搜索（Backtracking strategies）n回溯搜索策略是盲目搜索中的一種。思想為：n首先將規(guī)則給出一個固定的排序；n在搜索時，對當(dāng)前狀態(tài)（搜索開始時，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測每一條規(guī)則；n在當(dāng)前狀態(tài)未使用過的規(guī)則中找到第一條可觸發(fā)規(guī)則，被應(yīng)用于當(dāng)前狀態(tài)；n得到的新狀態(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索；n如果當(dāng)前狀態(tài)無規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過仍未找到問題的解，則將當(dāng)前狀態(tài)的前一個狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前狀態(tài)。n重復(fù)以上搜索，直到找到問題的解，或者試探了所有可能后仍找不到問題的解為止?；厮菟阉鱪舉例說明：四皇后問題n在一個44

5、的國際象棋棋盤上，一次一個地擺布四枚皇后棋子，擺好后要滿足每行、每列和對角線上只允許出現(xiàn)一枚棋子，即棋子間不許相互俘獲?；厮菟阉鱪給出棋盤的幾個勢態(tài)，其中a，b滿足目標條件，c，d，e為不合法狀態(tài)，即不可能構(gòu)成滿足目標條件的中間態(tài)勢回溯搜索n搜索方法的實現(xiàn)遞歸實現(xiàn)n遞歸方法的特點n遞歸必須要有出口n遞歸公式中，每一次調(diào)用必須距出口更近一些回溯搜索回溯搜索n算法步驟Backtrack(DATA)n如果當(dāng)前狀態(tài)DATA為目標狀態(tài)，則找到目標。n該狀態(tài)不合法，則過程返回失敗信息 ，必須回溯。n計算DATA（當(dāng)前狀態(tài)）的可應(yīng)用規(guī)則集，依某種原則（任意排列或按啟發(fā)式準則）排列后賦給RULES。n如果規(guī)則

6、用完未找到目標，過程返回FAIL，必須回溯?；厮菟阉鱪取頭條可應(yīng)用規(guī)則。n刪去頭條規(guī)則，減少可應(yīng)用規(guī)則表的長度。n調(diào)用規(guī)則R作用于當(dāng)前狀態(tài)，生成新狀態(tài)（RDATA）。n對新狀態(tài)遞歸調(diào)用本過程。n當(dāng)PATHFAIL時，遞歸調(diào)用失敗，則轉(zhuǎn)移回第四步，調(diào)用另一規(guī)則進行測試。n過程返回解路徑規(guī)則表（或局部解路徑子表）。回溯搜索n回溯搜索會出現(xiàn)的問題n深度問題n死循環(huán)問題回溯搜索n回溯中失敗原因的分析多步回溯問題n回溯搜索中知識的應(yīng)用盲目搜索策略n狀態(tài)空間圖的搜索策略n寬度優(yōu)先搜索策略n深度優(yōu)先搜索策略n代價樹的寬度優(yōu)先搜索n代價樹的深度優(yōu)先搜索n盲目搜索的性質(zhì)總結(jié)狀態(tài)空間圖的搜索策略n算法思想：n首先

7、將問題的初始狀態(tài)（即狀態(tài)空間中的初始節(jié)點）當(dāng)作是當(dāng)前狀態(tài)。n選擇一個合適的算符作用于當(dāng)前狀態(tài)，生成一組后繼狀態(tài)（或稱為）后繼節(jié)點，n然后檢查這組后繼狀態(tài)中有沒有目標狀態(tài)。n如果有，則說明搜索成功，從初始狀態(tài)到目標狀態(tài)的一系列算符即是問題的解；若沒有，則按照某種控制策略從已生成的狀態(tài)中再選一個狀態(tài)作為當(dāng)前狀態(tài)，n重復(fù)上述的過程直到目標狀態(tài)不在出現(xiàn)或者不再有可供操作的狀態(tài)及算符為止。狀態(tài)空間圖的搜索策略n圖論中的幾個術(shù)語n節(jié)點深度：n初始節(jié)點（根節(jié)點）的深度為0n任何其它節(jié)點的深度等于父節(jié)點的深度加1n路徑：n設(shè)一節(jié)點的序列為（n0,n1,ni,nk）i=1k若在任意一個節(jié)點ni-1都有一個后繼的

8、節(jié)點ni，則稱該節(jié)點序列為節(jié)點n0到nk長度為k的一條路徑。狀態(tài)空間圖的搜索策略n路徑耗散值：n令C( ni, nj)為節(jié)點ni到nj這段路徑（或弧線）的耗散值，一條路徑的耗散值等于連接這條路徑各節(jié)點間所有弧線耗散值的總和。n初始節(jié)點S0到任意節(jié)點的x的路徑耗散值稱為路徑代價，記為g(x)n路徑耗散值可按如下遞歸公式計算：g(nj)=g(ni)+C(ni,nj)狀態(tài)空間圖的搜索策略n已擴展節(jié)點和未擴展節(jié)點n擴展節(jié)點n所謂已擴展節(jié)點就是用合適的算符對某個節(jié)點操作后生成的一組后繼節(jié)點。擴展的過程實際上就是求得后繼節(jié)點的過程。n已擴展節(jié)點n對狀態(tài)空間圖中的某個節(jié)點，如果求出了它的后繼節(jié)點，則此節(jié)點稱

9、為已擴展節(jié)點。n未擴展節(jié)點n對狀態(tài)空間圖中的某個節(jié)點，如果未求出它的后繼節(jié)點，則稱此節(jié)點為未擴展節(jié)點。狀態(tài)空間圖的搜索策略n一般來講，習(xí)慣于將未擴展的節(jié)點存放于一個名為open的表中，而將已擴展的節(jié)點存放于名為closed的表中。nOpen 表和closed表的數(shù)據(jù)結(jié)構(gòu)如下所示：狀態(tài)空間圖的搜索策略n狀態(tài)空間的搜索算法：n1 建立一個只含有初始節(jié)點S0的搜索圖G，把S0放入到open表中n2 建立closed表，并且將其置為空表n3 判斷open表是否為空表，若為空，則問題無解，退出。n4 若open表非空，則選擇open表中的第一個節(jié)點，把它從open表中移出，并放入closed表中，將此節(jié)

10、點標記為節(jié)點n。狀態(tài)空間圖的搜索策略n5 考察節(jié)點n是 否為目標節(jié)點，如果是，則問題有解，并且成功退出。問題的解既可從圖G中沿著指針從n到S0的這條路徑得到。n6 擴展節(jié)點n生成一組不是n的祖先的后繼節(jié)點，并將它們記為集合M，將M中的這些節(jié)點作為n的后繼節(jié)點加入圖G中。狀態(tài)空間圖的搜索策略n7 對于那些未曾在G中出現(xiàn)過的（即未曾在open表上或closed表上出現(xiàn)過的）M中的節(jié)點，設(shè)置一個指向父節(jié)點（即節(jié)點n）的指針，并把這些節(jié)點加入到open表中；對于已在G中出現(xiàn)過的M中的那些節(jié)點，確定是否需要修改指向父節(jié)點（n節(jié)點）的指針；對于那些先前已經(jīng)在G中出現(xiàn)并且已在closed表中的那些M中的節(jié)點

11、，確定是否需要修改通向它們后繼點的指針。n8 按照某一種方式或者某種策略重排open表中的節(jié)點的順序n9 轉(zhuǎn)到第（3）步。狀態(tài)空間圖的搜索策略n解釋；n這里給出的是一個圖搜索的一般框架，不是一個具體的算法，n關(guān)鍵是算法的第8步，按不同的原則對open表進行排序，將得到不同的圖搜索算法。 n上面的搜索過程實際上就是問題的求解過程。在利用狀態(tài)空間搜索法來求解問題時，并不是將問題的狀態(tài)空間圖全部輸入計算機，而只是存入與問題有關(guān)的部分狀態(tài)空間圖，這種部分狀態(tài)空間圖是在搜索過程中生成的，并且每計算一步都要檢查是否達到了目標節(jié)點，這樣就可能盡量少地生成與問題無關(guān)的狀態(tài)。狀態(tài)空間圖的搜索策略n節(jié)點類型說明狀

12、態(tài)空間圖的搜索策略n修改指針的說明狀態(tài)空間圖的搜索策略狀態(tài)空間圖的搜索策略狀態(tài)空間圖的搜索策略寬度優(yōu)先搜索策略n寬度優(yōu)先n又稱為是廣度優(yōu)先；n是一種盲目的搜索策略。n它的基本思想是：n從初始節(jié)點開始，逐層對節(jié)點進行依次擴展，并考察它是否為目標節(jié)點。在對下層的節(jié)點進行擴展或者是搜索之前，必須完成對當(dāng)前層的所有節(jié)點的擴展或者是搜索。nOpen表的節(jié)點排隊準則：n先進入open表中，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。寬度優(yōu)先搜索策略n算法：狀態(tài)空間圖的寬度優(yōu)先搜索算法n把初始節(jié)點S0放入到open表中n判斷open表是否為空，若為空，則問題無解，退出，否則繼續(xù)。n選擇open表中的第一個節(jié)

13、點（標記為節(jié)點n ），把它從open表中移出，并放入closed表中。寬度優(yōu)先搜索策略n考察節(jié)點n是 否為目標節(jié)點，若是，則求解結(jié)束，得到解路徑。n若節(jié)點n不可擴展，則轉(zhuǎn)到第2步，否則執(zhí)行第6步。n對節(jié)點n進行擴展，將它的所有后繼節(jié)點放入open表的末端，并為這些節(jié)點設(shè)置指向父節(jié)點n的指針，然后轉(zhuǎn)到第2步。初始節(jié)點S放入到OPEN表OPEN表為空？OPEN表的第一個節(jié)點移出(節(jié)點n)，放入CLOSED表中對節(jié)點n進行擴展節(jié)點n為目標節(jié)點？節(jié)點n不可擴展？寬度優(yōu)先搜索框圖寬度優(yōu)先搜索框圖問題無解NYYNNY求解結(jié)束，回溯得到解路徑將它的所有后繼節(jié)點放入OPEN表的末端，并為這些節(jié)點設(shè)置指向父節(jié)點

14、n的指針算法實現(xiàn)過程OPEN表ClOSED表SLF寬度優(yōu)先搜索策略寬度優(yōu)先搜索策略n例題：八數(shù)碼難題n設(shè)在一個3*3的方格模型上，擺放八個數(shù)碼1、2、3、4、5、6、7、8，其中有一個時空格，空格可以執(zhí)行如下操作：空格左移，空格上移，空格下移，空格右移。初始狀態(tài)和目標狀態(tài)如下所示：寬度優(yōu)先搜索策略深度優(yōu)先搜索n深度優(yōu)先是一種盲目的搜索策略n深度優(yōu)先思想：n首先最先擴展最先產(chǎn)生的節(jié)點，即從初始節(jié)點S0開始，在它的后繼節(jié)點種選擇一個節(jié)點，對其進行考察。若它不是目標節(jié)點，則對該節(jié)點進行擴展，并再度從它的后繼節(jié)點種選擇一個節(jié)點進行考察，以此類推，一直搜索下去，當(dāng)達到某個非目標節(jié)點又無法繼續(xù)擴展的點時，

15、才選擇兄弟節(jié)點進行考察深度優(yōu)先搜索深度優(yōu)先搜索n算法：狀態(tài)空間圖的深度優(yōu)先搜索算法n把初始節(jié)點S0放入到open表中來；n如果open表為空，則問題無解退出；n從open表中將第一個節(jié)點（節(jié)點n）移出，放入已擴展節(jié)點表closed中；n考察節(jié)點n是否為目標節(jié)點，若是則找到問題的解，給與相應(yīng)的解路徑，退出；n若節(jié)點n不可擴展，則轉(zhuǎn)到第2步n擴展節(jié)點n，將其后繼節(jié)點放到open表的前端，并為其設(shè)置指向節(jié)點n的指針，然后轉(zhuǎn)向第2步。深度優(yōu)先搜索n深度優(yōu)先和寬度優(yōu)先的區(qū)別n對節(jié)點n進行擴展的時候，其后繼節(jié)點在open表中存在的位置。寬度優(yōu)先搜索的將后繼節(jié)點放入open表的末端而深度優(yōu)先搜索則是將后得到

16、的節(jié)點放入open表的前端。有界深度優(yōu)先搜索n產(chǎn)生原因 ：n深度優(yōu)先搜索對于有限狀態(tài)空間圖來說，總能夠找到解。但是對于無限圖來講就未必。并且相對來講搜索效率會比較低。所以為了防止在無解的分支上進行無效的搜索，需要對搜索深度做一些限制。n思想：n任何節(jié)點如果到達了深度限制，就把它作為沒有后繼節(jié)點進行處理，對另一個分支進行搜索。有界深度優(yōu)先搜索n有界深度優(yōu)先算法n1 把初始節(jié)點S0放入open表中n2 如果open表為空，則問題無解，退出n3 把open表中的第一個節(jié)點（節(jié)點n）從open表中移到closed表中。n4 考察節(jié)點n是否為目標節(jié)點，若是則求得問題的解，并退出；否則繼續(xù)執(zhí)行第5步有界深

17、度優(yōu)先搜索n5 如果節(jié)點n的深度等于最大深度，則轉(zhuǎn)第2步n6 如果節(jié)點n不可以擴展，既沒有后繼節(jié)點，則轉(zhuǎn)到第2步，否則轉(zhuǎn)到第7步n7 擴展節(jié)點n，將后繼節(jié)點放入到open表的前端，并為其設(shè)置指向節(jié)點n的指針，然后轉(zhuǎn)向第2步。有界深度優(yōu)先搜索n例題n設(shè)八數(shù)碼難題的初始狀態(tài)和目標狀態(tài)如下所示，請采用有界深度優(yōu)先的策略求解問題的搜索樹，深度界限dm=5有界深度優(yōu)先搜索n解釋說明n在有界深度優(yōu)先搜索算法中，深度界限的選擇很重要。n在某些問題中，他的解可能就位于某一分支較深的位置上，而界限選擇如果沒有足夠大的話，可能就會找不到問題的解。n所以有界深度優(yōu)先搜索策略是不完備的。代價樹的搜索n介紹n前面所介紹

18、的問題都是單位耗散問題，下面將要介紹的是非單位耗散的時候如何構(gòu)造搜索策略。n這里將介紹兩種方法：n代價樹寬度優(yōu)先搜索n代價樹深度優(yōu)先搜索代價樹寬度優(yōu)先搜索n算法的基本思想n每次從open表中選擇一個代價最小的節(jié)點，移入closed表中。n因此對每一個節(jié)點擴展之后，就要計算它所有的后繼節(jié)點的代價，并將它們與open表中得以有待擴展的節(jié)點按照代價的大小進行排序n從open表中選擇的下一個被擴展節(jié)點是排在最前面的解點。代價樹寬度優(yōu)先搜索n算法：代價樹寬度優(yōu)先搜索算法n1 把初始節(jié)點S0放入open表中，令g(S0)=0n2 如果open表為空，則問題無解，退出n3 把open表中的代價最小的節(jié)點，即

19、排在最前端的節(jié)點（節(jié)點n）從open表中移到closed表中。n4 考察節(jié)點n是否為目標節(jié)點，若是則求得問題的解，并退出；否則繼續(xù)。代價樹寬度優(yōu)先搜索n5 判斷節(jié)點n是否可以擴展，如果不可以擴展則轉(zhuǎn)向第2步，否則繼續(xù)n6 對節(jié)點n進行擴展，將它們所有的后繼節(jié)點放入open表中，并對每一個后繼節(jié)點nj計算其代價 g(j)=g(i)+c(i,j)n7 為每一個后繼節(jié)點設(shè)置指向n的指針，然后根據(jù)節(jié)點的代價大小對open表中的所有節(jié)點進行從小到大排序n8 轉(zhuǎn)向第2步代價樹寬度優(yōu)先搜索n例題：推銷員最短路徑問題n假設(shè)A,B,C,D,E是五個城市，推銷員要從A城出發(fā)，到達E城。需要走怎樣的路徑，費用才能最

20、省？n五個城市的交通圖以及每兩個城市間的旅行費用如下所示，圖中的數(shù)字就是旅行費用。代價樹的深度優(yōu)先搜索策略n代價樹的深度優(yōu)先搜索和寬度優(yōu)先搜索的區(qū)別n代價樹寬度優(yōu)先搜索每次都從open表中選擇一個代價最小的節(jié)點移入closed表中，并對這一節(jié)點判斷是否為目標點或者擴展n而代價樹寬度優(yōu)先搜索則是從剛剛擴展的節(jié)點的后繼節(jié)點種選擇一個代價最小的節(jié)點移入closed表中，并進行擴展或者判斷代價樹的深度優(yōu)先搜索策略n代價樹深度優(yōu)先搜索策略算法n1 把初始節(jié)點S0放入open表中，令g(S0)=0n2 如果open表為空，則問題無解，退出n3 把open表中的代價最小的節(jié)點，即排在最前端的節(jié)點（節(jié)點n）從

21、open表中移到closed表中。n4 考察節(jié)點n是否為目標節(jié)點，若是則求得問題的解，并退出；否則繼續(xù)。代價樹的深度優(yōu)先搜索策略n5 判斷節(jié)點n是否可以擴展，如果不可以擴展則轉(zhuǎn)向第2步，否則繼續(xù)n6 對節(jié)點n進行擴展，將它們所有的后繼節(jié)點按照有向邊的代價從小到大的排序之后放入open表的前端。n7 為每一個后繼節(jié)點設(shè)置指向n的指針n8 轉(zhuǎn)向第2步代價樹深度優(yōu)先搜索n例題：推銷員最短路徑問題n假設(shè)A,B,C,D,E是五個城市，推銷員要從A城出發(fā)，到達E城。需要走怎樣的路徑，費用才能最??？n五個城市的交通圖以及每兩個城市間的旅行費用如下所示，圖中的數(shù)字就是旅行費用。性質(zhì)總結(jié)n我們來總結(jié)一下深度優(yōu)先

22、和寬度優(yōu)先的性質(zhì) n深度優(yōu)先n一般不能保證找到最優(yōu)解n解與深度限制有密切的關(guān)系n深度優(yōu)先搜索的效率n與回溯方法的差別n是一個通用的方法性質(zhì)總結(jié)n寬度優(yōu)先n當(dāng)問題有解的時候，一定能找到n當(dāng)問題為單位耗散值的時候，且問題有解，則找到的一定是最優(yōu)解n方法與問題無關(guān)，是一種通用的搜索策略n效率比較低下n屬于圖搜索的范圍漸進式深度優(yōu)先搜索n目的n解決寬度優(yōu)先搜索方法的空間問題和深度優(yōu)先方法和回溯方法不能找到最優(yōu)解的問題n思想 n先給定深度優(yōu)先搜索一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或者是遍尋過所有的分支為止。啟發(fā)式搜索策略n概述n最佳優(yōu)先搜索n局部最佳優(yōu)先搜索算法n全局最佳優(yōu)先搜索算法

23、n最佳圖搜索法nA算法nA算法啟發(fā)信息與估價函數(shù)n搜索過程中，關(guān)鍵的一步是確定如何選擇下一個要被考察的點，不同的選擇方法面對著不同的搜索策略。n啟發(fā)信息n可以用來指導(dǎo)搜索過程且與具體問題求解有關(guān)的控制信息稱為啟發(fā)信息啟發(fā)信息與估價函數(shù)n啟發(fā)信息的種類n用于決定要擴展的下一個節(jié)點，以避免像深度優(yōu)先或者寬度優(yōu)先那樣盲目地擴展n在擴展節(jié)點的過程中，用于決定要生成哪一個或者那幾個后繼節(jié)點，以免盲目地生成所有可能的后繼節(jié)點n用于確定某些應(yīng)該從搜索樹中拋棄或者修剪的節(jié)點。啟發(fā)信息與估價函數(shù)n估價函數(shù)（Evlauation function）n用來度量或者是估算節(jié)點的“希望”程度的函數(shù)。n估價函數(shù)的定義基本

24、原則n一個節(jié)點處在最佳路徑上的概率n求出任意一個節(jié)點與目標節(jié)點集之間的距離度量或者差異度量n根據(jù)格局（博弈）問題或者狀態(tài)的特點來打分啟發(fā)信息與估價函數(shù)n啟發(fā)式信息對算法的影響n強強：啟發(fā)式信息強，可以降低搜索的工作量，但可能丟失最優(yōu)解。n弱弱：啟發(fā)式信息弱，搜索的工作量加大，但是一般容易找到最優(yōu)解。最佳優(yōu)先搜索n算法概述n又稱為有序搜索或者擇優(yōu)搜索，n算法思想n最佳優(yōu)先搜索算法總是挑選最有希望的節(jié)點作為下一個要擴展的節(jié)點，而這種最有希望的順序是按照估價函數(shù)f(x)的值來挑選。一般估價函數(shù)的值越小，它的希望程度越大局部最佳優(yōu)先搜索n算法概述n局部最佳優(yōu)先搜索算法有些類似于深度優(yōu)先搜索算法，但是由

25、于使用了與問題特征有關(guān)的估價函數(shù)來確定下一個帶擴展節(jié)點，所以它是一種啟發(fā)是搜索算法。局部最佳優(yōu)先搜索n算法思想n當(dāng)對某一個節(jié)點擴展之后，對它的每一個后繼節(jié)點計算估價函數(shù)f(x)的值，并在這些后繼節(jié)點的范圍內(nèi)，選擇一個f(x)值最小的節(jié)點，作為下一個要考察的節(jié)點n由于他每次只是在后繼節(jié)點的范圍內(nèi)選擇一個要考察的點，范圍比較小，所以稱為局部局部最佳優(yōu)先搜索最佳優(yōu)先搜索或者局部擇優(yōu)搜索局部擇優(yōu)搜索局部最佳優(yōu)先搜索n算法：局部最佳優(yōu)先搜索算法n1 把初始節(jié)點S0放入open表中，令f(S0)=0n2 如果open表為空，則問題無解，退出。否則轉(zhuǎn)第三步。n3 把open表中選取第一個節(jié)點（節(jié)點n）從op

26、en表中移到closed表中。n4 考察節(jié)點n是否為目標節(jié)點，若是則求得問題的解，并退出；否則繼續(xù)。局部最佳優(yōu)先搜索n5 判斷節(jié)點n是否可以擴展，如果不可以擴展則轉(zhuǎn)向第2步，否則繼續(xù)n6 對節(jié)點n進行擴展，并對它所有的后繼節(jié)點計算估價函數(shù)f(x)的值，并按照估價函數(shù)f(x)從小到大的順序依次放入open表的前端。n7 為每個后繼節(jié)點設(shè)置指向n的指針n8 轉(zhuǎn)向第2步局部最佳優(yōu)先搜索n局部最佳優(yōu)先搜索與深度優(yōu)先及代價樹深度優(yōu)先搜索的區(qū)別n選擇下一個節(jié)點時所用的標準不一樣局部最佳優(yōu)先搜索n局部最佳優(yōu)先搜索n估價函數(shù)的值作為標準n深度優(yōu)先搜索n后繼節(jié)點的深度作為選擇標準，后生成的節(jié)點先考察n代價樹深度

27、優(yōu)先搜索n各后繼節(jié)點到其前驅(qū)節(jié)點之間的代價作為選擇標準。局部最佳優(yōu)先搜索n如果把層深度函數(shù)d(x)當(dāng)作估價函數(shù)f(x)，或者是把代價函數(shù)g(x)當(dāng)作估價函數(shù)f(x)，那么就可以把深度優(yōu)先搜索和代價樹深度優(yōu)先搜索看作是局部最佳優(yōu)先搜索的兩個特例。全局最佳優(yōu)先搜索n算法概述n由信息的啟發(fā)式搜索，類似于寬度優(yōu)先搜索。n所不同的事，在確定下一個擴展節(jié)點時，以與問題特性密切相關(guān)的估價函數(shù)作為標準，不過這種方法實在open表中的全部節(jié)點中選擇一個估價函數(shù)值f(x)最小的節(jié)點，作為下一個被考察的節(jié)點。全局最佳優(yōu)先搜索n算法概述n正因為選擇的范圍是open表中的全部節(jié)點，所以它成為全局最佳優(yōu)先搜索全局最佳優(yōu)先

28、搜索或者是全局擇全局擇優(yōu)搜索。優(yōu)搜索。全局最佳優(yōu)先搜索n算法：n1 把初始節(jié)點S0放入open表中，計算f(S0)n2 如果open表為空，則問題無解，退出。n3 把open表中選取第一個節(jié)點（節(jié)點n）從open表中移到closed表中。n4 考察節(jié)點n是否為目標節(jié)點，若是則求得問題的解，并退出；否則繼續(xù)。全局最佳優(yōu)先搜索n5 判斷節(jié)點n是否可以擴展，如果不可以擴展則轉(zhuǎn)向第2步，否則繼續(xù)n6 對節(jié)點n進行擴展，并對它所有的后繼節(jié)點計算估價函數(shù)f(x)的值，為每個后繼節(jié)點設(shè)置指向n的指針。n7把所有的后繼節(jié)點送入到open表中，然后對open表中所有的節(jié)點按照估價值從小到達進行排序。n8 轉(zhuǎn)向第

29、2步全局最佳優(yōu)先搜索n全局最佳優(yōu)先搜索實際上是對寬度優(yōu)先搜索和代價樹寬度優(yōu)先搜索的一個擴展，而寬度優(yōu)先搜索和代價樹寬度優(yōu)先搜索可以認為是它的一個特例。全局最佳優(yōu)先搜索n例題：n用全局最佳優(yōu)先搜索方法求解八數(shù)碼難題，假設(shè)八數(shù)碼難題的初始狀態(tài)和目標狀態(tài)分別如下所示，請用全局最佳優(yōu)先搜索算法來求解從S0到Sg的轉(zhuǎn)換路徑。最佳圖搜索法n在啟發(fā)式搜索中，估價函數(shù)的定義是非常重要的，如果定義的不好，則上述的搜索算法不一定能找到最優(yōu)解，即便找到解，也不一定是最優(yōu)解。所以必須要討論如何對估價函數(shù)進行限制和定義。最佳圖搜索法n良好的解n我們一般用啟發(fā)能力的強弱來比較不同的搜索方法的效果。n在大多數(shù)實際問題中，讓

30、人感興趣的是路徑耗散值和求解路經(jīng)所需搜索的耗散值兩者的組合最小。最佳圖搜索法n良好的解n更為一般的情況下是考慮搜索方法對于所有可能預(yù)見的問題，其平均的組合耗散值最小。n啟發(fā)式度量只能根據(jù)使用方法的實際經(jīng)驗作出判斷，并沒有必要去追求嚴格的最優(yōu)結(jié)果。A算法n概述n啟發(fā)式搜索算法A，一般簡稱為A算法n算法思想n定義一個評價函數(shù)f，對當(dāng)前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點進行擴展。A算法n評價函數(shù)n形式：f(n)=g(n)+h(n)n其中n是要被評價的節(jié)點，n那么f(n)、g(n)和h(n)都表示什么哪？為此我們先看一下下面的幾個函數(shù)的含義。A算法n解釋：ng*(n):從初始節(jié)點S0到節(jié)點n之

31、間的最小代價路徑的實際代價nh*(n):從節(jié)點n到目標節(jié)點Sg的最小代價路徑的代價nf*(n)=g*(n)+h*(n)nf*(n):表示節(jié)點S0到節(jié)點n的一條最佳路徑的實際代價加上從節(jié)點n到目標節(jié)點的一條最佳路徑的代價之和。A算法nf(n),g(n)和h(n)則分別是對上面的三個函數(shù)的估計值，是一種預(yù)測。nA算法就是按照這種預(yù)測，來達到有效搜索的目的。A算法n啟發(fā)式搜索算法An1 把初始節(jié)點S0放入open表中，令f(S0)=0n2 如果open表為空，則問題無解，退出。n3 把open表中選取第一個節(jié)點（節(jié)點n）從open表中移到closed表中。n4 考察節(jié)點n是否為目標節(jié)點，若是則求得問題的解，并退出；否則繼續(xù).n5如果節(jié)點n可擴展，則轉(zhuǎn)6，否則轉(zhuǎn)2A算法n6 擴展節(jié)點n，