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

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

2、解方法。由于絕大多數(shù)需要人工智能方法求解的問題缺乏直接求解的方法，因此，智能方法求解的問題缺乏直接求解的方法，因此，搜索為一種求解問題的一般方法。搜索為一種求解問題的一般方法。 下面首先討論搜索的基本概念，然后著重介紹狀下面首先討論搜索的基本概念，然后著重介紹狀態(tài)空間知識表示和搜索策略，主要有回溯策略、態(tài)空間知識表示和搜索策略，主要有回溯策略、寬度優(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)空間知識表示方法狀態(tài)空間知識表示方法5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略5.5 與與/或或圖搜索策略圖搜索策略55.1 搜索的概念 問題求解：問題的表示。 求解方法。問題求解的基本方法：搜索法、歸約法、歸結(jié)法、推理法及產(chǎn)生式等。65.1.1 搜索的基本問題與主要過程 搜索中需要解決的基本問題搜索中需要解決的基本問題：（1）是否一定能找到一個解。（2）找到的解是否是最佳

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

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

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

7、態(tài)空間表示法狀態(tài)空間狀態(tài)空間：利用狀態(tài)變量和操作符號，表示系統(tǒng)或問題的有關(guān)知識的符號體系，狀態(tài)空間是一個四元組： ),(0GSOS ：狀態(tài)集合。 ：操作算子的集合。 ：包含問題的初始狀態(tài)是 的非空子集。 ：若干具體狀態(tài)或滿足某些性質(zhì)的路徑信息描述。O0SGSS145.2.1 狀態(tài)空間表示法求解路徑求解路徑：從 結(jié)點到 結(jié)點的路徑。 0SGGSSSkOOOO321210kOO,1：狀態(tài)空間的一個解。 狀態(tài)空間的一個解狀態(tài)空間的一個解：一個有限的操作算子序列。15例例 八數(shù)碼問題的狀態(tài)空間八數(shù)碼問題的狀態(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 例例 旅行商問題旅行商問題（traveling salesman problem, TSP）或郵遞員路徑問題?；蜞]遞員路徑問題。 5.2.2 狀態(tài)空間的圖描述（家）（單位：km）可能路徑：費用為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 費用 : 費用 : 費用 : 費用: 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)空間知識表示方法狀態(tài)空間知識表示方法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ā)，不停地、試探性地尋找路徑，直到它到達目的或“不可解結(jié)點”，即“死胡同”為止。若它遇到不可解結(jié)點就回溯到路徑中最近的父結(jié)點上，查看該結(jié)點是否還有其他的子結(jié)點未被擴展。若有，則沿這些子結(jié)點繼續(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)還未被搜索到，即未被生成擴展 。(3) NSS（no solvable states）表）表：不可解狀態(tài)集，列出了找不到解題路徑的狀態(tài)。如果在搜索中擴展出的狀態(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）來避免算法重新搜索 無解的路徑。 （3）在PS 表中記錄當(dāng)前搜索路徑的狀態(tài)，當(dāng)滿足目的時可 以將它作為結(jié)果返回。 （4）為避免陷入死循環(huán)必須對新生成的子狀態(tài)進行檢查， 看它是否在該三張表中 。265.3.2 寬度優(yōu)先搜索策略open表（NPS表）：已經(jīng)生成出來但其子狀態(tài)未被搜索的狀態(tài)。closed表（ PS表和NSS表的合并）：記錄了已被生成擴展過的狀態(tài)。 0S12345678910寬度優(yōu)先搜索法中狀態(tài)的搜索次序?qū)挾葍?yōu)先搜索法中狀態(tài)的搜索次序27例例3 通過搬動積木塊，希望從初始狀態(tài)達到一個目的狀態(tài)，即三塊積木堆疊在一起。 5.3.2 寬度優(yōu)先搜索策略

13、BCAABC(a) 初始狀態(tài)(b) 目的狀態(tài) 積木問題積木問題28操作算子為MOVE（X，Y）：把積木X搬到Y(jié)（積木或桌面）上面。5.3.2 寬度優(yōu)先搜索策略MOVE（A，Table）：“搬動積木A到桌面上”。 操作算子可運用的先決條件：（1）被搬動積木的頂部必須為空。（2）如果 Y 是積木，則積木 Y 的頂部也必須為空。（3）同一狀態(tài)下，運用操作算子的次數(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沒有后裔，失敗退出 積木問題的寬度優(yōu)先搜索樹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)搜索到某一個狀態(tài)時，它所有的子狀態(tài)以及子狀態(tài)的后裔狀態(tài)都必須先于該狀態(tài)的兄弟狀態(tài)被搜索。 為了保證找到解，應(yīng)選擇合適的深度限制值，或采取不斷加大深度限制值的辦法，反復(fù)搜索，直到找到解。 5.3.3 深度優(yōu)先搜索策略32深度優(yōu)先搜索并不能保證第一次搜索到的某個狀態(tài)

