【正文】 重排九宮問題的狀態(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é)點(diǎn)和目標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。 例 （ 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個互相可直達(dá)的城市 ， 某推銷商準(zhǔn)備從其中的 A城出發(fā) ， 周游各城市一遍 ， 最后又回到 A城 。 （ 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。即沒遍歷完時，在城市序列中添加一個沒有到過的城市。 （ 3）隱式圖搜索 對于有 A、 B、 C、 D四個 城市所組成的連通城市網(wǎng)， 初始狀態(tài)： ?=A， |?|=1，滿足規(guī)則 1 ， 則操作的結(jié)果為 ： ?=AB 、或 ?=AC、或 ?=AD， 繼續(xù)使用規(guī)則 1 ，直到生成包含四個城市的序列出現(xiàn)，再使用規(guī)則 2。要求將 A、B移至三號桿，每次只可移動一個盤子，任何時刻 B不能在 A上。 其中 : 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） 。盲目搜索與問題無關(guān)，具有通用性。 CLOSED表： 用來記錄考察過的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系，如每個節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號（返回指針）。 2023/4/2 人工智能 38 節(jié)點(diǎn) 父節(jié)點(diǎn)編號 編號 節(jié)點(diǎn) 父節(jié)點(diǎn)編號 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)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位置 一層一 層向下的搜索過程。 ? 廣度優(yōu)先搜索算法： 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，取 OPEN表中第一個節(jié)點(diǎn) N放在 CLOSED表中；并冠以順序編號 n； 步 4 若節(jié)點(diǎn) N為目標(biāo)節(jié)點(diǎn)，則搜索成功。 廣度優(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 2 3 4 5 8 7 6 15 1 2 8 5 3 7 4 6 17 1 3 5 8 2 7 4 6 18 8 1 3 2 5 7 4 6 19 1 2 3 7 8 5 4 6 20 2 3 1 8 5 7 4 6 21 1 2 8 4 3 7 6 5 22 1 2 3 8 5 7 4 6 5 1 2 3 8 4 7 6 5 23 八數(shù)碼廣度優(yōu)先搜索 1 2 8 5 3 7 4 6 9 16 1 2 3 8 5 6 7 4 2023/4/2 人工智能 43 廣度優(yōu)先搜索 廣度優(yōu)先搜索的特點(diǎn)： ?廣度優(yōu)先中 OPEN表 是一個 隊列 ， CLOSED表 是一個 順序表 ，表中各節(jié)點(diǎn)按順序編號，正被考察的節(jié)點(diǎn)在表中編號最大。 ?廣度優(yōu)先策略是 完備 的，即如果問題的解存在，則它一定可以找到解，并且找到的解還是最優(yōu)解。 ?缺點(diǎn)搜索 效率低 。 ?深度優(yōu)先搜索算法： 與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是 OPEN表 被設(shè)計成 后進(jìn)先出的棧 ，新生成的子節(jié)點(diǎn)放在 OPEN表的前面，后生成的節(jié)點(diǎn)優(yōu)先被考察。 例 1 2 3 8 5 7 4 6 1 1 2 3 8 4 5 7 6 3 1 2 3 8 4 5 7 6 1 2 3 8 4 5 7 6 1 2 3 8 5 7 4 6 1 2 3 8 4 5 7 6 1 2 3 8 4 7 6 5 4 1 2 8 4 3 7 6 5 1 2 3 8 5 7 4 6 2 1 2 3 8 4 7 6 5 5 2023/4/2 人工智能 46 深度優(yōu)先搜索 深度優(yōu)先搜索的特點(diǎn) ： ?OPEN表為一個 堆棧 。 ?一般 不能保證找到最優(yōu)解 。由于解的路徑長度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出 dm的值是比較困難的。 (1) 當(dāng)在 dm界限之內(nèi)找不到解時，可以將深度界限 dm不斷擴(kuò)大，每次增加一個深度增量 ?d，直到找到解，或者搜索完整棵樹。 當(dāng) ⊿ d =1時，算法開始蛻變?yōu)?廣度優(yōu)先搜索 算法。 步 2 若 OPEN表為空， 則考查 CLOSED表是否有待擴(kuò)展節(jié)點(diǎn)： ①若無，則問題無解，退出。 (3) 步 3 取 OPEN表中第一個節(jié)點(diǎn) N放在 CLOSED表中；并冠以編號 n； 步 4 若節(jié)點(diǎn) N為目標(biāo)節(jié)點(diǎn)，成功退出。 (1) 問題： 當(dāng) ⊿ d 1 時， 是否能保證找到最優(yōu)解？ S0Sg 2dm 1 = dm + △ ddm△ d = 3Sg 1d ( Sg 1)dm 2= d ( Sg 1) 12023/4/2 人工智能 53 (2) 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，置 d(S0)=0， dm=dm0， G=NULL。 步 6 若 N不可擴(kuò)展，則轉(zhuǎn)步 2； 步 7 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的返回指針放入OPEN表首部， 置 d（ Ni ）＝ d（ N）＋ 1 ，轉(zhuǎn)步 2。 ?啟發(fā)函數(shù) 要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識形式化，即用一定的函數(shù)表示出來，通過函數(shù)計算來評價每種選擇的價值大小，用以 指導(dǎo)搜索過程 ，這樣的函數(shù)稱為啟發(fā)函數(shù)。 啟發(fā)函數(shù)可以是： （ 1）一個節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的量度； （ 2）一個節(jié)點(diǎn)處在最佳路徑上的概率； （ 3）根據(jù)主觀經(jīng)驗的主觀打分等。 ?按選擇范圍不同，啟發(fā)式搜索分為 ： ?全局擇優(yōu)搜索 ?局部擇優(yōu)搜索 2023/4/2 人工智能 59 啟發(fā)式搜索算法 （ 2） 基本思想： 在 OPEN表中 保留所有已生成而未考察 的節(jié)點(diǎn)， 并用啟發(fā)函數(shù) h(x)對它們 全部 進(jìn)行估價 ， 從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展 ， 而不管這個節(jié)點(diǎn)出現(xiàn)在搜索樹的什么地方 。 2023/4/2 人工智能 60 啟發(fā)式搜索算法 （ 4） 基本思想： 局部擇優(yōu)搜索是在啟發(fā)性知識導(dǎo)航下的深度優(yōu)先搜索，在 OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，對其中 新生成的每個子節(jié)點(diǎn) x計算啟發(fā)函數(shù) ，從 全部子節(jié)點(diǎn) 中選出 最優(yōu)節(jié)點(diǎn) 進(jìn)行擴(kuò)展，其選擇下一個要考察節(jié)點(diǎn)的范圍是剛剛生成的全部子節(jié)點(diǎn)， 局部擇優(yōu)搜索算法： 與全局擇優(yōu)搜索算法的區(qū)別僅在 步 6： 步 6 否則，擴(kuò)展 N，計算 N的每個子節(jié)點(diǎn) x的函數(shù)值，并將 N的所有子節(jié)點(diǎn) x配以指向節(jié)點(diǎn) N的指針后，將 全部子節(jié)點(diǎn) 按啟發(fā)函數(shù)值升序排列后放入 OPEN表的首部，轉(zhuǎn)步 2。 在全局擇優(yōu)和局部擇優(yōu)搜索算法中，都沒有考慮從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)已經(jīng)付出的實(shí)際代價。將兩者同時考慮，用于指導(dǎo)搜索的算法稱為 A算法和 A*算法 。 f（ x） ＝ g（ x）＋ h（ x） ? g（ x）代價函數(shù) ： 初始節(jié)點(diǎn) S0到達(dá)節(jié)點(diǎn) x處已付出的 代價， 有利于搜索縱向發(fā)展，提高搜索效率，但影響完備性。 啟發(fā)式搜索的 A算法和 A*算法（ 3） 代價 g（ x） 的計算 g（ x） 表示從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) x的代價： g（ S0 ）＝ 0 g（ xj ）＝ g（ xi ）＋ c（ xi， xj） 其中， c（ xi， xj） 表示父節(jié)點(diǎn) xi到子節(jié)點(diǎn) xj的代價 A D C E B 4 6 4 3 3 2 3 2 3 4 6 2 3 4 4 6 3 2 C1 B1 D1 D2 E1 C2 E2 D3 C3 B2 E4 E3 6 B3 2023/4/2 人工智能 64 啟發(fā)式搜索的 A算法和 A*算法（ 4） 對估價函數(shù) f（ x） ＝ g（ x）＋ h（ x） 令其中的 h（ x） =0時，這時得到的是 代價樹 的 非啟發(fā)式搜索算法。 ? 瞎子爬山法 將局部擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到瞎子爬山搜索算法。 步 5