【正文】 ? 無子節(jié)點的節(jié)點稱為 端節(jié)點 。 ：證明 AD＝ A′D ′ Q13 180。 2023/4/2 人工智能 93 與或圖表示及搜索技術(shù) 與或圖表示 與或樹的盲目搜索 與或樹的啟發(fā)式搜索 與或圖表示（ 1） ? 與或圖的概念來源于問題求解中的分解和變換 ? 一個復(fù)雜的問題 P常?？梢苑纸鉃榕c之等價的一組子問題 P1， P2 ， ? Pn， 當(dāng)這些問題全部可解時，問題可解；任何一個子問題無解時，都將導(dǎo)致原問題 P無解。在河的左岸有五個修道士、五個野人和一條船，修道士們想用這條船將所有的人都運過河去，但受到以下條件的限制： （ 1）修道士和野人都會劃船，但船一次 最多 只能 運三個人； （ 2）在任何岸邊及船上 野人數(shù)目 都 不得超過修道士 ，否則修道士就會被野人吃掉。 S0 過去生成 P的路徑 現(xiàn)在生成 P的路徑 過去對 Ps的 最優(yōu)路徑 Ps P m n k n之前已是某一節(jié)點 m的后繼，所以需要做如同（ 2）同樣的處理，如圖右部所示。將兩者同時考慮，用于指導(dǎo)搜索的算法稱為 A算法和 A*算法 。 (3) 步 3 取 OPEN表中第一個節(jié)點 N放在 CLOSED表中；并冠以編號 n； 步 4 若節(jié)點 N為目標(biāo)節(jié)點，成功退出。 ?缺點搜索 效率低 。要求將 A、B移至三號桿，每次只可移動一個盤子，任何時刻 B不能在 A上。 2023/4/2 人工智能 21 例 （ 2） 問題的狀態(tài) 可以用一個三元數(shù)組來描述： S＝ (m, c, b) m：左岸的修道士數(shù) c：左岸的野人數(shù) b：左岸的船數(shù) 右岸的狀態(tài)不必標(biāo)出，因為： 右岸的修道士數(shù) m’ ＝ 3－ m 右岸的野人數(shù) c’ ＝ 3－ c 右岸的船數(shù) b’ ＝ 1－ b 2023/4/2 人工智能 22 例 （ 3） 狀態(tài) m, c, b 狀態(tài) m, c, b 狀態(tài) m, c, b 狀態(tài) m, c, b S0 3 3 1 S8 1 3 1 S16 3 3 0 S24 1 3 0 S1 3 2 1 S9 1 2 1 S17 3 2 0 S25 1 2 0 S2 3 1 1 S10 1 1 1 S18 3 1 0 S26 1 1 0 S3 3 0 1 S11 1 0 1 S19 3 0 0 S27 1 0 0 S4 2 3 1 S12 0 3 1 S20 2 3 0 S28 0 3 0 S5 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0 S6 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0 S7 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0 2023/4/2 人工智能 23 例 （ 4） F＝ {p01, p10,p11,p02,p20,q01,q10,q11, q02,q20} q20 b=0, (m=0,c=2)或 (m=1,c=1) b=1, m=m+2 q02 b=0, m=0或 3, c≤ 2 b=1, c=c+2 q11 b=0, m=c, c≤ 2 b=1, m=m+1, c=c+1 q10 b=0, (m=0,c=1)或 (m=2,c=2) b=1, m=m+1 q01 b=0, m=0或 3, c≤ 2 b=1, c=c+1 p20 b=1, (m=3,c=1)或 (m=2,c=2) b=0, m=m2 p02 b=1, m=0或 3, c≥2 b=0, c=c2 p11 b=1, m=c, c≥1 b=0, m=m1, c=c1 p10 b=1, (m=3,c=2)或 (m=1,c=1) b=0, m=m1 p01 b=1, m=0或 3, c≥1 b=0, c=c1 操作符 條 件 動 作 例 （ 5） 給出狀態(tài)和操作的描述之后，該問題的狀態(tài)空間是： {{S0}， { P 01， P 10， P 11， P 02， P 20， Q01， Q 10， Q 11， Q 02， Q 20}， {S31}}。 ?操作在狀態(tài)圖中表示為 邊 。 ?常用的知識表示形式 ? 狀態(tài)空間圖 ? 與或圖 ? 謂詞邏輯 ? 產(chǎn)生式 ? 框架 ? 語義網(wǎng)絡(luò) ? …… 知識表示 (2) 2023/4/2 人工智能 8 例 。 ? 博恩斯坦 （ Bernstein） ：知識是由特定領(lǐng)域的描述、關(guān)系和過程組成的。 圖搜索技術(shù) (2) 2023/4/2 人工智能 10 SgSo問 題 全 狀 態(tài) 空 間搜 索 空 間解 路 徑圖 22搜索空間示意圖 問題的狀態(tài)空間、搜索空間及解的示意圖： 圖搜索技術(shù) (3) 搜索策略將決定搜索過程按照什么樣的順序考察節(jié)點和經(jīng)過狀態(tài)空間圖的哪些節(jié)點。 ?由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(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｝， ，且 。 ?算法中使用的數(shù)據(jù)結(jié)構(gòu) : OPEN表 ： 專門登記已經(jīng)生成但還沒有考察的節(jié)點，即待考察節(jié)點。 ?深度優(yōu)先又稱 縱向搜索 。 2023/4/2 人工智能 54 狀態(tài)空間圖的啟發(fā)式搜索 (1) ?啟發(fā)性知識 就是與被求解問題自身特性相關(guān)的知識，包括被求解問題的解的特性、解的分布規(guī)律和在實際當(dāng)中求解此類問題的經(jīng)驗、技巧等，對應(yīng)于問題求解框架中的 控制性知識 。 按對節(jié)點的考察范圍不同，可分為兩種搜索策略： ? 分支界限法 將全局擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到分支界限搜索算法。 h（ x）：不同的問題啟發(fā)函數(shù)的定義不同，相同的 問題也可以定義出不同的啟發(fā)函數(shù)。 啟發(fā)函數(shù) 1： h（ n） =0。屋頂上 D處掛著一串香蕉，猴子爬到梯子上或箱子上都能摘到香蕉。 2023/4/2 人工智能 100 與或圖表示（ 5） 將原問題用圖的形式表示如下： Q Q1 Q2 Q11 Q12 Q13 Q11 39。 （ 4）非終止節(jié)點的端節(jié)點是不可解節(jié)點； （ 5）一個與節(jié)點不可解，只要其子節(jié)點至少有一個不可解； （ 6）一個或節(jié)點不可解，當(dāng)且僅當(dāng)其全部子節(jié)點不可解。 弧線表示所連邊為“與”的關(guān)系 不帶弧線的邊為或關(guān)系 與或圖表示（ 6） 例 梵塔問題。 B180。目前，游戲業(yè)界的標(biāo)準(zhǔn)是使用 A*算法或 IDA*算法， A*算法一般要快一些，而 IDA*算法則比 A*算法要使用更少的內(nèi)存。 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)格局 實際距離為 8 實際距離為 11 2023/4/2 人工智能 79 1 4 8 3 2 7 6 5 5 1 2 3 8 4 7 6 5 Sg 1 擴展順序 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 中心位置是否有將牌 沿著周圍非中心方格上依順時針檢查 x格局 中的每一個將牌，如果其后緊跟著的將牌正好是目標(biāo) 格局中該將牌的后續(xù)者，該將牌得 0分，否則得 2分。 步 7 對 OPEN表中所有節(jié)點按 f值以升序排列，轉(zhuǎn)步 2。 啟發(fā)式搜索算法 （ 3） 全局擇優(yōu)搜索算法： 步 1 把初始節(jié)點 S0放入 OPEN表中，計算 h(S0)； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個節(jié)點 N放入 CLOSED表中，并冠以序號 n ； 步 4 若目標(biāo)節(jié)點 Sg ＝ N，則搜索成功，利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴展，則轉(zhuǎn)步 2 ； 步 6 否則，擴展 N，計算 N的每個子節(jié)點 x的函數(shù)值，并將N所有子節(jié)點 x配以指向 N的返回指針后放入 OPEN表中，依據(jù)啟發(fā)函數(shù)對節(jié)點的計算，再對 OPEN表中 所有節(jié)點 按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步 2。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜索算法 (或迭代加深搜索 )。利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出； 步 5 若 N不可擴展，轉(zhuǎn)步 2； 步 6 否則，擴展 N，將其所有子節(jié)點配上指向 N的返回指針放入 OPEN表的 尾部 ，轉(zhuǎn)步 2。 初始狀態(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。 Q4=(1,0,0)。通常引進(jìn)一組變量 ，表示與問題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組 來表示狀態(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)對應(yīng)敘述性知識 ，描述一個問題在開始、結(jié)束或中間的某一時刻所處的 狀況 或 狀態(tài) 。 Q2=(0,1,0) Q3=(0,1,1) 。 （ 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。 ? 廣度優(yōu)先搜索算法： 步 1 把初始節(jié)點 S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，取 OPEN表中第一個節(jié)點 N放在 CLOSED表中；并冠以順序編號 n； 步 4 若節(jié)點 N為目標(biāo)節(jié)點，則搜索成功。 (1) 當(dāng)在 dm界限之內(nèi)找不到解時，可以將深度界限 dm不斷擴大，每次增加一個深度增量 ?d，直到找到解，或者搜索完整棵樹。 ?按選擇范圍不同，啟發(fā)式搜索分為 ： ?全局擇優(yōu)搜索 ?局部擇優(yōu)搜索 2023/4/2 人工智能 59 啟發(fā)式搜索算法 （ 2） 基本思想： 在 OPEN表中 保留所有已生成而未考察 的節(jié)點， 并用啟發(fā)函數(shù) h(x)對它們 全部 進(jìn)行估價 ， 從中選出最優(yōu)節(jié)點進(jìn)行擴展 ， 而不管這個節(jié)點出現(xiàn)在搜索樹的什么