【正文】 {{S0}， { P 01， P 10， P 11， P 02， P 20， Q01， Q 10， Q 11， Q 02， Q 20}， {S31}}。 2023/4/2 人工智能 25 例 （ 6） S0 (3,3,1) S18 (3,1,0) p02 q02 S17 (3,2,0) p01 q01 S21 (2,2,0) p11 q11 S1 (3,2,1) q01 p01 p10 q10 S19 (3,0,0) q02 p02 S2 (3,1,1) q01 p01 S26 (1,1,0) q20 p20 S31 (0,0,0) q11 p11 S14 (0,1,1) p01 q01 p02 q02 S10 (1,1,1) p10 q10 S13 (0,2,1) q01 p01 S30 (0,1,0) p02 q02 S12 (0,3,1) p01 q01 S29 (0,2,0) p20 q20 S5 (2,2,1) q11 p11 ： 四條 S0到 S31長度相等的最短路徑，對應(yīng)的操作序列就是該問題的四個最優(yōu)解 2023/4/2 人工智能 26 隱式狀態(tài)空間圖 ?顯式狀態(tài)空間圖： 表示了問題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系，這種表示方式稱為 顯式狀態(tài)空間圖 ，或稱為 狀態(tài)空間圖的顯示表示 。 ?隱式狀態(tài)空間圖 ：利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換（操作）的知識定義的狀態(tài)空間圖。在計算機中僅存儲描述問題狀態(tài)及操作的有關(guān)知識，包括該問題的各狀態(tài)分量的取值情況、分量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài)，以及全部操作的條件和動作等。隱式狀態(tài)空間圖也稱為是 狀態(tài)空間圖的隱式表示或隱式圖 。 重排九宮問題的隱式圖描述為： （ 1）有關(guān)狀態(tài)的知識： 狀態(tài) S的定義： S＝ (X0， X1， X2， X3， X4 ， X5， X6 ， X7 ， X8) 其中， Xi?｛ 0， 1， 2， 3， 4， 5， 6， 7， 8｝， ，且 。 初始狀態(tài)： S0 ＝（ 0， 1， 2， 3， 5， 6， 4， 7， 8） 目標狀態(tài)： Sg ＝（ 0， 1， 2， 3， 4， 5， 6， 7， 8） ( a ) 初 始 狀 態(tài)( b ) 終 止 狀 態(tài) 1 2 3 8 5 7 4 6 1 2 3 8 4 7 6 5 X1 X2 X3 X8 X0 X4 X7 X6 X5 重排九宮問題的狀態(tài)表示 80 ??iiji j X X??時 ，例 （八數(shù)碼問題） 例 （ 2） （ 2）有關(guān)操作的知識（規(guī)則）： 0組規(guī)則 R1(X0=0 ) ? (X2=n ) ? X0 = n ? X2 =0； R2(X0=0 ) ? (X4=n ) ? X0 = n ? X4 =0； R3(X0=0 ) ? (X6=n ) ? X0 = n ? X6 =0； R4(X0=0 ) ? (X8=n ) ? X0 = n ? X8 =0； 1組規(guī)則 R5(X1=0 ) ? (X2=n ) ? X1 = n ? X2 =0； R6(X1=0 ) ? (X8=n ) ? X1 = n ? X8 =0； 8組規(guī)則 : R22(X8=0 ) ? (X1=n ) ? X8 = n ? X1 =0； R23(X8=0 ) ? (X0=n ) ? X8 = n ? X0=0； R24(X8=0 ) ? (X7=n ) ? X8 = n ? X7 =0； …… 例 （ 3） 八數(shù)碼的狀態(tài)圖可表示為 （ {S0}, {r1 , r2 ,? , r 24 }, {Sg}） 八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點和目標節(jié)點，其余節(jié)點需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為 隱式狀態(tài)圖 ，或者說 狀態(tài)圖 的 隱式表示 。 例 （ 4） （ 3）隱式圖搜索 初始狀態(tài) S＝（ 0， 1， 2， 3， 5， 6， 4， 7， 8 ）滿足條件 X0 =0，故可以使用第 0組的四條規(guī)則： 如果選擇規(guī)則 R1，則狀態(tài)轉(zhuǎn)換為： S1＝（ 2， 1， 0， 3， 5， 6， 4， 7，8) R 2R 4R 1R 3 1 2 3 8 5 7 4 6 1 3 8 2 5 7 4 6 1 2 3 8 5 7 4 6 1 2 3 8 4 5 7 6 1 2 3 8 8 5 7 4 62023/4/2 人工智能 31 例 旅行商問題 (TSP)(1) 設(shè)有 n個互相可直達的城市 ， 某推銷商準備從其中的 A城出發(fā) ， 周游各城市一遍 ， 最后又回到 A城 。 要求為該推銷商規(guī)劃一條最短的旅行路線 。 （ 1） 狀態(tài)描述 ：該問題的狀態(tài)為以 A打頭城市序列： ?=AA1… Ai… Aj… A’ 其中： A、 Ai、 Aj、 A’為城市名， 1?i、 j?n1， Aj?A， Ai?A； 1?|?|?n+1； 當(dāng) i ?j 時， Ai? Aj； 當(dāng)且僅當(dāng) |?|=n+1時 ， A’=A。 初始狀態(tài) ： ?=A， |?|=1 終止?fàn)顟B(tài) ： ?=AA1A2… A， |?|=n+1 例 旅行商問題 (TSP)(2) （ 2）操作描述 （狀態(tài)轉(zhuǎn)換規(guī)則）： 規(guī)則 1 ：如果 ?=AA1… Ai… Aj… ，且 |?|? n，但 A’??，則置?= ? A。即沒遍歷完時，在城市序列中添加一個沒有到過的城市。 規(guī)則 2 ： 如果 |?|= n，置 ?= ?A，即從當(dāng)前城市返回 A城。 （ 3）隱式圖搜索 對于有 A、 B、 C、 D四個 城市所組成的連通城市網(wǎng)， 初始狀態(tài)： ?=A， |?|=1，滿足規(guī)則 1 ， 則操作的結(jié)果為 ： ?=AB 、或 ?=AC、或 ?=AD， 繼續(xù)使用規(guī)則 1 ，直到生成包含四個城市的序列出現(xiàn)，再使用規(guī)則 2。 2023/4/2 人工智能 32 補充例 二階梵塔問題（ 1） 有三個桿，一號桿有 A、 B兩個金盤， A小于 B。要求將 A、B移至三號桿，每次只可移動一個盤子，任何時刻 B不能在 A上。 （ 1） 有關(guān)狀態(tài)的知識： 用二元組 （ SA， SB） 表示狀態(tài) ， SA表示 A所在桿號 ， SB表示B所在桿號 。 其中 : SA ,SB?{1,2,3} , 則 全部狀態(tài)如下： （ 1， 1） ， （ 1， 2） ， （ 1， 3） （ 2， 1） ， （ 2， 2） ， （ 2， 3） （ 3， 1） ， （ 3， 2） ， （ 3， 3） 初始狀態(tài)為 （ 1， 1） ， 終止?fàn)顟B(tài)為 ： （ 3， 3） 。 2023/4/2 人工智能 33 A B 1 2 3 S0：（ 1， 1） 1 2 3 S1：（ 1， 2） 1 2 3 S2：（ 1， 3） A A 1 2 3 S5：（ 2， 3） 1 2 3 S4：（ 2， 2） 1 2 3 S3：（ 2， 1） 1 2 3 S8：（ 3， 3） 1 2 3 S7：（ 3， 2） 1 2 3 S6：（ 3， 1） A A A A A B A B B B B B 補充例 二階梵塔問題（ 2） 2023/4/2 人工智能 34 （ 2）有關(guān)操作的知識（規(guī)則）： A（ i， j）表示金盤 A從第 i號桿移到 j號桿，B（ i， j）表示金盤 B從第 i號桿移到 j號桿，其中： i,j ?{1,2,3}，但 i ?j ，全部操作為： A（ 1， 2）， A（ 1， 3）， A（ 2， 1） A（ 2， 3）， A（ 3， 1）， A（ 3， 2） B（ 1， 2）， B（ 1， 3）， B（ 2， 1） B（ 2， 3）， B（ 3， 1）， B（ 3， 2） 分析每個操作的條件和動作，得到下表： 補充例 二階梵塔問題（ 3） 2023/4/2 人工智能 35 補充例 二階梵塔問題（ 4） 操作符 條件 動作 A（ 1， 2） SA=1 SA=2 A（ 1， 3） SA=1 SA=3 A（ 2， 1） SA=2 SA=1 A（ 2， 3） SA=2 SA=3 A（ 3， 1） SA=3 SA=1 A（ 3， 2） SA=3 SA=2 B（ 1， 2） SB=1， SA? 1,2 或 SA=3 SB=2 B（ 1， 3） SB=1， SA? 1,3 或 SA=2 SB=3 B（ 2， 1） SB=2， SA? 1,2 或 SA=3 SB=1 B（ 2， 3） SB=2， SA? 2,3 或 SA=1 SB=3 B（ 3， 1） SB=3， SA? 1,3 或 SA=2 SB=1 B（ 3， 2） SB=3， SA? 2,3 或 SA=1 SB=2 2023/4/2 人工智能 36 補充例 二階梵塔問題（ 5） （ 3）狀態(tài)空間圖 1,1 2,1 3,1 2,3 3,3 1,3 3,2 1,2 2,2 A(1,2) A(1,3) B(1,2) A(3,2) A(1,2) B(3,2) A(3,1) B(1,3) A(2,3) 2023/4/2 人工智能 37 狀態(tài)空間圖的盲目搜索 ?盲目搜索 :搜索時不參考與具體待求解問題相關(guān)的任何信息，只是按預(yù)先設(shè)定的順序逐個考察節(jié)點。盲目搜索與問題無關(guān)，具有通用性。 ?算法中使用的數(shù)據(jù)結(jié)構(gòu) : OPEN表 ： 專門登記已經(jīng)生成但還沒有考察的節(jié)點，即待考察節(jié)點。 CLOSED表： 用來記錄考察過的節(jié)點以及節(jié)點之間的關(guān)系，如每個節(jié)點指向父節(jié)點的編號（返回指針）。CLOSED表中存放的就是一定搜索策略下的搜索樹。 2023/4/2 人工智能 38 節(jié)點 父節(jié)點編號 編號 節(jié)點 父節(jié)點編號 OPEN表 CLOSED表 2023/4/2 人工智能 39 狀態(tài)空間圖的盲目搜索 廣度優(yōu)先搜索 深度優(yōu)先搜索 2023/4/2 人工智能 40 廣度優(yōu)先搜索（ 1） ? 廣度優(yōu)先搜索（ A?ed）基本思想： 廣度優(yōu)先搜索是嚴格按節(jié)點在樹中的出現(xiàn)位置 一層一 層向下的搜索過程。通過將 OPEN表設(shè)計為一個隊列來實現(xiàn)，將新生成的子節(jié)點放在 OPEN表的后面，保證先生成的節(jié)點先考察 。 ? 廣度優(yōu)先搜索算法： 步 1 把初始節(jié)點 S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，取 OPEN表中第一個節(jié)點 N放在 CLOSED表中；并冠以順序編號 n； 步 4 若節(jié)點 N為目標節(jié)點，則搜索成功。利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴展，轉(zhuǎn)步 2； 步 6 否則，擴展 N，將其所有子節(jié)點配上指向 N的返回指針放入 OPEN表的 尾部 ，轉(zhuǎn)步 2。 廣度優(yōu)先搜索（ 2） 2023/4/2 人工智能 42 例 1 2 3 8 5 7 4 6 1 1 2 3 8 5 6 7 4 8 1 3 8 2 5 7 4 6 10 1 2 3 8 4 5 7 6 7 1 2 3 8 4 5 7 6 6 1 3 8 2 5 7 4 6 11 1 2 3 8 4 5 7 6 2 1 2 3 8 5 7 4 6 3 1 2 3 8 4 5 7 6 4 1 2 3 7 8 5 4 6 12 2 3 1 8 5 7 4 6 13 1 2 3 8 4 7 6 5 14 1