狀態(tài)空間搜索策略

1、三、搜索策略三、搜索策略3.1 圖搜索策略3.2 盲目搜索3.3 啟發(fā)式搜索 從問題表示到問題的解決，有一個(gè)求解的過程。常見的AI問題求解技術(shù)有兩種，即“搜索”（Search）和“推理”（Reasoning）方法。 邏輯推理，是通過構(gòu)造一個(gè)邏輯系統(tǒng)，由它可以從已有的斷言（公理）推導(dǎo)出新的斷言。并用邏輯形式語言描述的一組公理來表達(dá)問題域。用這種方法來解決問題就是通過推理來積聚越來越多的斷言，直到獲得問題的解答。 雖然問題求解可通過搜索方法，也可用邏輯推理，但二者的側(cè)重點(diǎn)是不一樣的。前者著重于尋求問題解答的過程，而后者強(qiáng)調(diào)前提（初始）問題空間（公理集合）與問題解答間連接的邏輯正確性?；蛘吆?jiǎn)單地講，

2、搜索著重于發(fā)現(xiàn)（Discovery），而推理強(qiáng)調(diào)證明（Proof）。 搜索 在狀態(tài)圖中尋找目標(biāo)或路徑的基本方法 從初始節(jié)點(diǎn)，沿著與之相連的邊，尋找目標(biāo)節(jié)點(diǎn)的過程 搜索樹 搜索過程中經(jīng)過的節(jié)點(diǎn)和邊，按照原圖的連接關(guān)系，便形成一個(gè)樹形的有向圖 盲目搜索 無向?qū)阉?窮舉式搜索 從初始節(jié)點(diǎn)，沿連接邊逐一考察各個(gè)節(jié)點(diǎn)，或反向進(jìn)行 啟發(fā)式(heuristic)搜索 利用“啟發(fā)性信息”引導(dǎo)的搜索 啟發(fā)式信息是與問題有關(guān)的有利于盡快找到問題解的信息或知識(shí)3.1 圖搜索策略 圖（狀態(tài)圖）搜索控制策略一種在圖中尋找路徑的方法。圖中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)狀態(tài)，每條連線對(duì)應(yīng)一個(gè)操作符。這些節(jié)點(diǎn)和連線(即狀態(tài)與操作符)又分

3、別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標(biāo)記。求得把一個(gè)數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價(jià)于求得圖中的一條路徑問題。 圖組成 節(jié)點(diǎn) 有向邊 圖分類 或圖（直接圖、狀態(tài)圖） 與或圖圖搜索過程圖 圖（狀態(tài)圖）搜索策略 CLOSED 表：用來記錄考察過的節(jié)點(diǎn) 對(duì)樹形搜索，存儲(chǔ)的是搜索樹 對(duì)線式搜索，存儲(chǔ)的是折線 OPEN表：記錄待考察的節(jié)點(diǎn) 排序方式不同，對(duì)應(yīng)的搜索算法不同節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)CLOSED表OPEN表開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針方向重排

4、OPEN表失敗成功圖3.1 圖搜索過程框圖是是否否3.2 盲目搜索 特點(diǎn)：不需重排OPEN表 種類：寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。3.2.1 寬度優(yōu)先搜索v 定義 以接近起始節(jié)點(diǎn)的程度逐層擴(kuò)展節(jié)點(diǎn)的搜索方法。v 特點(diǎn)： 一種高代價(jià)搜索，但若有解存在，則必能找到它。v 算法 廣度（寬度）優(yōu)先搜索廣度（寬度）優(yōu)先搜索 (Breadth-first search, BFS) 優(yōu)先在同一級(jí)節(jié)點(diǎn)中考察，只有當(dāng)同一級(jí)節(jié)點(diǎn)考察完畢之后，才考察下一級(jí)節(jié)點(diǎn) 自頂向下一層一層逐漸生成的 寬度優(yōu)先搜索算法寬度優(yōu)先搜索算法步1 ：把初始節(jié)點(diǎn)So放入OPEN表中。步2 ：若OPEN表為空, 則搜索失敗,退出。 步3

