第5章 搜索求解策略(AI應(yīng)用3版)

1、Artificial Intelligence Principles and Applications 第第 5 章章 搜索求解策略搜索求解策略教材：教材： 王萬(wàn)良王萬(wàn)良人工智能及其應(yīng)用人工智能及其應(yīng)用（第（第3版）版） 高等教育出版社，高等教育出版社，2016. 22第5章 搜索求解策略 在求解一個(gè)問(wèn)題時(shí)，涉及到兩個(gè)方面：一是該問(wèn)在求解一個(gè)問(wèn)題時(shí)，涉及到兩個(gè)方面：一是該問(wèn)題的表示，如果一個(gè)問(wèn)題找不到一個(gè)合適的表示題的表示，如果一個(gè)問(wèn)題找不到一個(gè)合適的表示方法，就談不上對(duì)它求解。另一方面則是選擇一方法，就談不上對(duì)它求解。另一方面則是選擇一種相對(duì)合適的求解方法。由于絕大多數(shù)需要人工種相對(duì)合適的求

2、解方法。由于絕大多數(shù)需要人工智能方法求解的問(wèn)題缺乏直接求解的方法，因此，智能方法求解的問(wèn)題缺乏直接求解的方法，因此，搜索為一種求解問(wèn)題的一般方法。搜索為一種求解問(wèn)題的一般方法。 下面首先討論搜索的基本概念，然后著重介紹狀下面首先討論搜索的基本概念，然后著重介紹狀態(tài)空間知識(shí)表示和搜索策略，主要有回溯策略、態(tài)空間知識(shí)表示和搜索策略，主要有回溯策略、寬度優(yōu)先搜索、深度優(yōu)先搜索等盲目的圖搜索策寬度優(yōu)先搜索、深度優(yōu)先搜索等盲目的圖搜索策略，以及略，以及A及及A*搜索算法等啟發(fā)式圖搜索策略。搜索算法等啟發(fā)式圖搜索策略。3第5章 搜索求解策略5.1 搜索的概念搜索的概念5.2 狀態(tài)空間的搜索策略狀態(tài)空間的搜

3、索策略5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略5.5 與與/或或圖搜索策略圖搜索策略4第5章 搜索求解策略5.1 搜索的概念搜索的概念5.2 狀態(tài)空間知識(shí)表示方法狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略5.5 與與/或或圖搜索策略圖搜索策略55.1 搜索的概念 問(wèn)題求解：?jiǎn)栴}的表示。 求解方法。問(wèn)題求解的基本方法：搜索法、歸約法、歸結(jié)法、推理法及產(chǎn)生式等。65.1.1 搜索的基本問(wèn)題與主要過(guò)程 搜索中需要解決的基本問(wèn)題搜索中需要解決的基本問(wèn)題：（1）是否一定能找到一個(gè)解。（2）找到的解是否是最佳

4、解。（3）時(shí)間與空間復(fù)雜性如何。（4）是否終止運(yùn)行或是否會(huì)陷入一個(gè)死循環(huán)。75.1.1 搜索的基本問(wèn)題與主要過(guò)程搜索的主要過(guò)程搜索的主要過(guò)程：(1) 從初始或目的狀態(tài)出發(fā)，并將它作為當(dāng)前狀態(tài)。(2) 掃描操作算子集，將適用當(dāng)前狀態(tài)的一些操作算子作用于當(dāng)前狀態(tài)而得到新的狀態(tài)，并建立指向其父結(jié)點(diǎn)的指針 。(3) 檢查所生成的新?tīng)顟B(tài)是否滿足結(jié)束狀態(tài)，如果滿足，則得到問(wèn)題的一個(gè)解，并可沿著有關(guān)指針從結(jié)束狀態(tài)反向到達(dá)開(kāi)始狀態(tài)，給出一解答路徑；否則，將新?tīng)顟B(tài)作為當(dāng)前狀態(tài)，返回第(2)步再進(jìn)行搜索。 85.1.2 搜索策略1. 搜索方向搜索方向： (1) 數(shù)據(jù)驅(qū)動(dòng)數(shù)據(jù)驅(qū)動(dòng)：從初始狀態(tài)出發(fā)的正向搜索。 正向搜

