【正文】 N表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個節(jié)點(diǎn) N放入 CLOSED表中，并冠以順序編號 n； 步 4 若目標(biāo)節(jié)點(diǎn) Sg＝ N，則搜索成功，利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出。 按對節(jié)點(diǎn)的考察范圍不同，可分為兩種搜索策略： ? 分支界限法 將全局擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到分支界限搜索算法。 ? h（ x）啟發(fā)函數(shù) ：節(jié)點(diǎn) x 到達(dá)目標(biāo)節(jié)點(diǎn) Sg的 接近程度估計值 有利于搜索橫向發(fā)展，提高搜索的完備性，但影響搜索效率。 2023/4/2 人工智能 63 啟發(fā)式搜索的 A算法和 A*算法（ 2） 1. A算法 估價函數(shù) f（ x） :為了防止在單獨(dú)利用啟發(fā)函數(shù)的時候誤入歧途，將啟發(fā)函數(shù) h（ x）與代價函數(shù) g（ x）相結(jié)合，即初始節(jié)點(diǎn) S0到達(dá)節(jié)點(diǎn) x處已付出的 代價與 節(jié)點(diǎn) x 到達(dá)目標(biāo)節(jié)點(diǎn) Sg的 接近程度估計值總和 。 在很多實(shí)際問題中，已經(jīng)付出的實(shí)際代價是必須考慮的，如 TSP問題等。 2023/4/2 人工智能 61 啟發(fā)式搜索的 A算法和 A*算法（ 1） 啟發(fā)函數(shù)是對當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)未來可能要付出的代價的估計。 啟發(fā)式搜索算法 （ 3） 全局擇優(yōu)搜索算法： 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，計算 h(S0)； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個節(jié)點(diǎn) N放入 CLOSED表中，并冠以序號 n ； 步 4 若目標(biāo)節(jié)點(diǎn) Sg ＝ N，則搜索成功，利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴(kuò)展，則轉(zhuǎn)步 2 ； 步 6 否則，擴(kuò)展 N，計算 N的每個子節(jié)點(diǎn) x的函數(shù)值，并將N所有子節(jié)點(diǎn) x配以指向 N的返回指針后放入 OPEN表中，依據(jù)啟發(fā)函數(shù)對節(jié)點(diǎn)的計算，再對 OPEN表中 所有節(jié)點(diǎn) 按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步 2。 2023/4/2 人工智能 57 狀態(tài)空間圖的啟發(fā)式搜索 (3) 啟發(fā)式搜索算法 啟發(fā)式搜索的 A算法和 A*算法 A*算法在游戲中的應(yīng)用 2023/4/2 人工智能 58 啟發(fā)式搜索算法 （ 1） ?啟發(fā)式搜索 用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再 增加啟發(fā)函數(shù)值 的 計算 與 傳播 過程，并且由 啟發(fā)函數(shù)值 來 確定 節(jié)點(diǎn)的 擴(kuò)展順序 。 2023/4/2 人工智能 55 2023/4/2 人工智能 56 狀態(tài)空間圖的啟發(fā)式搜索 (2) 在實(shí)際設(shè)計過程中， 啟發(fā)函數(shù)是用來估計搜索樹節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為 h（ x） 。 2023/4/2 人工智能 54 狀態(tài)空間圖的啟發(fā)式搜索 (1) ?啟發(fā)性知識 就是與被求解問題自身特性相關(guān)的知識，包括被求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類問題的經(jīng)驗(yàn)、技巧等，對應(yīng)于問題求解框架中的 控制性知識 。 步 2 若 OPEN表為空，則考察 CLOSED表是否有待擴(kuò)展節(jié)點(diǎn)： （ 1）若無待擴(kuò)展節(jié)點(diǎn)，則判斷 G表是否為空： 若為空，搜索失敗，退出； 否則，取出 G表最后面的節(jié)點(diǎn) Sg， Sg即為所求最優(yōu)解，搜索成功，退出； （ 2）若有待擴(kuò)展節(jié)點(diǎn)，則取出 CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表中，令 dm=dm+⊿ d，轉(zhuǎn)步 2； (3) 步 3 取 OPEN表中首部的節(jié)點(diǎn) N放在 CLOSED表中；并冠以順序編號 n； 步 4 若 d（ N） ＞ dm，則標(biāo) N為待擴(kuò)展節(jié)點(diǎn)，轉(zhuǎn)步 2； 步 5 若 N是目標(biāo)節(jié)點(diǎn) Sg ，則令 dm＝ d（ Sg ） 1 ，把 Sg放到 G 表的尾部，轉(zhuǎn)步 2。 步 5 若 N的深度 d（ N） ＞ dm（深度限制值）， 則標(biāo) N為待擴(kuò)展節(jié)點(diǎn)， 則轉(zhuǎn)步 2； 步 6 N無子節(jié)點(diǎn)，則轉(zhuǎn)步 2； 步 7 擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的指針放入OPEN首部 ， 置 d（ Ni ）＝ d（ N）＋ 1，轉(zhuǎn)步 2。 ② 若有，則取出 CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到 OPEN表中，令 dm=dm+⊿ d。 (2) ? 迭代加深搜索過程： 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中，置 S0的深度 d（ S0 ）＝ 0， dm為任意初值。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜索算法 (或迭代加深搜索 )。 ?即使能求出解，它也不一定是最優(yōu)解。如下圖所示： S0S g 1圖 213 深度優(yōu)先搜索不具有完備性示意圖 2023/4/2 人工智能 47 （ Acd ） 為克服深度優(yōu)先搜索的不足，可以對其深度進(jìn)行限制 ?深度界限的選擇很重要 dm 若太小，則達(dá)不到解的深度，得不到解；若太大，既浪費(fèi)了計算機(jī)的存儲空間與時間，又降低了搜索效率。 ?深度優(yōu)先又稱 縱向搜索 。深度優(yōu)先搜索算法只需 將寬度優(yōu)先搜索算法步 6修改為 ： 步 6 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn)配上指向 N的指針放入 OPEN表的 首部 ，轉(zhuǎn)步 2。 2023/4/2 人工智能 44 深度優(yōu)先搜索 (1) ?深度優(yōu)先搜索的基本思想： 深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)先在自己的子節(jié)點(diǎn)集合中選擇下一個被考察的節(jié)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子節(jié)點(diǎn)或受到深度限制時，才返回到上一級節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。 ?廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。 ?廣度優(yōu)先搜索又稱為 寬度優(yōu)先 或 橫向搜索 。利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴(kuò)展，轉(zhuǎn)步 2； 步 6 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn)配上指向 N的返回指針放入 OPEN表的 尾部 ，轉(zhuǎn)步 2。通過將 OPEN表設(shè)計為一個隊(duì)列來實(shí)現(xiàn)，將新生成的子節(jié)點(diǎn)放在 OPEN表的后面，保證先生成的節(jié)點(diǎn)先考察 。CLOSED表中存放的就是一定搜索策略下的搜索樹。 ?算法中使用的數(shù)據(jù)結(jié)構(gòu) : OPEN表 ： 專門登記已經(jīng)生成但還沒有考察的節(jié)點(diǎn)，即待考察節(jié)點(diǎn)。 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 補(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） 分析每個操作的條件和動作，得到下表： 補(bǔ)充例 二階梵塔問題（ 3） 2023/4/2 人工智能 35 補(bǔ)充例 二階梵塔問題（ 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 補(bǔ)充例 二階梵塔問題（ 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é)點(diǎn)。 （ 1） 有關(guān)狀態(tài)的知識： 用二元組 （ SA， SB） 表示狀態(tài) ， SA表示 A所在桿號 ， SB表示B所在桿號 。 2023/4/2 人工智能 32 補(bǔ)充例 二階梵塔問題（ 1） 有三個桿，一號桿有 A、 B兩個金盤， A小于 B。 規(guī)則 2 ： 如果 |?|= n，置 ?= ?A，即從當(dāng)前城市返回 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ī)劃一條最短的旅行路線 。類似于這樣表示的狀態(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｝， ，且 。在計算機(jī)中僅存儲描述問題狀態(tài)及操作的有關(guān)知識，包括該問題的各狀態(tài)分量的取值情況、分量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài)，以及全部操作的條件和動作等。 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)空間圖的顯示表示 。 假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 Q7=(1,1,1)。 Q4=(1,0,0)。 Q1=(0,0,1)。 ? 狀態(tài)空間的解為三元組 Qs, a, Qg ? Qs ：某個初始狀態(tài) ? Qg ：某個目標(biāo)狀態(tài) ? a：把 Qs變換成 Qg的有限的操作序列 ? 狀態(tài)轉(zhuǎn)換圖 S1 S3 S2 … f1 f2 f3 f4 Qs Qg fn 2023/4/2 人工智能 16 2023/4/2 人工智能 17 例 翻轉(zhuǎn)錢幣問題（ 1） 三枚錢幣處于反、正、反狀態(tài)，每次只許翻動一枚錢幣，問連續(xù)翻動三次后，能否出現(xiàn)全正或全反狀態(tài)。 ?由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。 2023/4/2 人工智能 15 狀態(tài)空間圖（ 3） ?問題的 狀態(tài)空間圖 是一個描述