5、 ：取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放在CLOSED表中, 并冠以順序編號(hào)n。步4 ：若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功, 結(jié)束。 步5 ：若N不可擴(kuò)展, 則轉(zhuǎn)步2。步6 ：擴(kuò)展N, 將mj子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表尾部, 轉(zhuǎn)步2。 注解注解：1. OPEN表是一個(gè)隊(duì)列2. CLOSED表是一個(gè)順序表，表中各節(jié)點(diǎn)按順序標(biāo)號(hào)，正在被考察的節(jié)點(diǎn)在表中編號(hào)最大3. 如果問題有解，目標(biāo)點(diǎn)Sg必出現(xiàn)在OPEN表中，算法結(jié)束4. 根據(jù)返回指針，在CLOSED表中回溯，得到求解路徑開始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？擴(kuò)展n

6、，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針失敗成功圖3.2 寬度優(yōu)先算法框圖是否是否 例子八數(shù)碼難題（8-puzzle problem） 1238456712384567（目標(biāo)狀態(tài)）規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_始順時(shí)針旋轉(zhuǎn)。不許斜向移動(dòng)，也不返回先輩節(jié)點(diǎn)。從圖可見，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解（目標(biāo)節(jié)點(diǎn)）。1238456712384123845674123856712 3841238456712384567123845676789101112131238456756756711238456712384567123845671238456723451

7、3456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 384567123845671238456712384567141516171819202112384567圖3.4 八數(shù)碼難題的寬度優(yōu)先搜索樹 寬度優(yōu)先搜索算法寬度優(yōu)先搜索算法 寬度優(yōu)先/橫向搜索 優(yōu)點(diǎn) 策略是完備的 如果有解，肯定找到解，且找到的解是最優(yōu)解(最短路徑) 缺點(diǎn) 效率低 節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+13.2.2 深度優(yōu)先搜索3.2.2 深度優(yōu)先搜索v 定義 首先擴(kuò)展最新產(chǎn)生

8、的(即最深的)節(jié)點(diǎn)。v 算法 防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度深度界限。 與寬度優(yōu)先搜索算法最根本的不同在于：將擴(kuò)展的后繼節(jié)點(diǎn)放在OPEN表的前端。（算法框圖見教材） 深度優(yōu)先搜索深度優(yōu)先搜索（Depth-first search ，DFS） 在搜索樹的每一層始終只擴(kuò)展一個(gè)子結(jié)點(diǎn)，不斷地向縱深前進(jìn) 直到不能再前進(jìn)（到達(dá)葉子結(jié)點(diǎn)或深度限制），才從當(dāng)前節(jié)點(diǎn)返回上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn) 從樹根開始一枝一枝逐漸生成的 路徑 節(jié)點(diǎn)序列為(n0, n1,nk) 對(duì)于i=1,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni， 該序列稱為從n0到nk的路徑n0nkn1nk-1n

9、3n2 深度優(yōu)先搜索算法深度優(yōu)先搜索算法 縱向搜索 缺點(diǎn) 如果一個(gè)有解的問題樹可能有無窮分支，如果誤入無窮分支（即深度無限），則不可能找到目標(biāo)節(jié)點(diǎn) 策略不是完備的 找到的解是不一定最優(yōu)解最短路徑)3.2.3 等代價(jià)搜索v 定義 是寬度優(yōu)先搜索的一種推廣，不是沿著等長(zhǎng)度路徑斷層進(jìn)行擴(kuò)展，而是沿著等代價(jià)路徑斷層進(jìn)行擴(kuò)展。 搜索樹中每條連接弧線上的有關(guān)代價(jià),表示時(shí)間、距離等花費(fèi)。 v 算法 若所有連接弧線具有相等代價(jià)，則簡(jiǎn)化為寬度優(yōu)先搜索算法。開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點(diǎn)i從OPEN表移至CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？失敗成功圖3.2 等代價(jià)搜索算法框