5、索正向搜索從問(wèn)題給出的條件出發(fā)。逆向搜索逆向搜索：從想達(dá)到的目的入手，看哪些操作算子能產(chǎn)生該目的以及應(yīng)用這些操作算子產(chǎn)生目的時(shí)需要哪些條件。 (2) 目的驅(qū)動(dòng)目的驅(qū)動(dòng)：從目的狀態(tài)出發(fā)的逆向搜索。雙向搜索：從開(kāi)始狀態(tài)出發(fā)作正向搜索，同時(shí)又從目的狀態(tài)出發(fā)作逆向搜索，直到兩條路徑在中間的某處匯合為止。(3) 雙向搜索95.1.2 搜索策略2. 盲目搜索與啟發(fā)式搜索盲目搜索與啟發(fā)式搜索:（1）盲目搜索）盲目搜索：在不具有對(duì)特定問(wèn)題的任何有關(guān)信息的條件下，按固定的步驟（依次或隨機(jī)調(diào)用操作算子）進(jìn)行的搜索。 （2）啟發(fā)式搜索）啟發(fā)式搜索：考慮特定問(wèn)題領(lǐng)域可應(yīng)用的知識(shí)，動(dòng)態(tài)地確定調(diào)用操作算子的步驟，優(yōu)先選擇

6、較適合的操作算子，盡量減少不必要的搜索，以求盡快地到達(dá)結(jié)束狀態(tài)。10第5章 搜索求解策略5.1 搜索的概念搜索的概念5.2 狀態(tài)空間知識(shí)表示方法狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略115.2 狀態(tài)空間知識(shí)表示方法5.2.1 狀態(tài)空間表示法狀態(tài)空間表示法5.2.2 狀態(tài)空間的圖描述狀態(tài)空間的圖描述125.2.1 狀態(tài)空間表示法狀態(tài)狀態(tài)：表示系統(tǒng)狀態(tài)、事實(shí)等敘述型知識(shí)的一組變量或數(shù)組：,21nqqqQ,21mfffF 操作操作：表示引起狀態(tài)變化的過(guò)程型知識(shí)的一組關(guān) 系或函數(shù)：T135.2.1 狀

7、態(tài)空間表示法狀態(tài)空間狀態(tài)空間：利用狀態(tài)變量和操作符號(hào)，表示系統(tǒng)或問(wèn)題的有關(guān)知識(shí)的符號(hào)體系，狀態(tài)空間是一個(gè)四元組： ),(0GSOS ：狀態(tài)集合。 ：操作算子的集合。 ：包含問(wèn)題的初始狀態(tài)是 的非空子集。 ：若干具體狀態(tài)或滿足某些性質(zhì)的路徑信息描述。O0SGSS145.2.1 狀態(tài)空間表示法求解路徑求解路徑：從 結(jié)點(diǎn)到 結(jié)點(diǎn)的路徑。 0SGGSSSkOOOO321210kOO,1：狀態(tài)空間的一個(gè)解。 狀態(tài)空間的一個(gè)解狀態(tài)空間的一個(gè)解：一個(gè)有限的操作算子序列。15例例 八數(shù)碼問(wèn)題的狀態(tài)空間八數(shù)碼問(wèn)題的狀態(tài)空間。 5.2.1 狀態(tài)空間表示法狀態(tài)集 ：所有擺法S操作算子：將空格向上移Up將空格向左移L

8、eft將空格向下移Down將空格向右移Right165.2.2 狀態(tài)空間的圖描述八數(shù)碼八數(shù)碼狀態(tài)空間圖狀態(tài)空間圖 175.2.2 狀態(tài)空間的圖描述（狀態(tài)）（操作算子）狀態(tài)空間的有向圖描述狀態(tài)空間的有向圖描述18 例例 旅行商問(wèn)題旅行商問(wèn)題（traveling salesman problem, TSP）或郵遞員路徑問(wèn)題?；蜞]遞員路徑問(wèn)題。 5.2.2 狀態(tài)空間的圖描述（家）（單位：km）可能路徑：費(fèi)用為375的路徑（A，B，C，D，E，A） 195.2.2 狀態(tài)空間的圖描述 旅行推銷員狀態(tài)空間圖（部分） ABCDEA 375 A A A A B B C C C C D D D D A E E

