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

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

3、的規(guī)那么序列問(wèn)題就等價(jià)于求得圖中的一條途徑問(wèn)題。圖組成節(jié)點(diǎn)有向邊圖分類(lèi)或圖直接圖、形狀圖與或圖圖搜索過(guò)程圖圖形狀圖搜索戰(zhàn)略CLOSED 表：用來(lái)記錄調(diào)查過(guò)的節(jié)點(diǎn)對(duì)樹(shù)形搜索，存儲(chǔ)的是搜索樹(shù)對(duì)線式搜索，存儲(chǔ)的是折線OPEN表：記錄待調(diào)查的節(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表開(kāi)場(chǎng)把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目的節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供前往節(jié)點(diǎn)n的指針修正指針?lè)较蛑嘏臤PEN表失敗勝利圖3.1 圖搜索過(guò)程框圖是是否否3.2 盲目搜索 特點(diǎn)：不需重排OPEN表種類(lèi)：

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

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

6、12384567目的形狀規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_(kāi)場(chǎng)順時(shí)針旋轉(zhuǎn)。不許斜向挪動(dòng)，也不前往先輩節(jié)點(diǎn)。從圖可見(jiàn)，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解目的節(jié)點(diǎn)。12384567123841238456741238567123841238456712384567123845676789101112131238456756756711238456712384567123845671238456723451345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238

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

8、st search ，DFS在搜索樹(shù)的每一層一直只擴(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)從樹(shù)根開(kāi)場(chǎng)一枝一枝逐漸生成的途徑節(jié)點(diǎn)序列為(n0, n1,nk)對(duì)于i=1,k，假設(shè)節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，該序列稱(chēng)為從n0到nk的途徑n0nkn1nk-1n3n2深度優(yōu)先搜索算法縱向搜索缺陷假設(shè)一個(gè)有解的問(wèn)題樹(shù)能夠有無(wú)窮分支，假設(shè)誤入無(wú)窮分支即深度無(wú)限，那么不能夠找到目的節(jié)點(diǎn)戰(zhàn)略不是完備的找到的解是不一定最優(yōu)解最短途徑)3.2.3 等代價(jià)搜索 定義 是寬度優(yōu)先搜索的一種推行，不是沿著等長(zhǎng)度途徑斷層進(jìn)展擴(kuò)展，而是沿著等

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

10、用480個(gè)定制VLSI國(guó)際象棋處置器執(zhí)行生成行棋的功能樹(shù)的最后幾層的硬件搜索以及對(duì)葉節(jié)點(diǎn)的評(píng)價(jià).每秒平均搜索12.6億種走法，峰值時(shí)每秒鐘搜索33億個(gè)節(jié)點(diǎn). 每走一步至多可以預(yù)先計(jì)算300億種個(gè)棋局, 常規(guī)搜索深度是14步.機(jī)器的中心算法是運(yùn)用互換表的規(guī)范迭代深化-搜索, 而且對(duì)關(guān)鍵的點(diǎn)具備產(chǎn)生超越搜索深度的擴(kuò)展才干,在某些情況下可以到達(dá)40層的深度.評(píng)價(jià)函數(shù)采用了超越8000個(gè)特征;運(yùn)用一本有4000個(gè)棋局的開(kāi)局手冊(cè)以及一個(gè)存有70萬(wàn)個(gè)巨匠級(jí)競(jìng)賽棋譜的數(shù)據(jù)庫(kù); 運(yùn)用一個(gè)大型殘局?jǐn)?shù)據(jù)庫(kù)保管已處理的棋局.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問(wèn)題的提出窮舉算法可以處理形狀空間很小的簡(jiǎn)單問(wèn)題大空間無(wú)法勝任：組合爆炸組合爆炸64階梵塔：節(jié)點(diǎn)：364=0.94*1030實(shí)際最短途徑：264-1=2*1019博弈一字棋：9！= 3.6*105西洋棋：1078國(guó)際象棋：10120極限并行速度10-104秒/步，需1016年圍棋：107613.3 啟發(fā)式搜索

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

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

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

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

16、義：定義1 在GRAPHSEARCH過(guò)程中，假設(shè)第8步的重排OPEN表是根據(jù)f(x)=g(x)+h(x)進(jìn)展的，那么稱(chēng)該過(guò)程為A算法。 定義2 在A算法中，假設(shè)對(duì)一切的x存在h(x)h*(x),那么稱(chēng)h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。 定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱(chēng)為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?評(píng)價(jià)函數(shù)的計(jì)算gn根據(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ā)信息，稱(chēng)為啟發(fā)函數(shù)對(duì)未來(lái)擴(kuò)展的方向作出估計(jì)f(n)按f(n)遞增的順序來(lái)陳列OP

17、EN表的節(jié)點(diǎn)，優(yōu)先擴(kuò)展f(n)值小的節(jié)點(diǎn)，表達(dá)了好的優(yōu)先搜索思想3.3.3 A*算法八數(shù)碼2 8 31 6 47 51 2 38 47 6 5初始形狀八數(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

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é)點(diǎn)n到目的節(jié)點(diǎn)g的最小代價(jià), 即最正確途徑上的實(shí)踐代價(jià)那么A算法稱(chēng)為A*算法 A*算法h單調(diào)限制 一個(gè)啟發(fā)函數(shù)h，假設(shè)對(duì)一切節(jié)點(diǎn)ni和nj,滿足h(ni)-h(nj) c(ni, nj)h(g)=0那么稱(chēng)h是單調(diào)的。 其中:nj是ni的子節(jié)點(diǎn)g是目的節(jié)點(diǎn)h(