10、圖是否是否S是否目標(biāo)節(jié)點(diǎn)？是成功擴(kuò)展i，計(jì)算其后繼節(jié)點(diǎn)j的g(j)，并把后繼節(jié)點(diǎn)放入OPEN表否令g(s)=0國際象棋對(duì)弈程序國際象棋對(duì)弈程序: :深藍(lán)深藍(lán)開發(fā)者開發(fā)者: IBM : IBM 的的Murry Campbell, Feng-Hsiung Hsu Murry Campbell, Feng-Hsiung Hsu 和和Joseph HoaneJoseph Hoane采用采用3030個(gè)個(gè)IBM RS/6000IBM RS/6000處理器來運(yùn)行軟件搜索處理器來運(yùn)行軟件搜索使用使用480480個(gè)定制個(gè)定制VLSIVLSI國際象棋處理器執(zhí)行生成行棋的功能國際象棋處理器執(zhí)行生成行棋的功能樹的最后

11、幾層的樹的最后幾層的”硬件搜索硬件搜索”以及對(duì)葉節(jié)點(diǎn)的評(píng)價(jià)以及對(duì)葉節(jié)點(diǎn)的評(píng)價(jià). .每秒平均搜索每秒平均搜索12.612.6億種走法，峰值時(shí)每秒鐘搜索億種走法，峰值時(shí)每秒鐘搜索3333億個(gè)節(jié)點(diǎn)億個(gè)節(jié)點(diǎn). . 每走一步至多每走一步至多能夠預(yù)先計(jì)算能夠預(yù)先計(jì)算300300億種個(gè)棋局億種個(gè)棋局, , 常規(guī)搜索深度是常規(guī)搜索深度是1414步步. .機(jī)器的核心算法是使用調(diào)換表的標(biāo)準(zhǔn)迭代深入機(jī)器的核心算法是使用調(diào)換表的標(biāo)準(zhǔn)迭代深入-搜索搜索, , 而且對(duì)關(guān)鍵的點(diǎn)具而且對(duì)關(guān)鍵的點(diǎn)具備產(chǎn)生超越搜索深度的擴(kuò)展能力備產(chǎn)生超越搜索深度的擴(kuò)展能力, ,在某些情況下可以達(dá)到在某些情況下可以達(dá)到4040層的深度層的深度.

12、.評(píng)價(jià)函數(shù)采用了超過評(píng)價(jià)函數(shù)采用了超過80008000個(gè)特征個(gè)特征; ;使用一本有使用一本有40004000個(gè)棋局的個(gè)棋局的”開局手冊(cè)開局手冊(cè)”以以及一個(gè)存有及一個(gè)存有7070萬個(gè)大師級(jí)比賽棋譜的數(shù)據(jù)庫萬個(gè)大師級(jí)比賽棋譜的數(shù)據(jù)庫; ; 使用一個(gè)大型殘局?jǐn)?shù)據(jù)庫保存使用一個(gè)大型殘局?jǐn)?shù)據(jù)庫保存已解決的棋局已解決的棋局. .Video http:/ Deep Blue 15 years http:/ 卡斯帕羅夫 http:/ Windows 8 http:/ Kinect問題的提出問題的提出 窮舉算法 可以解決狀態(tài)空間很小的簡(jiǎn)單問題 大空間無法勝任：組合爆炸 組合爆炸 64階梵塔： 節(jié)點(diǎn)：364=0.

13、94*1030 理論最短路徑：264-1=2*1019 博弈 一字棋：9！= 3.6*105 西洋棋：1078 國際象棋：10120（極限并行速度10-104秒/步，需1016年） 圍棋：107613.3 啟發(fā)式搜索啟發(fā)性信息啟發(fā)性信息 按其用途劃分, 啟發(fā)性信息可分為以下三類： 用于擴(kuò)展節(jié)點(diǎn)的選擇, 即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn), 以免盲目擴(kuò)展。 用于生成節(jié)點(diǎn)的選擇,即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn),以免盲目地生成過多無用節(jié)點(diǎn)。 用于刪除節(jié)點(diǎn)的選擇,即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn), 以免造成進(jìn)一步的時(shí)空浪費(fèi)。 3.3 啟發(fā)式搜索 特點(diǎn)：重排OPEN表，選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展 種類：有序搜索、A