9、E E E E E D 路徑: 路徑: 路徑 : 路徑: ABCEDA ABDCE ABDECA 費(fèi)用 : 費(fèi)用 : 費(fèi)用 : 費(fèi)用: 425 525 475 525 475 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425 . . . . . . . 20第5章 搜索求解策略5.1 搜索的概念搜索的概念5.2 狀態(tài)空間知識(shí)表示方法狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略215.3 盲目的

10、圖搜索策略5.3.1 回溯策略回溯策略5.3.2 寬度優(yōu)先搜索策略寬度優(yōu)先搜索策略5.3.3 深度優(yōu)先搜索策略深度優(yōu)先搜索策略225.3.1 回溯策略 帶回溯策略的搜索帶回溯策略的搜索： 從初始狀態(tài)出發(fā)，不停地、試探性地尋找路徑，直到它到達(dá)目的或“不可解結(jié)點(diǎn)”，即“死胡同”為止。若它遇到不可解結(jié)點(diǎn)就回溯到路徑中最近的父結(jié)點(diǎn)上，查看該結(jié)點(diǎn)是否還有其他的子結(jié)點(diǎn)未被擴(kuò)展。若有，則沿這些子結(jié)點(diǎn)繼續(xù)搜索；如果找到目標(biāo)，就成功退出搜索，返回解題路徑。235.3.1 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C回溯搜索示意圖回溯搜索示意圖245.3.1 回溯策略回溯搜索的算法回溯

11、搜索的算法(1) PS（path states）表）表：保存當(dāng)前搜索路徑上的狀態(tài)。如果找到了目的，PS就是解路徑上的狀態(tài)有序集。 (2) NPS（new path states）表）表：新的路徑狀態(tài)表。它包含了等待搜索的狀態(tài)，其后裔狀態(tài)還未被搜索到，即未被生成擴(kuò)展 。(3) NSS（no solvable states）表）表：不可解狀態(tài)集，列出了找不到解題路徑的狀態(tài)。如果在搜索中擴(kuò)展出的狀態(tài)是它的元素，則可立即將之排除，不必沿該狀態(tài)繼續(xù)搜索。 255.3.1 回溯策略圖搜索算法（深度優(yōu)先、寬度優(yōu)先、最好優(yōu)先搜索等）的回溯思想：（1）用未處理狀態(tài)表（NPS）使算法能返回（回溯）到其 中任一狀態(tài)

12、。 （2）用一張“死胡同”狀態(tài)表（NSS）來(lái)避免算法重新搜索 無(wú)解的路徑。 （3）在PS 表中記錄當(dāng)前搜索路徑的狀態(tài)，當(dāng)滿足目的時(shí)可 以將它作為結(jié)果返回。 （4）為避免陷入死循環(huán)必須對(duì)新生成的子狀態(tài)進(jìn)行檢查， 看它是否在該三張表中 。265.3.2 寬度優(yōu)先搜索策略open表（NPS表）：已經(jīng)生成出來(lái)但其子狀態(tài)未被搜索的狀態(tài)。closed表（ PS表和NSS表的合并）：記錄了已被生成擴(kuò)展過(guò)的狀態(tài)。 0S12345678910寬度優(yōu)先搜索法中狀態(tài)的搜索次序?qū)挾葍?yōu)先搜索法中狀態(tài)的搜索次序27例例3 通過(guò)搬動(dòng)積木塊，希望從初始狀態(tài)達(dá)到一個(gè)目的狀態(tài)，即三塊積木堆疊在一起。 5.3.2 寬度優(yōu)先搜索策略

