【正文】 與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是 OPEN表 被設(shè)計(jì)成 后進(jìn)先出的棧 ，新生成的子節(jié)點(diǎn)放在 OPEN表的前面，后生成的節(jié)點(diǎn)優(yōu)先被考察。 ? 廣度優(yōu)先搜索算法： 步 1 把初始節(jié)點(diǎn) S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，取 OPEN表中第一個(gè)節(jié)點(diǎn) N放在 CLOSED表中；并冠以順序編號(hào) n； 步 4 若節(jié)點(diǎn) N為目標(biāo)節(jié)點(diǎn)，則搜索成功。 其中 : 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） 。 （ 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 時(shí)， Ai? Aj； 當(dāng)且僅當(dāng) |?|=n+1時(shí) ， A’=A。 ?隱式狀態(tài)空間圖 ：利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換（操作）的知識(shí)定義的狀態(tài)空間圖。 Q2=(0,1,0) Q3=(0,1,1) 。 如：如果室內(nèi)溫度低于 26度，則關(guān)閉空調(diào)。 2023/4/2 人工智能 11 2023/4/2 人工智能 12 狀態(tài)空間圖表示 狀態(tài)空間圖 隱式狀態(tài)空間圖 2023/4/2 人工智能 13 狀態(tài)空間圖（ 1） 狀態(tài)對(duì)應(yīng)敘述性知識(shí) ，描述一個(gè)問題在開始、結(jié)束或中間的某一時(shí)刻所處的 狀況 或 狀態(tài) 。在問題求解過程中，待求解的問題被抽象成一定空間上的圖，搜索過程就是 從 圖中 初始節(jié)點(diǎn) 出發(fā)，沿著與之相連的邊 試探著 前進(jìn)， 尋找目標(biāo)節(jié)點(diǎn) 或 可解節(jié)點(diǎn) 的過程。 例如，李明在北京，他要去西安（辦事）。第 2章 基于圖的知識(shí)表示與圖搜索技術(shù) 2023/4/2 人工智能 2 第 2章 基于圖的知識(shí)表示與圖搜索技術(shù) 概述 狀態(tài)空間圖表示 狀態(tài)空間圖的盲目搜索 狀態(tài)空間圖的啟發(fā)式搜索 與或圖表示及搜索技術(shù) 博弈樹及搜索技術(shù) 2023/4/2 人工智能 3 概述 知識(shí)與問題求解框架 知識(shí)表示 圖搜索技術(shù) 2023/4/2 人工智能 4 知識(shí)與問題求解框架 (1) ? 心理學(xué) ：個(gè)體通過與環(huán)境相互作用后獲得的信息及其組織。 又如，博弈問題。 搜索過程中 經(jīng)過 （考察過） 的節(jié)點(diǎn)和邊 ，按原圖的連接關(guān)系，便會(huì) 構(gòu)成 一個(gè) 樹型 的有 向圖 ，稱為搜索樹。通常引進(jìn)一組變量 ，表示與問題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組 來表示狀態(tài)。 2023/4/2 人工智能 15 狀態(tài)空間圖（ 3） ?問題的 狀態(tài)空間圖 是一個(gè)描述該問題全部可能的 狀態(tài) 及相互 關(guān)系 的 圖 ，如考慮操作的代價(jià)，狀態(tài)空間圖就是一個(gè) 賦值有向圖 。 Q4=(1,0,0)。在計(jì)算機(jī)中僅存儲(chǔ)描述問題狀態(tài)及操作的有關(guān)知識(shí)，包括該問題的各狀態(tài)分量的取值情況、分量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài)，以及全部操作的條件和動(dòng)作等。 初始狀態(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。 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)操作的知識(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ǔ)充例 二階梵塔問題（ 3） 2023/4/2 人工智能 35 補(bǔ)充例 二階梵塔問題（ 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ǔ)充例 二階梵塔問題（ 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í)不參考與具體待求解問題相關(guān)的任何信息，只是按預(yù)先設(shè)定的順序逐個(gè)考察節(jié)點(diǎn)。利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴(kuò)展，轉(zhuǎn)步 2； 步 6 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn)配上指向 N的返回指針放入 OPEN表的 尾部 ，轉(zhuǎn)步 2。深度優(yōu)先搜索算法只需 將寬度優(yōu)先搜索算法步 6修改為 ： 步 6 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn)配上指向 N的指針放入 OPEN表的 首部 ，轉(zhuǎn)步 2。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜索算法 (或迭代加深搜索 )。 步 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表中；并冠以順序編號(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。 啟發(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。 ? h（ x）啟發(fā)函數(shù) ：節(jié)點(diǎn) x 到達(dá)目標(biāo)節(jié)點(diǎn) Sg的 接近程度估計(jì)值 有利于搜索橫向發(fā)展，提高搜索的完備性，但影響搜索效率。 步 7 對(duì) OPEN表中所有節(jié)點(diǎn)按 f值以升序排列，轉(zhuǎn)步 2。 2023/4/2 人工智能 71 啟發(fā)式搜索的 A算法和 A*算法（ 11） f（ x） ＝ g（ x）＋ h（ x） 探討九宮重排問題的估價(jià)函數(shù)的設(shè)計(jì)過程。 0 2 1 1 1 1 1 1 p(a)=8 0 2 1 2 2 1 0 1 p(b)=9 反映出 a比 b更容易 到達(dá)目標(biāo)格局 實(shí)際距離為 8 實(shí)際距離為 11 2023/4/2 人工智能 79 1 4 8 3 2 7 6 5 5 1 2 3 8 4 7 6 5 Sg 1 擴(kuò)展順序 f3(x)值 1 3 4 8 2 7 6 5 5 1 4 8 3 2 7 6 5 1 4 8 3 2 7 6 5 7 7 1 3 4 8 2 7 6 5 1 3 4 8 2 7 6 5 5 1 3 4 8 6 2 7 5 7 7 2 3 1 3 8 2 4 7 6 5 5 1 3 4 8 2 5 7 6 7 4 1 3 8 2 4 7 6 5 5 5 1 2 3 8 4 7 6 5 5 6 8 1 3 8 2 4 7 6 5 2023/4/2 人工智能 80 啟發(fā)式搜索的 A算法和 A*算法（ 20） 因素 3 格局中將牌回家的順序 8 1 2 6 3 7 5 4 1 2 3 8 4 7 6 5 Sg 2 8 1 4 6 3 7 5 b a 因素 4 中心位置是否有將牌 沿著周圍非中心方格上依順時(shí)針檢查 x格局 中的每一個(gè)將牌，如果其后緊跟著的將牌正好是目標(biāo) 格局中該將牌的后續(xù)者，該將牌得 0分，否則得 2分。 2023/4/2 人工智能 84 啟發(fā)式搜索的 A算法和 A*算法（ 24） 解：先建立問題的狀態(tài)空間。目前，游戲業(yè)界的標(biāo)準(zhǔn)是使用 A*算法或 IDA*算法， A*算法一般要快一些，而 IDA*算法則比 A*算法要使用更少的內(nèi)存。即一個(gè)問題與一組子問題的 或等價(jià) 。 B180。 ：證明 CD＝ C ′D′ Q23 180。 弧線表示所連邊為“與”的關(guān)系 不帶弧線的邊為或關(guān)系 與或圖表示（ 6） 例 梵塔問題。 與或圖一般表示問題的變換過程，就是從原問題出發(fā)，運(yùn)用某些規(guī)則不斷的進(jìn)行問題的 分解 （得到 與分支 ）和變換 （得到 或分支 ），而得到一個(gè)與或圖，與或圖的節(jié)點(diǎn)一般代表問題，整個(gè)圖就表示問題空間。 （ 4）非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)； （ 5）一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)至少有一個(gè)不可解； （ 6）一個(gè)或節(jié)點(diǎn)不可解，當(dāng)且僅當(dāng)其全部子節(jié)點(diǎn)不可解。移動(dòng)金盤的規(guī)則是： 一次 只 能 移一個(gè) 金盤； 移動(dòng)的過程中 不允許大盤壓 在 小盤 上。 2023/4/2 人工智能 100 與或圖表示（ 5） 將原問題用圖的形式表示如下： Q Q1 Q2 Q11 Q12 Q13 Q11 39。 C180。屋頂上 D處掛著一串香蕉，猴子爬到梯子上或箱子上都能摘到香蕉。 ? 在游戲設(shè)計(jì)中，使用 A*算法尋找路徑時(shí)，啟發(fā)函數(shù) h(x)的設(shè)計(jì)還需要考慮更多的因素，如路徑的距離、途中的障礙物、地形允許的行走速度、是否敵人視線與火力之下的位置、敵我雙方暴露的時(shí)間和次數(shù)、