【正文】 w(b)=6,從 w（ x）值看 a格局離目標格局更遠。 h（ x）：不同的問題啟發(fā)函數(shù)的定義不同，相同的 問題也可以定義出不同的啟發(fā)函數(shù)。 Closed表中，說明 P的后繼也在 n之前已經(jīng)生成，稱為Ps。 Path1 Path2 S0 m n P 先擴展 后擴展 P在 n之前已是某一節(jié)點 m的后繼 如圖所示：說明從 S0→P 至少有兩條路，這時有兩種情況： f（ Path2） f（ Path1），當前路徑較好，要修改 P的指針，使其指向 n，即搜索之后的最佳路徑。 2）若 xi存在于 OPEN或 CLOSED表中，也 刪除 之，但表明此時存在兩條初始節(jié)點 S0到 xi的路徑；如果 新路徑較 短 ，則 修改 xi節(jié)點的 返回指針 （指向 N），并修改 xi及其后裔節(jié)點和 f值；同時若 xi存在 于 CLOSED表中，則將其 移出放入 OPEN表 重新考察 。 按對節(jié)點的考察范圍不同，可分為兩種搜索策略： ? 分支界限法 將全局擇優(yōu)搜索算法中的 h（ x） 替換為 g（ x） ，即可得到分支界限搜索算法。 2023/4/2 人工智能 63 啟發(fā)式搜索的 A算法和 A*算法（ 2） 1. A算法 估價函數(shù) f（ x） :為了防止在單獨利用啟發(fā)函數(shù)的時候誤入歧途，將啟發(fā)函數(shù) h（ x）與代價函數(shù) g（ x）相結(jié)合，即初始節(jié)點 S0到達節(jié)點 x處已付出的 代價與 節(jié)點 x 到達目標節(jié)點 Sg的 接近程度估計值總和 。 2023/4/2 人工智能 61 啟發(fā)式搜索的 A算法和 A*算法（ 1） 啟發(fā)函數(shù)是對當前節(jié)點到達目標節(jié)點未來可能要付出的代價的估計。 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é)點的 擴展順序 。 2023/4/2 人工智能 54 狀態(tài)空間圖的啟發(fā)式搜索 (1) ?啟發(fā)性知識 就是與被求解問題自身特性相關(guān)的知識，包括被求解問題的解的特性、解的分布規(guī)律和在實際當中求解此類問題的經(jīng)驗、技巧等，對應(yīng)于問題求解框架中的 控制性知識 。 步 5 若 N的深度 d（ N） ＞ dm（深度限制值）， 則標 N為待擴展節(jié)點， 則轉(zhuǎn)步 2； 步 6 N無子節(jié)點，則轉(zhuǎn)步 2； 步 7 擴展 N，將其所有子節(jié)點 Ni配上指向 N的指針放入OPEN首部 ， 置 d（ Ni ）＝ d（ N）＋ 1，轉(zhuǎn)步 2。 (2) ? 迭代加深搜索過程： 步 1 把初始節(jié)點 S0放入 OPEN表中，置 S0的深度 d（ S0 ）＝ 0， dm為任意初值。 ?即使能求出解，它也不一定是最優(yōu)解。 ?深度優(yōu)先又稱 縱向搜索 。 2023/4/2 人工智能 44 深度優(yōu)先搜索 (1) ?深度優(yōu)先搜索的基本思想： 深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)先在自己的子節(jié)點集合中選擇下一個被考察的節(jié)點，不斷向縱深方向前進，直到到達葉子節(jié)點或受到深度限制時，才返回到上一級節(jié)點沿另一方向繼續(xù)前進。 ?廣度優(yōu)先搜索又稱為 寬度優(yōu)先 或 橫向搜索 。通過將 OPEN表設(shè)計為一個隊列來實現(xiàn)，將新生成的子節(jié)點放在 OPEN表的后面，保證先生成的節(jié)點先考察 。 ?算法中使用的數(shù)據(jù)結(jié)構(gòu) : OPEN表 ： 專門登記已經(jīng)生成但還沒有考察的節(jié)點，即待考察節(jié)點。 （ 1） 有關(guān)狀態(tài)的知識： 用二元組 （ SA， SB） 表示狀態(tài) ， SA表示 A所在桿號 ， SB表示B所在桿號 。 規(guī)則 2 ： 如果 |?|= n，置 ?= ?A，即從當前城市返回 A城。 要求為該推銷商規(guī)劃一條最短的旅行路線 。 重排九宮問題的隱式圖描述為： （ 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｝， ，且 。 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)空間圖的顯示表示 。 Q7=(1,1,1)。 Q1=(0,0,1)。 ?由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。在程序中，狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。 12 nq q q， ， ，12()nq q q， ， ，2023/4/2 人工智能 14 狀態(tài)空間圖（ 2） 操作對應(yīng)過程性知識 ，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)之間的關(guān)系。啟發(fā)式搜索廣泛地應(yīng)用于實際問題求解中，如博弈、機器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。 圖搜索技術(shù) (2) 2023/4/2 人工智能 10 SgSo問 題 全 狀 態(tài) 空 間搜 索 空 間解 路 徑圖 22搜索空間示意圖 問題的狀態(tài)空間、搜索空間及解的示意圖： 圖搜索技術(shù) (3) 搜索策略將決定搜索過程按照什么樣的順序考察節(jié)點和經(jīng)過狀態(tài)空間圖的哪些節(jié)點。 在一個 2n?2n的方格棋盤中，去掉對角的兩個方格，如圖（ a），問能否將它全部劃成若干 1?2的小長方塊？ 2 n2 n( b ) 同 構(gòu) 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 22 n2 n( b ) 同 構(gòu) 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 22 n2 n( b ) 同 構(gòu) 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 2目標狀態(tài) 初始狀態(tài) 可達狀態(tài) 同構(gòu)問題 同態(tài)問題 2023/4/2 人工智能 9 圖搜索技術(shù) (1) 搜索，簡單地說就是 “尋找 ”，目的是找到問題的解。 （ 2） 過程性知識： 描述狀態(tài)之間的變換關(guān)系的各種知識。 ?問題求解： 是指在一定的控制策略下， 通過 一系列的 操作 或 運算來 改變 問題的 狀態(tài) ，使之與目標狀態(tài)接近或一致。 ? 博恩斯坦 （ Bernstein） ：知識是由特定領(lǐng)域的描述、關(guān)系和過程組成的。 ? 費根鮑姆 ：知識是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。 2023/4/2 人工智能 5 知識與問題求解框架 (3) ?問題： 是指事件或事物的已知或 當前狀態(tài) 與 目標狀態(tài) 之間有 差異。 ?問題的求解框架 （ 1） 敘述性知識： 描述問題的狀態(tài)有關(guān)的各種知識。 ?常用的知識表示形式 ? 狀態(tài)空間圖 ? 與或圖 ? 謂詞邏輯 ? 產(chǎn)生式 ? 框架 ? 語義網(wǎng)絡(luò) ? …… 知識表示 (2) 2023/4/2 人工智能 8 例 。搜索樹是一個搜索過程的搜索軌跡，或稱之為 搜索空間。 對于較大或無限狀態(tài)空間問題，盲目搜索效率太低，所以在實際當中往往是不可行的。 狀態(tài)在狀態(tài)圖中表示為 節(jié)點 。 ?操作在狀態(tài)圖中表示為 邊 。 ?狀態(tài)空間常記為三元組： S： 初始狀態(tài)的集合 F： 操作的集合 G： 目標狀態(tài)的集合。 初始狀態(tài) Qs 目標狀態(tài)集合 {Q0, Q7} 例 翻轉(zhuǎn)錢幣問題（ 2） 引入一個三元組 (q0,q1,q2)來描述總狀態(tài) ， 錢幣正面為 0， 反面為 1， 全部可能的狀態(tài)為： Q0=(0,0,0) 。 Q5=(1,0,1) Q6=(1,1,0) 。 2023/4/2 人工智能 21 例 （ 2） 問題的狀態(tài) 可以用一個三元數(shù)組來描述： S＝ (m, c, b) m：左岸的修道士數(shù) c：左岸的野人數(shù) b：左岸的船數(shù) 右岸的狀態(tài)不必標出，因為： 右岸的修道士數(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)和操作的描述之后，