13、BCAABC(a) 初始狀態(tài)(b) 目的狀態(tài) 積木問(wèn)題積木問(wèn)題28操作算子為MOVE（X，Y）：把積木X搬到Y(jié)（積木或桌面）上面。5.3.2 寬度優(yōu)先搜索策略MOVE（A，Table）：“搬動(dòng)積木A到桌面上”。 操作算子可運(yùn)用的先決條件：（1）被搬動(dòng)積木的頂部必須為空。（2）如果 Y 是積木，則積木 Y 的頂部也必須為空。（3）同一狀態(tài)下，運(yùn)用操作算子的次數(shù)不得多于一次。29ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(C,A)MOVE(A,C)MOVE(B,A)MOVE(B,C) MOVE(C,A)MOVE(C,B) MOVE(C,B)

14、MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S沒(méi)有后裔，失敗退出 積木問(wèn)題的寬度優(yōu)先搜索樹(shù)5.3.2 寬度優(yōu)先搜索策略305.3.3 深度優(yōu)先搜索策略0S12345678910111213KK 深度優(yōu)先搜索法中狀態(tài)的搜索次序0S12345678910111213KK深度優(yōu)先搜索法中狀態(tài)的搜索次序31在深度優(yōu)先搜索中，當(dāng)搜索到某一個(gè)狀態(tài)時(shí)，它所有的子狀態(tài)以及子狀態(tài)的后裔狀態(tài)都必須先于該狀態(tài)的兄弟狀態(tài)被搜索。 為了保證找到解，應(yīng)選擇合適的深度限制值，或采取不斷加大深度限制值的辦法，反復(fù)搜索，直到找到解。 5.3.3 深度優(yōu)先搜索策略32深度優(yōu)先搜索并不能保證第一次搜索到的某個(gè)狀態(tài)

15、時(shí)的路徑是到這個(gè)狀態(tài)的最短路徑。 對(duì)任何狀態(tài)而言，以后的搜索有可能找到另一條通向它的路徑。如果路徑的長(zhǎng)度對(duì)解題很關(guān)鍵的話，當(dāng)算法多次搜索到同一個(gè)狀態(tài)時(shí)，它應(yīng)該保留最短路徑。 5.3.3 深度優(yōu)先搜索策略33例例 卒子穿陣問(wèn)題卒子穿陣問(wèn)題，要求一卒子從頂部通過(guò)下圖所示的陣列到達(dá)底部。卒子行進(jìn)中不可進(jìn)入到代表敵兵駐守的區(qū)域（標(biāo)注1），并不準(zhǔn)后退。假定深度限制值為5。 5.3.3 深度優(yōu)先搜索策略000100100100000121342134行列圖5.10陣列圖000100100100000121342134行列圖5.10陣列圖 陣列圖陣列圖 345.3.3 深度優(yōu)先搜索策略open表：S17、S

16、18closed表：S0S16 0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死死死深度限制解 0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,

