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

1、三、搜索戰(zhàn)略3.1 圖搜索戰(zhàn)略3.2 盲目搜索3.3 啟發(fā)式搜索 從問題表示到問題的處理，有一個求解的過程。常見的AI問題求解技術(shù)有兩種，即“搜索Search和“推理Reasoning方法。 邏輯推理，是經(jīng)過構(gòu)造一個邏輯系統(tǒng)，由它可以從已有的斷言公理推導(dǎo)出新的斷言。并用邏輯方式言語描畫的一組公理來表達問題域。用這種方法來處理問題就是經(jīng)過推理來積聚越來越多的斷言，直到獲得問題的解答。 雖然問題求解可經(jīng)過搜索方法，也可用邏輯推理，但二者的偏重點是不一樣的。前者著重于尋求問題解答的過程，而后者強調(diào)前提初始問題空間公理集合與問題解答間銜接的邏輯正確性?；蛘吆唵蔚刂v，搜索著重于發(fā)現(xiàn)Discovery，而

2、推理強調(diào)證明Proof。 搜索在形狀圖中尋覓目的或途徑的根本方法從初始節(jié)點，沿著與之相連的邊，尋覓目的節(jié)點的過程搜索樹搜索過程中經(jīng)過的節(jié)點和邊，按照原圖的銜接關(guān)系，便構(gòu)成一個樹形的有向圖盲目搜索無導(dǎo)游搜索/窮舉式搜索從初始節(jié)點，沿銜接邊逐一調(diào)查各個節(jié)點，或反向進展啟發(fā)式(heuristic)搜索利用“啟發(fā)性信息引導(dǎo)的搜索啟發(fā)式信息是與問題有關(guān)的有利于盡快找到問題解的信息或知識3.1 圖搜索戰(zhàn)略 圖形狀圖搜索控制戰(zhàn)略一種在圖中尋覓途徑的方法。圖中每個節(jié)點對應(yīng)一個形狀，每條連線對應(yīng)一個操作符。這些節(jié)點和連線(即形狀與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)那么來標(biāo)志。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫

3、的規(guī)那么序列問題就等價于求得圖中的一條途徑問題。圖組成節(jié)點有向邊圖分類或圖直接圖、形狀圖與或圖圖搜索過程圖圖形狀圖搜索戰(zhàn)略CLOSED 表：用來記錄調(diào)查過的節(jié)點對樹形搜索，存儲的是搜索樹對線式搜索，存儲的是折線OPEN表：記錄待調(diào)查的節(jié)點排序方式不同，對應(yīng)的搜索算法不同節(jié)點父節(jié)點編號編號節(jié)點父節(jié)點編號CLOSED表OPEN表開場把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目的節(jié)點嗎？把n的后繼節(jié)點放入OPEN表的末端，提供前往節(jié)點n的指針修正指針方向重排OPEN表失敗勝利圖3.1 圖搜索過程框圖是是否否3.2 盲目搜索 特點：不需重排OPEN表種類：

4、寬度優(yōu)先、深度優(yōu)先、等代價搜索等。3.2.1 寬度優(yōu)先搜索 定義 以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法。 特點： 一種高代價搜索，但假設(shè)有解存在，那么必能找到它。 算法廣度寬度優(yōu)先搜索 (Breadth-first search, BFS)優(yōu)先在同一級節(jié)點中調(diào)查，只需當(dāng)同一級節(jié)點調(diào)查終了之后，才調(diào)查下一級節(jié)點自頂向下一層一層逐漸生成的寬度優(yōu)先搜索算法步1 ：把初始節(jié)點So放入OPEN表中。步2 ：假設(shè)OPEN表為空, 那么搜索失敗,退出。 步3 ：取OPEN表中前面第一個節(jié)點N放在CLOSED表中, 并冠以順序編號n。步4 ：假設(shè)目的節(jié)點Sg=N,那么搜索勝利, 終了。 步5 ：假設(shè)N不

5、可擴展, 那么轉(zhuǎn)步2。步6 ：擴展N, 將mj子節(jié)點配上指向N的指針依次放入OPEN表尾部, 轉(zhuǎn)步2。 注解：OPEN表是一個隊列CLOSED表是一個順序表，表中各節(jié)點按順序標(biāo)號，正在被調(diào)查的節(jié)點在表中編號最大假設(shè)問題有解，目的點Sg必出如今OPEN表中，算法終了根據(jù)前往指針，在CLOSED表中回溯，得到求解途徑開場把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表能否有后繼節(jié)點為目的節(jié)點？擴展n，把n的后繼節(jié)點放入OPEN表的末端，提供前往節(jié)點n的指針失敗勝利圖3.2 寬度優(yōu)先算法框圖是否是否 例子八數(shù)碼難題8-puzzle problem 12384567

6、12384567目的形狀規(guī)定：將牌移入空格的順序為：從空格左邊開場順時針旋轉(zhuǎn)。不許斜向挪動，也不前往先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解目的節(jié)點。12384567123841238456741238567123841238456712384567123845676789101112131238456756756711238456712384567123845671238456723451345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238

