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

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

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

4、枝法（Heuristic Pruning）,回溯搜索（Backtracking strategies）,回溯搜索策略是盲目搜索中的一種。思想為： 首先將規(guī)則給出一個(gè)固定的排序； 在搜索時(shí)，對(duì)當(dāng)前狀態(tài)（搜索開始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測(cè)每一條規(guī)則； 在當(dāng)前狀態(tài)未使用過(guò)的規(guī)則中找到第一條可觸發(fā)規(guī)則，被應(yīng)用于當(dāng)前狀態(tài)； 得到的新狀態(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索； 如果當(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)。 重復(fù)以上搜索，直到找到問(wèn)題的解，或者試探了所有可能后仍找不到問(wèn)題的解為止。,回溯搜索,舉例說(shuō)明

5、：四皇后問(wèn)題 在一個(gè)44的國(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ì),回溯搜索,搜索方法的實(shí)現(xiàn)遞歸實(shí)現(xiàn) 遞歸方法的特點(diǎn) 遞歸必須要有出口 遞歸公式中，每一次調(diào)用必須距出口更近一些,回溯搜索,回溯搜索,算法步驟Backtrack(DATA) 如果當(dāng)前狀態(tài)DATA為目標(biāo)狀態(tài)，則找到目標(biāo)。 該狀態(tài)不合法，則過(guò)程返回失敗信息 ，必須回溯。 計(jì)算DATA（當(dāng)前狀態(tài)）的可應(yīng)用規(guī)則集，依某種原則（任意排列或按啟發(fā)式準(zhǔn)則）

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

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

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

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

10、它從open表中移出，并放入closed表中，將此節(jié)點(diǎn)標(biāo)記為節(jié)點(diǎn)n。,狀態(tài)空間圖的搜索策略,5 考察節(jié)點(diǎn)n是 否為目標(biāo)節(jié)點(diǎn)，如果是，則問(wèn)題有解，并且成功退出。問(wèn)題的解既可從圖G中沿著指針從n到S0的這條路徑得到。 6 擴(kuò)展節(jié)點(diǎn)n生成一組不是n的祖先的后繼節(jié)點(diǎn)，并將它們記為集合M，將M中的這些節(jié)點(diǎn)作為n的后繼節(jié)點(diǎn)加入圖G中。,狀態(tài)空間圖的搜索策略,7 對(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ì)于那些先

11、前已經(jīng)在G中出現(xiàn)并且已在closed表中的那些M中的節(jié)點(diǎn)，確定是否需要修改通向它們后繼點(diǎn)的指針。 8 按照某一種方式或者某種策略重排open表中的節(jié)點(diǎn)的順序 9 轉(zhuǎn)到第（3）步。,狀態(tài)空間圖的搜索策略,解釋； 這里給出的是一個(gè)圖搜索的一般框架，不是一個(gè)具體的算法， 關(guān)鍵是算法的第8步，按不同的原則對(duì)open表進(jì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)，這樣就可能盡量少地生

12、成與問(wèn)題無(wú)關(guān)的狀態(tài)。,狀態(tài)空間圖的搜索策略,節(jié)點(diǎn)類型說(shuō)明,狀態(tài)空間圖的搜索策略,修改指針的說(shuō)明,狀態(tài)空間圖的搜索策略,狀態(tài)空間圖的搜索策略,狀態(tài)空間圖的搜索策略,寬度優(yōu)先搜索策略,寬度優(yōu)先 又稱為是廣度優(yōu)先； 是一種盲目的搜索策略。 它的基本思想是： 從初始節(jié)點(diǎn)開始，逐層對(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ò)展或者是搜索。 Open表的節(jié)點(diǎn)排隊(duì)準(zhǔn)則： 先進(jìn)入open表中，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。,寬度優(yōu)先搜索策略,算法：狀態(tài)空間圖的寬度優(yōu)先搜索算法 把初始節(jié)點(diǎn)S0放入到open表中 判斷open表是否

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

14、向父節(jié)點(diǎn)n的指針,算法實(shí)現(xiàn)過(guò)程,OPEN表,ClOSED表,SLF,寬度優(yōu)先搜索策略,寬度優(yōu)先搜索策略,例題：八數(shù)碼難題 設(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)先搜索,深度優(yōu)先 是一種盲目的搜索策略 深度優(yōu)先思想： 首先最先擴(kuò)展最先產(chǎn)生的節(jié)點(diǎn)，即從初始節(jié)點(diǎn)S0開始，在它的后繼節(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)

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

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

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

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

19、解，退出 3 把open表中的代價(jià)最小的節(jié)點(diǎn)，即排在最前端的節(jié)點(diǎn)（節(jié)點(diǎn)n）從open表中移到closed表中。 4 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是則求得問(wèn)題的解，并退出；否則繼續(xù)。,代價(jià)樹寬度優(yōu)先搜索,5 判斷節(jié)點(diǎn)n是否可以擴(kuò)展，如果不可以擴(kuò)展則轉(zhuǎn)向第2步，否則繼續(xù) 6 對(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) 7 為每一個(gè)后繼節(jié)點(diǎn)設(shè)置指向n的指針，然后根據(jù)節(jié)點(diǎn)的代價(jià)大小對(duì)open表中的所有節(jié)點(diǎn)進(jìn)行從小到大排序 8 轉(zhuǎn)向第2步,代價(jià)樹寬度優(yōu)先搜索,例題：推銷員最短路徑問(wèn)題 假設(shè)A,B,C,D,E是五個(gè)城市，推銷員

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

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

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

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

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

25、先搜索,算法概述 局部最佳優(yōu)先搜索算法有些類似于深度優(yōu)先搜索算法，但是由于使用了與問(wèn)題特征有關(guān)的估價(jià)函數(shù)來(lái)確定下一個(gè)帶擴(kuò)展節(jié)點(diǎn)，所以它是一種啟發(fā)是搜索算法。,局部最佳優(yōu)先搜索,算法思想 當(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) 由于他每次只是在后繼節(jié)點(diǎn)的范圍內(nèi)選擇一個(gè)要考察的點(diǎn)，范圍比較小，所以稱為局部最佳優(yōu)先搜索或者局部擇優(yōu)搜索,局部最佳優(yōu)先搜索,算法：局部最佳優(yōu)先搜索算法 1 把初始節(jié)點(diǎn)S0放入open表中，令f(S0)=0 2 如果open表為空，則問(wèn)題無(wú)解，退出。否則轉(zhuǎn)第三步。

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

27、節(jié)點(diǎn)的深度作為選擇標(biāo)準(zhǔn)，后生成的節(jié)點(diǎn)先考察 代價(jià)樹深度優(yōu)先搜索 各后繼節(jié)點(diǎn)到其前驅(qū)節(jié)點(diǎn)之間的代價(jià)作為選擇標(biāo)準(zhǔn)。,局部最佳優(yōu)先搜索,如果把層深度函數(shù)d(x)當(dāng)作估價(jià)函數(shù)f(x)，或者是把代價(jià)函數(shù)g(x)當(dāng)作估價(jià)函數(shù)f(x)，那么就可以把深度優(yōu)先搜索和代價(jià)樹深度優(yōu)先搜索看作是局部最佳優(yōu)先搜索的兩個(gè)特例。,全局最佳優(yōu)先搜索,算法概述 由信息的啟發(fā)式搜索，類似于寬度優(yōu)先搜索。 所不同的事，在確定下一個(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)先搜索,算法概述 正因?yàn)檫x擇的范圍是o

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

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

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

31、算法,解釋： g*(n):從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n之間的最小代價(jià)路徑的實(shí)際代價(jià) h*(n):從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的最小代價(jià)路徑的代價(jià) f*(n)=g*(n)+h*(n) f*(n):表示節(jié)點(diǎn)S0到節(jié)點(diǎn)n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和。,A算法,f(n),g(n)和h(n)則分別是對(duì)上面的三個(gè)函數(shù)的估計(jì)值，是一種預(yù)測(cè)。 A算法就是按照這種預(yù)測(cè)，來(lái)達(dá)到有效搜索的目的。,A算法,啟發(fā)式搜索算法A 1 把初始節(jié)點(diǎn)S0放入open表中，令f(S0)=0 2 如果open表為空，則問(wèn)題無(wú)解，退出。 3 把open表中選取第一個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)n）從open表中移到closed