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

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

2、得問(wèn)題獲得解決的推理路線的過(guò)程n搜索的兩層含義n要找到從初始事實(shí)到問(wèn)題最終答案的一條推理路線n找到的這條路線是時(shí)間和空間復(fù)雜度最小的求解路線搜索的種類n搜索可以分為盲目搜索和啟發(fā)式搜索兩種n盲目搜索n又稱為無(wú)信息搜索。也就是在搜索的過(guò)程中只按預(yù)先的搜索控制策略進(jìn)行搜索，而沒(méi)有任何中間信息來(lái)改變這些控制策略n啟發(fā)式搜索n稱為有信息搜索。它是指在問(wèn)題搜索過(guò)程中，根據(jù)問(wèn)題本身的特征或者搜索過(guò)程中產(chǎn)生出來(lái)的一些信息來(lái)不斷地改變或者調(diào)整搜索方向，使搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解，并找到最優(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動(dòng)態(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ī)則給出一個(gè)固定的排序；n在搜索時(shí)，對(duì)當(dāng)前狀態(tài)（搜索開(kāi)始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測(cè)每一條規(guī)則；n在當(dāng)前狀態(tài)未使用過(guò)的規(guī)則中找到第一條可觸發(fā)規(guī)則，被應(yīng)用于當(dāng)前狀態(tài)；n得到的新?tīng)顟B(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索；n如果當(dāng)前狀態(tài)無(wú)規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過(guò)仍未找到問(wèn)題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前狀態(tài)。n重復(fù)以上搜索，直到找到問(wèn)題的解，或者試探了所有可能后仍找不到問(wèn)題的解為止?；厮菟阉鱪舉例說(shuō)明：四皇后問(wèn)題n在一個(gè)44

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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