7、4567123845671238456712384567141516171819202112384567圖3.4 八數(shù)碼難題的寬度優(yōu)先搜索樹寬度優(yōu)先搜索算法寬度優(yōu)先/橫向搜索優(yōu)點戰(zhàn)略是完備的假設(shè)有解，一定找到解，且找到的解是最優(yōu)解(最短途徑)缺陷效率低節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+13.2.2 深度優(yōu)先搜索3.2.2 深度優(yōu)先搜索 定義 首先擴展最新產(chǎn)生的(即最深的)節(jié)點。 算法 防止搜索過程沿著無益的途徑擴展下去，往往給出一個節(jié)點擴展的最大深度深度界限。 與寬度優(yōu)先搜索算法最根本的不同在于：將擴展的后繼節(jié)點放在OPEN表的前端。算法框圖見教材深度優(yōu)先搜索Depth-fir

8、st search ，DFS在搜索樹的每一層一直只擴展一個子結(jié)點，不斷地向縱深前進直到不能再前進到達葉子結(jié)點或深度限制，才從當(dāng)前節(jié)點前往上一級節(jié)點，沿另一方向又繼續(xù)前進從樹根開場一枝一枝逐漸生成的途徑節(jié)點序列為(n0, n1,nk)對于i=1,k，假設(shè)節(jié)點ni-1具有一個后繼節(jié)點ni，該序列稱為從n0到nk的途徑n0nkn1nk-1n3n2深度優(yōu)先搜索算法縱向搜索缺陷假設(shè)一個有解的問題樹能夠有無窮分支，假設(shè)誤入無窮分支即深度無限，那么不能夠找到目的節(jié)點戰(zhàn)略不是完備的找到的解是不一定最優(yōu)解最短途徑)3.2.3 等代價搜索 定義 是寬度優(yōu)先搜索的一種推行，不是沿著等長度途徑斷層進展擴展，而是沿著等

9、代價途徑斷層進展擴展。 搜索樹中每條銜接弧線上的有關(guān)代價,表示時間、間隔等破費。 算法 假設(shè)一切銜接弧線具有相等代價，那么簡化為寬度優(yōu)先搜索算法。開場把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點i從OPEN表移至CLOSED表能否有后繼節(jié)點為目的節(jié)點？失敗勝利圖3.2 等代價搜索算法框圖是否是否S能否目的節(jié)點？是勝利擴展i，計算其后繼節(jié)點j的g(j)，并把后繼節(jié)點放入OPEN表否令g(s)=0國際象棋對弈程序:深藍開發(fā)者: IBM 的Murry Campbell, Feng-Hsiung Hsu 和Joseph Hoane采用30個IBM RS/6000處置器來運轉(zhuǎn)軟件搜索運

10、用480個定制VLSI國際象棋處置器執(zhí)行生成行棋的功能樹的最后幾層的硬件搜索以及對葉節(jié)點的評價.每秒平均搜索12.6億種走法，峰值時每秒鐘搜索33億個節(jié)點. 每走一步至多可以預(yù)先計算300億種個棋局, 常規(guī)搜索深度是14步.機器的中心算法是運用互換表的規(guī)范迭代深化-搜索, 而且對關(guān)鍵的點具備產(chǎn)生超越搜索深度的擴展才干,在某些情況下可以到達40層的深度.評價函數(shù)采用了超越8000個特征;運用一本有4000個棋局的開局手冊以及一個存有70萬個巨匠級競賽棋譜的數(shù)據(jù)庫; 運用一個大型殘局?jǐn)?shù)據(jù)庫保管已處理的棋局.Videov.youku/v_show/id_XMzk1MzQ0ODYw.html Deep

11、 Blue 15 yearsv.youku/v_show/id_XMTEyOTU5MjQ0.html 卡斯帕羅夫v.youku/v_show/id_XMzU4NzY0NzE2.html Windows 8v.youku/v_show/id_XMzE4MzM5OTA0.html Kinect問題的提出窮舉算法可以處理形狀空間很小的簡單問題大空間無法勝任：組合爆炸組合爆炸64階梵塔：節(jié)點：364=0.94*1030實際最短途徑：264-1=2*1019博弈一字棋：9！= 3.6*105西洋棋：1078國際象棋：10120極限并行速度10-104秒/步，需1016年圍棋：107613.3 啟發(fā)式搜索

12、啟發(fā)性信息按其用途劃分, 啟發(fā)性信息可分為以下三類： 用于擴展節(jié)點的選擇, 即用于決議應(yīng)先擴展哪一個節(jié)點, 以免盲目擴展。 用于生成節(jié)點的選擇,即用于決議應(yīng)生成哪些后續(xù)節(jié)點,以免盲目地生成過多無用節(jié)點。 用于刪除節(jié)點的選擇,即用于決議應(yīng)刪除哪些無用節(jié)點, 以免呵斥進一步的時空浪費。 3.3 啟發(fā)式搜索特點：重排OPEN表，選擇最有希望的節(jié)點加以擴展種類：有序搜索、A*算法等3.3.1 啟發(fā)式搜索戰(zhàn)略和估價函數(shù)盲目搜索能夠帶來組合爆炸啟發(fā)式信息 用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息。啟發(fā)函數(shù)啟發(fā)函數(shù)是用來估計搜索樹上節(jié)點x與目的節(jié)點Sg接近程度的一種函數(shù), 通常記為h(x)定義一個節(jié)點到目的

