【正文】 則 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)轉換規(guī)則來產(chǎn)生。 ?隱式狀態(tài)空間圖 ：利用有關狀態(tài)描述和狀態(tài)轉換（操作）的知識定義的狀態(tài)空間圖。 翻動錢幣的操作抽象為改變上述狀態(tài)的算子 ， 即 F＝ {a, b, c} a:把錢幣 q0翻轉一次 b:把錢幣 q1翻轉一次 c:把錢幣 q2翻轉一次 問題的狀態(tài)空間為 {Q5}, {a, b, c}， {Q0 Q7} 2023/4/2 人工智能 18 例 翻轉錢幣問題（ 4） 問題的狀態(tài)空間為： 2023/4/2 人工智能 19 構造狀態(tài)空間圖： 5 0 7{ } { } { }Q a b c Q Q??， ， ， ， ，cbbcQ1aQs= Q5bQ7= Qg 2aQ3cQ2aQ6baQ4Q0 = Qg 1c( 0 , 0 , 0 ) ( 1 , 0 , 0 )( 0 , 0 , 1 )( 1 , 0 , 1 )( 1 , 1 , 1 ) ( 0 , 1 , 1 )( 1 , 1 , 0 )( 0 , 1 , 0 )aab aba baa bbb bcc cbc ccb 2023/4/2 人工智能 20 例 （ 1） 在河的左岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但受到以下條件的限制： （ 1）修道士和野人都會劃船，但船一次 最多 只能 運兩個人 ； （ 2）在任何岸邊 野人數(shù)目 都 不得超過修道士 ，否則修道士就會被野人吃掉。 Q2=(0,1,0) Q3=(0,1,1) 。 S F G??， ， 狀態(tài)空間圖（ 4） ? 在狀態(tài)空間表示法中，問題求解過程轉化為在圖中尋找 從初始狀態(tài) Qs出發(fā) 到達 目標狀態(tài) Qg的 路徑 問題，也就是尋找操作序列的問題。 如：如果室內(nèi)溫度低于 26度，則關閉空調。 ?描述一個操作要包含兩個部分 ? 條件 :指明被作用的狀態(tài)要滿足的約束條件 ? 動作 :指明一個操作對狀態(tài)的分量所做的改變。 2023/4/2 人工智能 11 2023/4/2 人工智能 12 狀態(tài)空間圖表示 狀態(tài)空間圖 隱式狀態(tài)空間圖 2023/4/2 人工智能 13 狀態(tài)空間圖（ 1） 狀態(tài)對應敘述性知識 ，描述一個問題在開始、結束或中間的某一時刻所處的 狀況 或 狀態(tài) 。 ?盲目搜索 ： 無向導 的 搜索 ，也稱窮舉搜索。在問題求解過程中，待求解的問題被抽象成一定空間上的圖，搜索過程就是 從 圖中 初始節(jié)點 出發(fā)，沿著與之相連的邊 試探著 前進， 尋找目標節(jié)點 或 可解節(jié)點 的過程。 （ 3） 控制性知識： 描述如何在當前狀態(tài)下選擇合適操作的知識。 例如，李明在北京，他要去西安（辦事）。 概括地說，知識是高度組織起來的信息集團，是人們在長期的生活和社會實踐中、科學研究和科學實驗中積累起來的經(jīng)驗或對客觀世界規(guī)律的認識等。第 2章 基于圖的知識表示與圖搜索技術 2023/4/2 人工智能 2 第 2章 基于圖的知識表示與圖搜索技術 概述 狀態(tài)空間圖表示 狀態(tài)空間圖的盲目搜索 狀態(tài)空間圖的啟發(fā)式搜索 與或圖表示及搜索技術 博弈樹及搜索技術 2023/4/2 人工智能 3 概述 知識與問題求解框架 知識表示 圖搜索技術 2023/4/2 人工智能 4 知識與問題求解框架 (1) ? 心理學 ：個體通過與環(huán)境相互作用后獲得的信息及其組織。 知識與問題求解框架 (2) （ 1）從應用領域來劃分 ? 常識性知識 ? 領域（專業(yè)）性知識 （ 2）從在問題求解中的作用來劃分 ? 敘述性知識 ? 過程性知識 ? 控制性知識 （ 3）從確定性來劃分 ? 確定性知識 ? 非確定性知識 （ 4）從知識的表現(xiàn)形式來劃分，可分為文字、符號、聲音、圖形、圖像等。 又如，博弈問題。 2023/4/2 人工智能 6 2023/4/2 人工智能 7 知識表示 (1) ?知識表示： 就是研究 在計算機中 如何用最合適的形式 表示 問題求解過程中所需要的各種知識，包括構成問題求解框架的全部知識。 搜索過程中 經(jīng)過 （考察過） 的節(jié)點和邊 ，按原圖的連接關系，便會 構成 一個 樹型 的有 向圖 ，稱為搜索樹。 ?啟發(fā)式搜索 ：利用 “啟發(fā)性信息 ”作為 導航 的搜索過程。通常引進一組變量 ，表示與問題狀態(tài)相關的各種要素，并用這組變量所構成的多元組 來表示狀態(tài)。 ?操作的表示形式可以是一個機械性的步驟、過程、規(guī)則或算子。 2023/4/2 人工智能 15 狀態(tài)空間圖（ 3） ?問題的 狀態(tài)空間圖 是一個描述該問題全部可能的 狀態(tài) 及相互 關系 的 圖 ，如考慮操作的代價，狀態(tài)空間圖就是一個 賦值有向圖 。 ? 狀態(tài)空間的解為三元組 Qs, a, Qg ? Qs ：某個初始狀態(tài) ? Qg ：某個目標狀態(tài) ? a：把 Qs變換成 Qg的有限的操作序列 ? 狀態(tài)轉換圖 S1 S3 S2 … f1 f2 f3 f4 Qs Qg fn 2023/4/2 人工智能 16 2023/4/2 人工智能 17 例 翻轉錢幣問題（ 1） 三枚錢幣處于反、正、反狀態(tài)，每次只許翻動一枚錢幣，問連續(xù)翻動三次后，能否出現(xiàn)全正或全反狀態(tài)。 Q4=(1,0,0)。 假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。在計算機中僅存儲描述問題狀態(tài)及操作的有關知識，包括該問題的各狀態(tài)分量的取值情況、分量之間的約束條件、開始狀態(tài)、終止狀態(tài)，以及全部操作的條件和動作等。類似于這樣表示的狀態(tài)圖稱為 隱式狀態(tài)圖 ，或者說 狀態(tài)圖 的 隱式表示 。 初始狀態(tài) ： ?=A， |?|=1 終止狀態(tài) ： ?=AA1A2… A， |?|=n+1 例 旅行商問題 (TSP)(2) （ 2）操作描述 （狀態(tài)轉換規(guī)則）： 規(guī)則 1 ：如果 ?=AA1… Ai… Aj… ，且 |?|? n，但 A’??，則置?= ? A。 2023/4/2 人工智能 32 補充例 二階梵塔問題（ 1） 有三個桿，一號桿有 A、 B兩個金盤， A小于 B。 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ī)則）： 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)空間圖的盲目搜索 ?盲目搜索 :搜索時不參考與具體待求解問題相關的任何信息，只是按預先設定的順序逐個考察節(jié)點。CLOSED表中存放的就是一定搜索策略下的搜索樹。利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴展，轉步 2； 步 6 否則，擴展 N，將其所有子節(jié)點配上指向 N的返回指針放入 OPEN表的 尾部 ，轉步 2。 ?廣度優(yōu)先搜索策略與問題無關，具有通用性。深度優(yōu)先搜索算法只需 將寬度優(yōu)先搜索算法步 6修改為 ： 步 6 否則，擴展 N，將其所有子節(jié)點配上指向 N的指針放入 OPEN表的 首部 ，轉步 2。如下圖所示： S0S g 1圖 213 深度優(yōu)先搜索不具有完備性示意圖 2023/4/2 人工智能 47 （ Acd ） 為克服深度優(yōu)先搜索的不足，可以對其深度進行限制 ?深度界限的選擇很重要 dm 若太小，則達不到解的深度，得不到解；若太大，既浪費了計算機的存儲空間與時間，又降低了搜索效率。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜索算法 (或迭代加深搜索 )。 ② 若有，則取出 CLOSED表中待擴展節(jié)點放入到 OPEN表中，令 dm=dm+⊿ d。 步 2 若 OPEN表為空，則考察 CLOSED表是否有待擴展節(jié)點： （ 1）若無待擴展節(jié)點，則判斷 G表是否為空： 若為空，搜索失敗，退出； 否則，取出 G表最后面的節(jié)點 Sg， Sg即為所求最優(yōu)解，搜索成功，退出； （ 2）若有待擴展節(jié)點，則取出 CLOSED表中待擴展節(jié)點放入到OPEN表中，令 dm=dm+⊿ d，轉步 2； (3) 步 3 取 OPEN表中首部的節(jié)點 N放在 CLOSED表中；并冠以順序編號 n； 步 4 若 d（ N） ＞ dm，則標 N為待擴展節(jié)點，轉步 2； 步 5 若 N是目標節(jié)點 Sg ，則令 dm＝ d（ Sg ） 1 ，把 Sg放到 G 表的尾部，轉步 2。 2023/4/2 人工智能 55 2023/4/2 人工智能 56 狀態(tài)空間圖的啟發(fā)式搜索 (2) 在實際設計過程中， 啟發(fā)函數(shù)是用來估計搜索樹節(jié)點x與目標節(jié)點接近程度的一種函數(shù)，通常記為 h（ x） 。 啟發(fā)式搜索算法 （ 3） 全局擇優(yōu)搜索算法： 步 1 把初始節(jié)點 S0放入 OPEN表中，計算 h(S0)； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個節(jié)點 N放入 CLOSED表中，并冠以序號 n ； 步 4 若目標節(jié)點 Sg ＝ N，則搜索成功，利用 C