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