13、節(jié)點的某種間隔或差別的度量一個節(jié)點處于最正確途徑上的概率根據(jù)閱歷的客觀打分估價函數(shù) 為獲得某些節(jié)點“希望的啟發(fā)信息，提供一個評定侯選擴展節(jié)點的方法，以便確定哪個節(jié)點最有能夠在通向目的的最正確途徑上 。 f(n)表示節(jié)點n的估價函數(shù)值 運用節(jié)點“希望程度估價函數(shù)值重排OPEN表3.3.2 有序搜索本質(zhì) 選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。開場把S放入OPEN表，計算估價函數(shù) f (s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點i放入CLOSED表i為目的節(jié)點嗎？擴展i，得后繼節(jié)點j，計算f(j)，提供前往節(jié)點i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關(guān)系及指

14、針失敗勝利圖3.9 有序搜索算法框圖是否是否算法 例子八數(shù)碼難題8-puzzle problem12384567目的形狀12384567初始形狀八數(shù)碼難題的有序搜索樹見以下圖：123845671238456712384567466123845671238456712384567655123845671238456757123845671238456767123845675813245671238456757圖3.10 八數(shù)碼難題的有序搜索樹12384647啟發(fā)式搜索利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，到達減少搜索范圍，降低問題復(fù)雜度的目的在保證找到最正確解的情況下，盡能夠減少搜索范圍，提高搜索效

15、率啟發(fā)信息強降低搜索任務(wù)量，但能夠?qū)е抡也坏阶顑?yōu)解弱產(chǎn)生式系統(tǒng)在找到一條途徑之前將擴展過多的節(jié)點，普通導(dǎo)致任務(wù)量加大極限情況下盲目搜索，但能夠可以找到最優(yōu)解3.3.3 A*算法A*算法評價函數(shù) f(n) = g(n) + h(n)n是被評價的結(jié)點f(n)評價函數(shù)從s經(jīng)過n到g的途徑的耗散值g(n)代價函數(shù)從s到n的途徑的耗散值h(n)啟發(fā)函數(shù)從n到g的途徑的耗散值3.3.3 A*算法估價函數(shù)的定義：對節(jié)點n定義f*(n)=g*(n)+h*(n) ,表示從S開場約束經(jīng)過節(jié)點n的一條最正確途徑的代價。希望估價函數(shù)f 定義為：f(n)=g(n)+h(n) g是g*的估計 ，h是h*的估計A*算法的定

16、義：定義1 在GRAPHSEARCH過程中，假設(shè)第8步的重排OPEN表是根據(jù)f(x)=g(x)+h(x)進展的，那么稱該過程為A算法。 定義2 在A算法中，假設(shè)對一切的x存在h(x)h*(x),那么稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。 定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā?評價函數(shù)的計算gn根據(jù)已搜索的結(jié)果，按照從初始結(jié)點s到結(jié)點n的途徑，計算其耗散值即可g(n)對g*(n)作出估計，有g(shù)(n)g*(n)h(n)依賴于啟發(fā)信息，稱為啟發(fā)函數(shù)對未來擴展的方向作出估計f(n)按f(n)遞增的順序來陳列OP

17、EN表的節(jié)點，優(yōu)先擴展f(n)值小的節(jié)點，表達了好的優(yōu)先搜索思想3.3.3 A*算法八數(shù)碼2 8 31 6 47 51 2 38 47 6 5初始形狀八數(shù)碼評價函數(shù)f(n) = g(n) + h(n)g(n)：從初始節(jié)點到當(dāng)前節(jié)點的耗散值h(n)：當(dāng)前節(jié)點“不在位的將牌數(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

18、6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5S(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)124356g=0h=4f=4g=1h=5f=6g=1h=3f=4g=1h=5f=6g=2h=3f=5g=2h=3f=5g=2h=4f=6g=3h=2f=5g=3h=4f=7g=3h=4f=7g=3h=3f=6g=4h=2f=6g=5h=0f=5g=5h=2f=77目的A*算法A*算法在A算法中，假設(shè)滿足條件h(n)h*(n) h*(n)是從節(jié)點n到目的節(jié)點g的最小代價, 即最正確途徑上的實踐代價那么A算法稱為A*算法 A*算法h單調(diào)限制 一個啟發(fā)函數(shù)h，假設(shè)對一切節(jié)點ni和nj,滿足h(ni)-h(nj) c(ni, nj)h(g)=0那么稱h是單調(diào)的。 其中:nj是ni的子節(jié)點g是目的節(jié)點h(