14、*算法等3.3.1 啟發(fā)式搜索策略和估價(jià)函數(shù)v盲目搜索可能帶來組合爆炸v啟發(fā)式信息 用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息。 啟發(fā)函數(shù)啟發(fā)函數(shù) 啟發(fā)函數(shù)是用來估計(jì)搜索樹上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度的一種函數(shù), 通常記為h(x) 定義 一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的度量 一個(gè)節(jié)點(diǎn)處于最佳路徑上的概率 根據(jù)經(jīng)驗(yàn)的主觀打分 估價(jià)函數(shù) 為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上 。 f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值 應(yīng)用節(jié)點(diǎn)“希望”程度（估價(jià)函數(shù)值）重排OPEN表3.3.2 有序搜索v實(shí)質(zhì) 選擇OPEN表上具有最小f值的節(jié)點(diǎn)

15、作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。開始把S放入OPEN表，計(jì)算估價(jià)函數(shù) f (s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表i為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供返回節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖3.9 有序搜索算法框圖是否是否v算法 例子八數(shù)碼難題（8-puzzle problem）12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）八數(shù)碼難題的有序搜索樹見下圖：123845671238456712384567（4）（6）（6）123845671238456712384567（6）（5）（5）12384567

16、12 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）圖3.10 八數(shù)碼難題的有序搜索樹123846（4）7 啟發(fā)式搜索 利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的 在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率 啟發(fā)信息 強(qiáng) 降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解 弱 產(chǎn)生式系統(tǒng)在找到一條路徑之前將擴(kuò)展過多的節(jié)點(diǎn)，一般導(dǎo)致工作量加大 極限情況下盲目搜索，但可能可以找到最優(yōu)解3.3.3 A*算法A*算法 評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù) f(n) = g(n) + h(n) n是被

17、評(píng)價(jià)的結(jié)點(diǎn) f(n) 評(píng)價(jià)函數(shù) 從s經(jīng)過n到g的路徑的耗散值 g(n) 代價(jià)函數(shù) 從s到n的路徑的耗散值 h(n) 啟發(fā)函數(shù) 從n到g的路徑的耗散值3.3.3 A*算法 估價(jià)函數(shù)的定義：對(duì)節(jié)點(diǎn)n定義f f* *(n)=g(n)=g* *(n)+h(n)+h* *(n)(n) ,表示從S開始約束通過節(jié)點(diǎn)n的一條最佳路徑的代價(jià)。希望估價(jià)函數(shù)f 定義為：f(n)=g(n)+h(n) g是g*的估計(jì) ，h是h*的估計(jì) A*算法的定義：定義定義1 1 在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為A算法。 定義定義2 2 在A算法中，如果

18、對(duì)所有的x存在h(x)h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。 定義定義3 3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?評(píng)價(jià)函數(shù)的計(jì)算 g（n） 根據(jù)已搜索的結(jié)果，按照從初始結(jié)點(diǎn)s到結(jié)點(diǎn)n的路徑，計(jì)算其耗散值即可 g(n)對(duì)g*(n)作出估計(jì)，有g(shù)(n)g*(n) h(n) 依賴于啟發(fā)信息，稱為啟發(fā)函數(shù)啟發(fā)函數(shù) 對(duì)未來擴(kuò)展的方向作出估計(jì) f(n) 按f(n)遞增的順序來排列OPEN表的節(jié)點(diǎn)，優(yōu)先擴(kuò)展f(n)值小的節(jié)點(diǎn)，體現(xiàn)了好的優(yōu)先搜索思想3.3.3 A*算法 八數(shù)碼2 8 31 6 47 51 2 38 47 6 5初始狀態(tài)八數(shù)碼八數(shù)碼 評(píng)價(jià)函數(shù) f(n) = g(n) + h(n) g(n)：從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值 h(n)：當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)2 8 31 6 47 51 2 3457 6 8h(n) =42 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51