15、時的路徑是到這個狀態(tài)的最短路徑。 對任何狀態(tài)而言，以后的搜索有可能找到另一條通向它的路徑。如果路徑的長度對解題很關(guān)鍵的話，當(dāng)算法多次搜索到同一個狀態(tài)時，它應(yīng)該保留最短路徑。 5.3.3 深度優(yōu)先搜索策略33例例 卒子穿陣問題卒子穿陣問題，要求一卒子從頂部通過下圖所示的陣列到達底部。卒子行進中不可進入到代表敵兵駐守的區(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)先搜索樹35第5章 搜索求解策略5.1 搜索的概念搜索的概念5.2 狀態(tài)空間知識表示方法狀態(tài)空間知識表示方法5.3 盲目的圖搜索策略盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略啟發(fā)式圖搜索策略 5.5 與與/或或圖搜索策略圖搜索策略365.4 啟發(fā)式圖搜索策略5.4.1 啟發(fā)式策略啟發(fā)式策略5.4.2 啟發(fā)信息和估價函數(shù)啟發(fā)信息和估價函數(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)空間中選擇最有希望到達問題解的路徑。啟發(fā)式策略啟發(fā)式策略：利用與問題有關(guān)的啟發(fā)信息進行搜索。385.4.1 啟發(fā)式策略運用啟發(fā)式策略的兩種基本情況運用啟發(fā)式策略的兩種基本情況： （1）一個問題由于在問題陳述和數(shù)據(jù)獲取方面固有 的模糊性，可能會使它沒有一個確定的解。 （2）雖然一個問題可能有確定解，但是其狀態(tài)空間 特別大，搜索中生成擴展的狀態(tài)數(shù)會隨著搜索 的深度呈指數(shù)級增長。39 例例 一字棋一字棋。在九宮棋盤上，從空棋盤開始，雙方輪流在棋盤上擺各自的棋子 或 （每次一枚），誰先取得三子一線（一行、一列或一條對角線）的結(jié)果就取勝。 5.4.1 啟發(fā)式策略

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

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

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

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

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

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

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

26、子狀態(tài)。如果某個子狀態(tài)已在態(tài)。如果某個子狀態(tài)已在open表（或表（或closed表）中出現(xiàn)過，表）中出現(xiàn)過，即該狀態(tài)再一次被發(fā)現(xiàn)時，則通過刷新它的祖先狀態(tài)的歷即該狀態(tài)再一次被發(fā)現(xiàn)時，則通過刷新它的祖先狀態(tài)的歷史記錄，使算法極有可能找到到達目的狀態(tài)的更短的路徑史記錄，使算法極有可能找到到達目的狀態(tài)的更短的路徑接著，接著，A搜索算法搜索算法open表中每個狀態(tài)的估價函數(shù)值，按照表中每個狀態(tài)的估價函數(shù)值，按照值的大小重新排序，將值最小的狀態(tài)放在表頭，使其第一值的大小重新排序，將值最小的狀態(tài)放在表頭，使其第一個被擴展。個被擴展。 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ù)碼問題的搜索樹，其估價函數(shù)定義為 ：狀態(tài)的深度，每步為單位代價。 ：以“不在位”的將牌數(shù)作為啟發(fā)信息的度量。)(nd)()()(nwndnf)(nw ：為狀態(tài) 到目的狀態(tài)的最優(yōu)路徑的代價。 ：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如果某一問題有解，那么利用A*搜索算法對該問題進行搜索則一定能搜索到解，并且一定能搜索到最優(yōu)的解而結(jié)束。上例中的八數(shù)碼A搜索樹也是A*搜索樹，所得的解路（s，B，E，I，K，L）為最優(yōu)解路，其步數(shù)為狀態(tài)L（5）上所標(biāo)注的5 。5.4.4 A*搜索算法及其特性分析561. 可采納性 當(dāng)一個搜索算法在最短路徑存在時能保證找到它，就稱它是可采納的。2. 單調(diào)性 搜索算法的單調(diào)性：在整個搜索