17、4(18S)4,1(死死死死深度限制解卒子穿陣的深度優(yōu)先搜索樹(shù)35第5章 搜索求解策略5.1 搜索的概念搜索的概念5.2 狀態(tài)空間知識(shí)表示方法狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略365.4 啟發(fā)式圖搜索策略5.4.1 啟發(fā)式策略啟發(fā)式策略5.4.2 啟發(fā)信息和估價(jià)函數(shù)啟發(fā)信息和估價(jià)函數(shù)5.4.3 A搜索算法搜索算法5.4.4 A*搜索算法及其特性分析搜索算法及其特性分析375.4.1 啟發(fā)式策略“啟發(fā)啟發(fā)”（heuristic）：關(guān)于發(fā)現(xiàn)和發(fā)明操作算子及搜索方法的研究。在狀態(tài)空間搜索中，啟發(fā)

18、式啟發(fā)式被定義成一系列操作算子，并能從狀態(tài)空間中選擇最有希望到達(dá)問(wèn)題解的路徑。啟發(fā)式策略啟發(fā)式策略：利用與問(wèn)題有關(guān)的啟發(fā)信息進(jìn)行搜索。385.4.1 啟發(fā)式策略運(yùn)用啟發(fā)式策略的兩種基本情況運(yùn)用啟發(fā)式策略的兩種基本情況： （1）一個(gè)問(wèn)題由于在問(wèn)題陳述和數(shù)據(jù)獲取方面固有 的模糊性，可能會(huì)使它沒(méi)有一個(gè)確定的解。 （2）雖然一個(gè)問(wèn)題可能有確定解，但是其狀態(tài)空間 特別大，搜索中生成擴(kuò)展的狀態(tài)數(shù)會(huì)隨著搜索 的深度呈指數(shù)級(jí)增長(zhǎng)。39 例例 一字棋一字棋。在九宮棋盤(pán)上，從空棋盤(pán)開(kāi)始，雙方輪流在棋盤(pán)上擺各自的棋子 或 （每次一枚），誰(shuí)先取得三子一線（一行、一列或一條對(duì)角線）的結(jié)果就取勝。 5.4.1 啟發(fā)式策略

19、 和 能夠在棋盤(pán)中擺成的各種不同的棋局就是問(wèn)題空間中的不同狀態(tài)。 9個(gè)位置上擺放空， ， 有 39 種棋局。 可能的走法 ： 。1789405.4.1 啟發(fā)式策略贏的幾率贏的幾率贏的幾率圖5.12 啟發(fā)式策略的運(yùn)用贏的幾率贏的幾率贏的幾率圖5.12 啟發(fā)式策略的運(yùn)用 啟發(fā)式策略的運(yùn)用啟發(fā)式策略的運(yùn)用415.4.1 啟發(fā)式策略圖5.13啟發(fā)式搜索下縮減的狀態(tài)空間啟發(fā)式搜索下縮減的狀態(tài)空間啟發(fā)式搜索下縮減的狀態(tài)空間425.4.2 啟發(fā)信息和估價(jià)函數(shù)在具體求解中，能夠利用與該問(wèn)題有關(guān)的信息來(lái)簡(jiǎn)化搜索過(guò)程，稱此類信息為啟發(fā)信息啟發(fā)信息。啟發(fā)式搜索啟發(fā)式搜索：利用啟發(fā)信息的搜索過(guò)程。435.4.2 啟發(fā)

20、信息和估價(jià)函數(shù) 求解問(wèn)題中能利用的大多是非完備的啟發(fā)信息：（1）求解問(wèn)題系統(tǒng)不可能知道與實(shí)際問(wèn)題有關(guān)的全部信息，因而無(wú)法知道該問(wèn)題的全部狀態(tài)空間，也不可能用一套算法來(lái)求解所有的問(wèn)題。（2）有些問(wèn)題在理論上雖然存在著求解算法，但是在工程實(shí)踐中，這些算法不是效率太低，就是根本無(wú)法實(shí)現(xiàn)。一字棋：9！，西洋跳棋：1078，國(guó)際象棋：10120，圍棋：10761。假設(shè)每步可以搜索一個(gè)棋局，用極限并行速度（10-104年/步）來(lái)處理，搜索一遍國(guó)際象棋的全部棋局也得1016年即1億億年才可以算完！ 445.4.2 啟發(fā)信息和估價(jià)函數(shù)啟發(fā)信息的分類： （1）陳述性啟發(fā)信息 （2）過(guò)程性啟發(fā)信息 （3）控制性啟

21、發(fā)信息利用控制性的啟發(fā)信息的情況： （1）沒(méi)有任何控制性知識(shí)作為搜索的依據(jù)，因而搜索的每一步完全是隨意的。 （2）有充分的控制知識(shí)作為依據(jù)，因而搜索的每一步選擇都是正確的，但這是不現(xiàn)實(shí)的。455.4.2 啟發(fā)信息和估價(jià)函數(shù) 估價(jià)函數(shù)的任務(wù)就是估計(jì)待搜索結(jié)點(diǎn)的“有希望”程度，并依次給它們排定次序（在open表中）。 估價(jià)函數(shù) ：從初始結(jié)點(diǎn)經(jīng)過(guò) 結(jié)點(diǎn)到達(dá)目的 結(jié)點(diǎn)的路徑的最小代價(jià)估計(jì)值，其一般形式是)(nfn)()()(nhngnf 一般地，在 中， 的比重越大，越傾向于寬度優(yōu)先搜索方式，而 的比重越大，表示啟發(fā)性能越強(qiáng)。( )f n( )g n( )h n46 例例 八數(shù)碼的估價(jià)函數(shù)八數(shù)碼的估價(jià)

22、函數(shù)設(shè)計(jì)方法有多種，并且不同的估價(jià)函數(shù)對(duì)求解八數(shù)碼問(wèn)題有不同的影響。 最簡(jiǎn)單的估價(jià)函數(shù)：取一格局與目的格局相比，其位置不符的將牌數(shù)目。 較好的估價(jià)函數(shù)：各將牌移到目的位置所需移動(dòng)的距離的總和。 第三種估價(jià)函數(shù)：對(duì)每一對(duì)逆轉(zhuǎn)將牌乘以一個(gè)倍數(shù)。 第四種估價(jià)函數(shù)：克服了僅計(jì)算將牌逆轉(zhuǎn)數(shù)目策略的局限，將位置不符將牌數(shù)目的總和與3倍將牌逆轉(zhuǎn)數(shù)目相加。 5.4.2 啟發(fā)信息和估價(jià)函數(shù)475.4.3 A搜索算法啟發(fā)式圖搜索法的基本特點(diǎn)啟發(fā)式圖搜索法的基本特點(diǎn)：如何尋找并設(shè)計(jì)一個(gè)與問(wèn)題有關(guān)的 及構(gòu)出 ， 然后以 的大小來(lái)排列待擴(kuò)展?fàn)顟B(tài)的次序，每次選擇 值最小者進(jìn)行擴(kuò)展。)(nh)()()(nhngnf)(nf

23、)(nf open表：保留所有已生成而未擴(kuò)展的狀態(tài)。 closed表：記錄已擴(kuò)展過(guò)的狀態(tài)。 進(jìn)入open表的狀態(tài)是根據(jù)其估值的大小插入到表中合適的位置，每次從表中優(yōu)先取出啟發(fā)估價(jià)函數(shù)值最小的狀態(tài)加以擴(kuò)展。 48一般啟發(fā)式圖搜索算法（一般啟發(fā)式圖搜索算法（簡(jiǎn)記為簡(jiǎn)記為A）5.4.3 A搜索算法procedure heuristic_searchopen：=start；closed：= ；f(s)：=g(s)+h(s)；*初始化while open dobegin從open表中刪除第一個(gè)狀態(tài)，稱之為n；if n=目的狀態(tài)then return(success)；生成n的所有子狀態(tài)；if n沒(méi)有任何

24、子狀態(tài)then continue；for n的每個(gè)子狀態(tài)docase子狀態(tài)is not already on open表or closed表；begin計(jì)算該子狀態(tài)的估價(jià)函數(shù)值；將該子狀態(tài)加到open表中； end； 495.4.3 A搜索算法case子狀態(tài)is already on open表：if該子狀態(tài)是沿著一條比在open表已有的更短路徑而到達(dá)then 記錄更短路徑走向及其估價(jià)函數(shù)值；case子狀態(tài)is already on closed表：if該子狀態(tài)是沿著一條比在closed表已有的更短路徑而到達(dá)thenbegin將該子狀態(tài)從closed表移到open表中；記錄更短路徑走向及其估價(jià)

25、函數(shù)值；end；case end；將n放入closed表中；根據(jù)估價(jià)函數(shù)值，從小到大重新排列open表；end；*open表中結(jié)點(diǎn)已耗盡return(failure)；end.505.4.3 A搜索算法每次重復(fù)時(shí)，每次重復(fù)時(shí)，A搜索算法從搜索算法從open表中取出第一個(gè)狀態(tài)，如表中取出第一個(gè)狀態(tài)，如果該狀態(tài)滿足目的條件，則算法返回到該狀態(tài)的搜索路徑。果該狀態(tài)滿足目的條件，則算法返回到該狀態(tài)的搜索路徑。如果如果open表的第一個(gè)狀態(tài)不是目的狀態(tài)，則算法利用與之表的第一個(gè)狀態(tài)不是目的狀態(tài)，則算法利用與之相匹配的一系列操作算子進(jìn)行相應(yīng)的操作來(lái)產(chǎn)生它的子狀相匹配的一系列操作算子進(jìn)行相應(yīng)的操作來(lái)產(chǎn)生它的

26、子狀態(tài)。如果某個(gè)子狀態(tài)已在態(tài)。如果某個(gè)子狀態(tài)已在open表（或表（或closed表）中出現(xiàn)過(guò)，表）中出現(xiàn)過(guò)，即該狀態(tài)再一次被發(fā)現(xiàn)時(shí)，則通過(guò)刷新它的祖先狀態(tài)的歷即該狀態(tài)再一次被發(fā)現(xiàn)時(shí)，則通過(guò)刷新它的祖先狀態(tài)的歷史記錄，使算法極有可能找到到達(dá)目的狀態(tài)的更短的路徑史記錄，使算法極有可能找到到達(dá)目的狀態(tài)的更短的路徑接著，接著，A搜索算法搜索算法open表中每個(gè)狀態(tài)的估價(jià)函數(shù)值，按照表中每個(gè)狀態(tài)的估價(jià)函數(shù)值，按照值的大小重新排序，將值最小的狀態(tài)放在表頭，使其第一值的大小重新排序，將值最小的狀態(tài)放在表頭，使其第一個(gè)被擴(kuò)展。個(gè)被擴(kuò)展。 51A(-5)B(-3)C(-4)D(-6)E(-5)F(-3)G(-4

27、)H(-3)IJKL(-5)M(-5) NO(-2)P(-3)QRSTU(-3)5.4.3 A搜索算法525.4.3 A搜索算法例例 利用A搜索算法求解八數(shù)碼問(wèn)題的搜索樹(shù)，其估價(jià)函數(shù)定義為 ：狀態(tài)的深度，每步為單位代價(jià)。 ：以“不在位”的將牌數(shù)作為啟發(fā)信息的度量。)(nd)()()(nwndnf)(nw ：為狀態(tài) 到目的狀態(tài)的最優(yōu)路徑的代價(jià)。 ：A搜索算法 A*搜索算法。 ( )( )*( )w nh nhnn)(*nh535.4.3 A搜索算法初始s ( 4)2 8 31 6 47 5B( 4)2 8 31 47 6 5C( 4)2 8 31 6 47 5A( 4)2 8 31 6 47 5

28、D( 5)2 8 31 47 6 5E( 5)2 31 8 47 6 5F( 6)2 8 31 47 6 5J ( 7)2 31 8 47 6 5I ( 5)2 31 8 47 6 5H( 7)2 8 37 1 46 5G( 6)8 32 1 47 6 5K( 5)1 2 38 47 6 5M( 7)1 2 37 8 46 5L( 5)1 2 38 47 6 5目的54open表和closed表內(nèi)狀態(tài)排列的變化情況 5.4.3 A搜索算法55如果某一問(wèn)題有解，那么利用A*搜索算法對(duì)該問(wèn)題進(jìn)行搜索則一定能搜索到解，并且一定能搜索到最優(yōu)的解而結(jié)束。上例中的八數(shù)碼A搜索樹(shù)也是A*搜索樹(shù)，所得的解路（s，B，E，I，K，L）為最優(yōu)解路，其步數(shù)為狀態(tài)L（5）上所標(biāo)注的5 。5.4.4 A*搜索算法及其特性分析561. 可采納性 當(dāng)一個(gè)搜索算法在最短路徑存在時(shí)能保證找到它，就稱它是可采納的。2. 單調(diào)性 搜索算法的單調(diào)性：在整個(gè)搜索