人工智能原理

人工智能原理

第2章搜索技術(shù)

〔上〕1 本章內(nèi)容

2.1搜索與問題求解

2.2無信息搜索戰(zhàn)略

2.3啟發(fā)式搜索戰(zhàn)略

2.4部分搜索算法

2.5約束滿足問題

2.6博弈搜索

參考書目

附錄A*算法可采用性的證明第2章搜索技術(shù)22.1搜索與問題求解

2.1.1問題與問題的解

2.1.2問題實(shí)例

2.1.3搜索戰(zhàn)略第2章搜索技術(shù)3搜索與問題求解問題求解過程是搜索答案(目的)的過程/所以問題求解技術(shù)也叫搜索技術(shù)—經(jīng)過對形狀空間的搜索而求解問題的技術(shù)問題求解智能體是一種基于目的的智能體在尋覓到達(dá)目的的過程中，當(dāng)智能面子對多個(gè)未知的選項(xiàng)時(shí)，首先檢驗(yàn)各個(gè)不同的導(dǎo)致知評價(jià)的形狀的能夠行動(dòng)序列，然后選擇最正確序列—這個(gè)過程就是搜索第2章搜索技術(shù)42.1.1問題與問題的解問題可以方式化地定義為4個(gè)組成部分智能體的初始形狀(即搜索的開場)后繼函數(shù)—智能體采取的能夠行動(dòng)的描畫，通常為<行動(dòng)，后繼形狀>/初始形狀和后繼函數(shù)隱含地定義了問題的形狀空間/形狀空間中的一條途徑是經(jīng)過行動(dòng)序列銜接起來的一個(gè)形狀序列目的測試—檢查給定的形狀是不是目的途徑耗散函數(shù)—每條途徑都有一個(gè)數(shù)值化的耗散值，反映了性能度量/求解問題的代價(jià)第2章搜索技術(shù)5問題的解問題的解就是初始形狀到目的形狀的途徑解的優(yōu)劣由途徑耗散函數(shù)量度(代價(jià))最優(yōu)解就是途徑耗散函數(shù)值最小的途徑上述解題過程把處理一個(gè)問題的過程描畫出來，稱之為解題知識(shí)的過程性表示過程性知識(shí)與陳說性知識(shí)相對搜索過程解題的特點(diǎn)—沒有直接的方法(公式)可以求解，而是一步一步的探求第2章搜索技術(shù)6形狀空間數(shù)據(jù)基：代表了所要處理的問題，有初始形狀，能夠有目的形狀也能夠沒有形狀空間：在解題過程中的每一時(shí)辰，數(shù)據(jù)基都處于一定的形狀，數(shù)據(jù)基一切能夠形狀的集合稱為形狀空間有向圖：假設(shè)把每個(gè)形狀看成一個(gè)節(jié)點(diǎn)，那么整個(gè)形狀空間是一個(gè)有向圖/該圖不一定全連通，即從某些形狀不一定能到達(dá)另外一些形狀第2章搜索技術(shù)7問題的可解性可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將形狀改動(dòng)/假設(shè)從代表初始形狀的節(jié)點(diǎn)出發(fā)，有一條途徑通向目的形狀，那么稱此目的形狀所代表的問題在當(dāng)前初始形狀下是可解的搜索空間：在解題過程中到達(dá)過的一切形狀的集合，稱為搜索空間不同于形狀空間，搜索空間只是其中一部分形狀空間和搜索空間都屬于過程性知識(shí)表示第2章搜索技術(shù)82.1.2問題實(shí)例玩具問題八數(shù)碼游戲(九宮圖)河內(nèi)塔八皇后問題真空吸塵器世界現(xiàn)實(shí)問題游覽商問題超大規(guī)模集成電路的規(guī)劃自動(dòng)裝配排序/蛋白質(zhì)設(shè)計(jì)互聯(lián)網(wǎng)搜索第2章搜索技術(shù)9八數(shù)碼游戲八數(shù)碼游戲：1-8數(shù)字(棋子)/9個(gè)方格(棋盤格)/1個(gè)空格可用如下方式的規(guī)那么來表示數(shù)字經(jīng)過空格進(jìn)展挪動(dòng)：<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>共24條規(guī)那么=4角*2+4邊*3+1中間*4搜索順序舉例： (1)優(yōu)先挪動(dòng)行數(shù)小的棋子(數(shù)字) (2)同一行中優(yōu)先挪動(dòng)列數(shù)大的棋子約束規(guī)那么：不使分開既定位置的數(shù)字?jǐn)?shù)添加第2章搜索技術(shù)10八數(shù)碼游戲的搜索樹第2章搜索技術(shù)既定位置=終態(tài)11八數(shù)碼問題方式化初始形狀初始形狀向量—規(guī)定向量中各分量對應(yīng)的位置，各位置上的初始數(shù)字后繼函數(shù)挪動(dòng)規(guī)那么—按照某條規(guī)那么挪動(dòng)數(shù)字，將得到的新向量目的測試新向量能否是目的形狀(也是向量方式)途徑耗散函數(shù)每次挪動(dòng)代價(jià)為1第2章搜索技術(shù)12河內(nèi)塔(1)河內(nèi)塔問題：n個(gè)大小不等的圓盤從一個(gè)柱子移到另一個(gè)柱子，共有3個(gè)柱子(n階河內(nèi)塔問題)約束：從第1根柱子挪動(dòng)到第3根柱子上去，利用第2根柱子/每次挪動(dòng)1個(gè)盤子，且挪動(dòng)過程必需是小盤落大盤描畫：設(shè)每個(gè)形狀為(a1,a2,a3,…,an),ai=1,2,3—表示第i個(gè)盤子在第1/2/3根柱子上第2章搜索技術(shù)13河內(nèi)塔(2)遞歸定義：{(a1,a2,a3,…,an)}為n階河內(nèi)塔的形狀集合，那么{(a1,a2,a3,…,an,1),(a1,a2,a3,…,an,2),(a1,a2,a3,…,an,3)}是n+1階河內(nèi)塔的形狀集合1階河內(nèi)塔有3個(gè)形狀，2階河內(nèi)塔有9個(gè)形狀，n階河內(nèi)塔有3n個(gè)形狀，給出1/2/3階河內(nèi)塔的形狀圖第2章搜索技術(shù)14河內(nèi)塔問題圖解第2章搜索技術(shù)15河內(nèi)塔問題方式化初始形狀初始形狀向量—規(guī)定向量中各分量對應(yīng)一切n個(gè)盤子，位置上數(shù)字代表3個(gè)柱子之一后繼函數(shù)挪動(dòng)規(guī)那么—根據(jù)約束條件給出的各形狀的后繼形狀目的測試新向量能否是目的形狀(也是向量方式)途徑耗散函數(shù)每挪動(dòng)一個(gè)盤子的代價(jià)為1第2章搜索技術(shù)16河內(nèi)塔問題求解求最短途徑問題：形狀圖中從三角形1個(gè)頂點(diǎn)走到另一個(gè)頂點(diǎn)結(jié)論：(1)假設(shè)初始形狀或目的形狀在三角形頂點(diǎn)上，那么最短途徑獨(dú)一；(2)對于恣意2個(gè)形狀，最短求解途徑至多為2條。(中國某大學(xué)研討生證明)求解過程—對形狀空間的搜索—以2階河內(nèi)塔為例第2章搜索技術(shù)17河內(nèi)塔問題的搜索樹第2章搜索技術(shù)1,12,13,11,12,31,13,23,32,1×2,2××√3,12,2×1,32,13,3××2,33,31,21,1××√2,21,23,13,3××√2,23,21,31,1××√18求解過程—樹搜索求解問題的過程運(yùn)用搜索樹方式每個(gè)形狀對應(yīng)搜索樹中一個(gè)節(jié)點(diǎn)根節(jié)點(diǎn)對應(yīng)于初始形狀每次從搜索樹的上層節(jié)點(diǎn)出發(fā)，根據(jù)約束條件進(jìn)入下一個(gè)能夠的形狀，即展開新的一層樹節(jié)點(diǎn)—節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)展開的順序即代表了不同的搜索戰(zhàn)略當(dāng)展開的節(jié)點(diǎn)為目的形狀時(shí)，就找到了問題的一個(gè)解第2章搜索技術(shù)192.1.3搜索戰(zhàn)略研討搜索過程思索的假設(shè)干問題 (1)有限搜索還是無限搜索 (2)知目的還是未知目的 (3)目的或目的+途徑 (4)有約束還是無約束 (5)數(shù)據(jù)驅(qū)動(dòng)(向前搜索)還是目的驅(qū)動(dòng) (6)單向搜索還是雙向搜索第2章搜索技術(shù)20搜索的分類搜索過程的分類：形狀空間搜索(圖搜索方式)，問題空間搜索(層次方法)，博弈空間搜索無信息搜索與啟發(fā)式搜索啟發(fā)式：利用中間信息改良控制戰(zhàn)略啟發(fā)式：(1)任何有助于找到問題的解，但不能保證找到解的方法是啟發(fā)式方法(2)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)式方法啟發(fā)式也叫啟發(fā)函數(shù)第2章搜索技術(shù)21搜索算法的性能4種途徑來評價(jià)搜索算法的性能完備性—當(dāng)問題有解時(shí)，算法能否保證找到一個(gè)解最優(yōu)性—算法能否能找到一個(gè)最優(yōu)解(途徑耗散函數(shù)值最小的途徑)時(shí)間復(fù)雜性—找到一個(gè)解需求破費(fèi)多少時(shí)間空間復(fù)雜性—在搜索過程中需求占用多少內(nèi)存第2章搜索技術(shù)22性能量度時(shí)空復(fù)雜性的量度—由形狀空間圖的大小來衡量/相關(guān)度量如下：分支因子b (每次展開的平均節(jié)點(diǎn)個(gè)數(shù))目的節(jié)點(diǎn)的深度d途徑的最大長度m 搜索深度限制l搜索耗散第2章搜索技術(shù)232.2無信息搜索戰(zhàn)略

2.2.1廣度優(yōu)先搜索

2.2.2深度優(yōu)先搜索和深度有限搜索

2.2.3疊代深化深度優(yōu)先搜索

2.2.4無信息搜索戰(zhàn)略性能比較

2.2.5圖搜索算法第2章搜索技術(shù)24盲目搜索戰(zhàn)略無信息搜索也稱盲目搜索：沒有任何附加信息，只需生成后繼和區(qū)分目的與非目的形狀有5種盲目搜索戰(zhàn)略廣度優(yōu)先搜索代價(jià)一致搜索深度優(yōu)先搜索深度有限搜索迭代深化深度優(yōu)先搜索第2章搜索技術(shù)252.2.1廣度優(yōu)先搜索廣度優(yōu)先搜索過程：首先擴(kuò)展根節(jié)點(diǎn)接著擴(kuò)展根節(jié)點(diǎn)的一切后繼節(jié)點(diǎn)然后再擴(kuò)展后繼節(jié)點(diǎn)的后繼，依此類推在下一層任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上的本層深度的一切節(jié)點(diǎn)都曾經(jīng)被擴(kuò)展廣度優(yōu)先搜索可以調(diào)用樹搜索算法(Tree-Search)實(shí)現(xiàn)其參數(shù)fringe(邊緣/擴(kuò)展分支)為先進(jìn)先出隊(duì)列FIFO第2章搜索技術(shù)26樹搜索算法(1)functionTree-Search(problem,fringe)returnsolution/failure (initialfringe=empty,mode=FIFO) fringe←Insert(Make-Node(Initial-State[problem]),fringe) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=GoalthenreturnSolution(node) fringe←Insert-All(Expend(node,problem), fringe)第2章搜索技術(shù)27樹搜索算法(2)關(guān)鍵在于如何擴(kuò)展節(jié)點(diǎn)functionExpend(node,problem)returnsetofnodes successors←theemptyset foreach<action,result>inSuccessor-Find[problem](State[node])do s←newNode/State[s]←result Parent-Node[s]=node/Action[s]=action Path-Cost[s]=Path-Cost[node]+Step-Cost[node, action,s] Depth[s]←Depth[node]+1 addstosuccessors returnsuccessors第2章搜索技術(shù)28廣度優(yōu)先搜索的性能在上述算法中，廣度優(yōu)先搜索以Tree-Search(problem,FIFO-Queue)調(diào)用樹搜索算法從4種度量來評價(jià)廣度優(yōu)先搜索：完備性—總能找到一個(gè)解假設(shè)每步擴(kuò)展的耗散一樣時(shí)，廣度優(yōu)先搜索能找到最優(yōu)解內(nèi)存耗費(fèi)是比執(zhí)行時(shí)間耗費(fèi)更大的問題指數(shù)級的時(shí)間耗費(fèi)(空間和時(shí)間耗費(fèi)的例子參見p60圖3.11)第2章搜索技術(shù)292.2.2深度優(yōu)先搜索和深度有限搜索深度優(yōu)先搜索過程：總是擴(kuò)展搜索樹的當(dāng)前擴(kuò)展分支(邊緣)中最深的節(jié)點(diǎn)搜索直接伸展到搜索樹的最深層，直到那里的節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)那些沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)擴(kuò)展終了就從邊緣中去掉然后搜索算法回退下一個(gè)還有未擴(kuò)展后繼節(jié)點(diǎn)的上層節(jié)點(diǎn)繼續(xù)擴(kuò)展搜索算法參見深度有限搜索算法(l=∞)第2章搜索技術(shù)30深度優(yōu)先搜索的性能深度優(yōu)先搜索經(jīng)過后進(jìn)先出隊(duì)列LIFO(棧)調(diào)用Tree-Search實(shí)現(xiàn)/通常運(yùn)用遞歸函數(shù)實(shí)現(xiàn)，依次對當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)調(diào)用該函數(shù)性能：內(nèi)存需求少—如分支因子=b/最大深度=m的形狀空間深度優(yōu)先搜索只需求存儲(chǔ)bm+1個(gè)節(jié)點(diǎn)(比較廣度優(yōu)先O(bd+1))不是完備的/不是最優(yōu)的最壞情況下時(shí)間復(fù)雜性也很高O(bm)第2章搜索技術(shù)31深度有限搜索深度優(yōu)先搜索的無邊境問題可以經(jīng)過提供一個(gè)預(yù)先設(shè)定的深度限制l來處理深度=l的節(jié)點(diǎn)當(dāng)作無后繼節(jié)點(diǎn)對待雖然處理了無限途徑問題，但假設(shè)l<d那么找不到解假設(shè)選擇d>l那么深度優(yōu)先搜索也不是最優(yōu)的時(shí)間復(fù)雜度O(bl)空間復(fù)雜度O(bl)深度優(yōu)先搜索可看作是一種特例即l=∞第2章搜索技術(shù)32非遞歸的深度有限搜索算法functionDepth-Limited-Search(problem,fringe,limit)returnsolution/failure/cutoff fringe←Insert(Make-Node(Initial-State[problem]),fringe) (mode=LIFO) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=Goalthenreturn Solution(node) elseifDepth[node]=limitthenreturncutoff elsefringe←Insert-All(Expend (node,problem),fringe)第2章搜索技術(shù)33搜索步數(shù)的限制上面算法中能夠有兩類失敗cutoff表示到達(dá)了有限深度而無解failure表示普通的前往值無解有時(shí)深度有限搜索基于問題本身的知識(shí)，如形狀空間的直徑即問題求解的最大步數(shù)但對于大多數(shù)問題，不到問題處理時(shí)是無法知道求解步數(shù)的限制第2章搜索技術(shù)342.2.3疊代深化深度優(yōu)先搜索假設(shè)每次改動(dòng)限制深度，多次調(diào)用深度有限搜索算法，就得到了疊代深化深度優(yōu)先搜索算法其深度限制依次為0/1/2…這樣，當(dāng)搜索到達(dá)最淺的目的節(jié)點(diǎn)深度時(shí)就可以發(fā)現(xiàn)目的節(jié)點(diǎn)這種搜索結(jié)合了廣度優(yōu)先和深度優(yōu)先兩種算法的優(yōu)點(diǎn)(算法見p63)分支因子有限時(shí)是完備的/途徑耗散是節(jié)點(diǎn)深度的非遞增函數(shù)時(shí)是最優(yōu)的空間需求為O(bd)/時(shí)間復(fù)雜性為O(bd)第2章搜索技術(shù)35形狀的生成疊代深化搜索中由于多次反復(fù)搜索，因此部分形狀被多次生成，看起來很浪費(fèi)但是由于在分支因子比較平衡的搜索樹中，多數(shù)節(jié)點(diǎn)都在最底層(即葉子節(jié)點(diǎn))，所以上層節(jié)點(diǎn)的多次生成影響不是很大/與廣度優(yōu)先搜索相比，效率還是更高普通來講，當(dāng)搜索空間很大而解的深度未知時(shí)，疊代深化搜索是一個(gè)首選的無信息搜索方法第2章搜索技術(shù)362.2.4無信息搜索戰(zhàn)略比較第2章搜索技術(shù)評價(jià)標(biāo)準(zhǔn)廣度優(yōu)先代價(jià)一致深度優(yōu)先深度有限疊代深入雙向搜索是否完備時(shí)間空間是否最優(yōu)是A是A/B否否是A是A/D

O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)是C是否否是C是C/D關(guān)于A/B/C/D的解釋：A—假設(shè)b有限那么是完備的/B—單步耗散≥e那么是完備的/C—假設(shè)單步耗散都是一樣的那么是最優(yōu)的/D—兩個(gè)方向上都運(yùn)用廣度優(yōu)先搜索372.2.5圖搜索算法曾經(jīng)看到搜索過程中會(huì)出現(xiàn)反復(fù)的形狀擴(kuò)展，應(yīng)該防止/假設(shè)算法不檢測反復(fù)形狀的話，有能夠使一個(gè)本來可解的問題變?yōu)椴豢山鈾z測就是把要擴(kuò)展的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)進(jìn)展比較，把遇到的一樣形狀去掉所以要記錄曾經(jīng)擴(kuò)展的節(jié)點(diǎn)—引入兩個(gè)表—存儲(chǔ)已擴(kuò)展的節(jié)點(diǎn)closed表和未擴(kuò)展的節(jié)點(diǎn)open表(即前述fringe)新算法稱為圖搜索算法第2章搜索技術(shù)38圖搜索算法第2章搜索技術(shù)functionGraph-Search(problem,fringe)returnsolutionorfailure closed←emptyset fringe←Insert(Make-Node(Initial-State[problem]),fringe) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=GoalthenreturnSolution(node) ifState[node]!CLOSEDthen addState[node]toclosed fringe←Insert-All(Expend(node,problem),fringe)39圖搜索算法的性能由樹到圖：存在不同分支節(jié)點(diǎn)的合并圖搜索算法與樹搜索算法比較：只是添加了對展開節(jié)點(diǎn)的判別，因此由不同的待擴(kuò)展節(jié)點(diǎn)陳列方式而構(gòu)成的搜索戰(zhàn)略(如廣度優(yōu)先和深度優(yōu)先)的性能依然同樹搜索算法對于含很多反復(fù)形狀的問題，其搜索效率比樹搜索算法有效很多討論參見p67第2章搜索技術(shù)40例子：“農(nóng)夫過河〞問題搜索農(nóng)夫過河問題用向量<人,狼,羊,白菜>表示在河岸兩邊的情況0表示此岸/1表示此岸過河規(guī)那么有8條(隱含了約束條件)1(0,*,*,*)→(1,*,*,*)/2(0,0,*,*)→(1,1,*,*) 3(0,*,0,*)→(1,*,1,*)/4(0,*,*,0)→(1,*,*,1) 5(1,*,*,*)→(0,*,*,*)/6(1,1,*,*)→(0,0,*,*)7(1,*,1,*)→(0,*,0,*)/8(1,*,*,1)→(0,*,*,0) *=0/1表示恣意岸邊但必需一樣第2章搜索技術(shù)41“農(nóng)夫過河〞—廣度優(yōu)先搜索第2章搜索技術(shù)000010101100×00101110010011010101111110110001closed表<0000><1010><0010><1110><1011><0100><0001><1101>所用規(guī)那么序列3/5/4/7/2所用規(guī)那么序列3/5/2/7/4所用規(guī)那么序列3/5/4/7/2/5/3所用規(guī)那么序列3/5/2/7/4/5/342“農(nóng)夫過河〞—深度優(yōu)先搜索第2章搜索技術(shù)000010101100×001011100100110101011111closed表<0000><1010><0010><1110><0100><1101>所用規(guī)那么序列3/5/2/7/4所用規(guī)那么序列3/5/2/7/4/5/3只運(yùn)用一個(gè)搜索分支/所擴(kuò)展的第一個(gè)節(jié)點(diǎn)是最新節(jié)點(diǎn)432.3啟發(fā)式搜索戰(zhàn)略

2.3.1貪婪最正確優(yōu)先搜索

2.3.2A*搜索

2.3.3啟發(fā)函數(shù)

2.3.4聯(lián)機(jī)搜索第2章搜索技術(shù)44啟發(fā)式搜索通用算法啟發(fā)式搜索也稱有信息搜索，其通用算法稱為最正確優(yōu)先搜索(Best-First-Search)最正確優(yōu)先搜索基于評價(jià)函數(shù)擴(kuò)展節(jié)點(diǎn)—按照間隔目的最短的評價(jià)值來擴(kuò)展并不是真正的最正確—只是表現(xiàn)得最正確/近似最正確算法的關(guān)鍵要素是啟發(fā)函數(shù)(Heuristicfunction)，記為f(n)/f(n)=從節(jié)點(diǎn)n到目的節(jié)點(diǎn)的最低耗散途徑的耗散估計(jì)值啟發(fā)函數(shù)引導(dǎo)搜索兩種方式—貪婪最正確優(yōu)先搜索/A*搜索(A*算法)第2章搜索技術(shù)452.3.1貪婪最正確優(yōu)先搜索貪婪最正確優(yōu)先搜索的評價(jià)函數(shù)f(n)=h(n)在貪婪最正確優(yōu)先搜索中總是選擇當(dāng)前離目的最近(最小代價(jià))的節(jié)點(diǎn)進(jìn)展擴(kuò)展(搜索)部分最正確未必全局最正確—不是最優(yōu)的(下例)運(yùn)用貪婪最正確優(yōu)先搜索算法搜索從Arad到首都的行車最短道路Arad的下一站有3個(gè)城市S(253)/T(329)/Z(374)→擴(kuò)展Sibiu有3個(gè)城市F(176)/O(380)/R(193)→擴(kuò)展Fagaras直接可到目的地然而實(shí)踐不是最優(yōu)的：S→F→B實(shí)踐全長310/S→RV→P→B實(shí)踐全長278，多了32km第2章搜索技術(shù)46問題實(shí)例—Romania公路圖第2章搜索技術(shù)47問題實(shí)例(1)第2章搜索技術(shù)尋覓從Arad到首都的行車最短道路評價(jià)函數(shù)f(n)=h(n)直線間隔啟發(fā)式hSLD與實(shí)踐間隔相關(guān)但需另外給出，見下表Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti100Eforie161RimnicuVilcea193Fagaras176Sibiu253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind37448問題實(shí)例(2)第2章搜索技術(shù)啟發(fā)函數(shù)h(n)最小化會(huì)對錯(cuò)誤的起點(diǎn)比較敏感例子：地圖中Iasi到Fagaras的行車道路(走入死路的能夠)需求仔細(xì)檢查反復(fù)形狀，否那么能夠永遠(yuǎn)找不到解與深度優(yōu)先搜索類似，非最優(yōu)、非完備最壞情況下時(shí)空復(fù)雜度都是O(bm)/m為最大搜索深度492.3.2A*搜索A*搜索的評價(jià)函數(shù)為f(n)=g(h)+h(n)g(n)是從初始節(jié)點(diǎn)到該節(jié)點(diǎn)n的途徑耗散h(n)是從節(jié)點(diǎn)n到目的節(jié)點(diǎn)的最低耗散途徑的估計(jì)耗散值，稱為啟發(fā)式或啟發(fā)函數(shù)因此，f(n)=經(jīng)過節(jié)點(diǎn)n、具有最低耗散值的解的估計(jì)耗散找到g(n)+h(n)值最小的節(jié)點(diǎn)當(dāng)然是合理的(參見書中p79圖4.3對于地圖的搜索)假設(shè)啟發(fā)函數(shù)h(n)滿足一定條件，那么A*搜索是完備的和最優(yōu)的第2章搜索技術(shù)50搜索算法的可采用性[定義]搜索算法的可采用性(可采用性)(Hart,Nilsson,Raphel,1968)假設(shè)形狀空間中的目的形狀存在，并且從初始形狀到目的形狀有一條通路，而搜索算法一定能在有限步內(nèi)終止并找到一個(gè)最優(yōu)解(代價(jià)最低)，那么這個(gè)形狀空間搜索算法稱為可采用的對于A*搜索來說，運(yùn)用樹搜索算法(Tree-Search)，那么它是可采用的假設(shè)對啟發(fā)函數(shù)h(n)作一定限制，那么運(yùn)用圖搜索算法(Graph-Search)也是可采用的第2章搜索技術(shù)51可采用的啟發(fā)函數(shù)算法的可采用性取決于啟發(fā)函數(shù)的可采用性啟發(fā)函數(shù)h(n)是可采用的—h(n)從來不會(huì)過高地估計(jì)到達(dá)目的的耗散值此即—h(n)滿足h(n)≤h*(n)，h*(n)是從當(dāng)前節(jié)點(diǎn)n到達(dá)目的的最低耗散值此即—f(n)永遠(yuǎn)不會(huì)高估經(jīng)過節(jié)點(diǎn)n的解的實(shí)踐耗散—f(n)≤f*(n)，所以是最優(yōu)解假設(shè)h(n)是可采用的，那么運(yùn)用Tree-Search的A*算法是可采用的(最優(yōu)的)本人嘗試證明，參考附錄證明過程第2章搜索技術(shù)52A*搜索的Tree-Search算法functionTree-Search(problem,fringe)returnsolutionorfailure Selecth(n) Make-Node(Initial-State[problem]&gettheirf(n) Insert(nodes,fringe) Sort(fringe,f(n)) dowhile(1) iffringe=Emptythenreturnfailure node←Remove-First(fringe) ifState[node]=GoalthenreturnSolution(node) Expend(node,problem)&gettheirf(n) Insert(nodes,fringe) Sort(fringe,f(n))第2章搜索技術(shù)53A*搜索的Graph-Search算法假設(shè)A*搜索運(yùn)用圖搜索算法，那么A*必然前往最優(yōu)解的結(jié)論就不成立—緣由是假設(shè)最優(yōu)途徑不是第一個(gè)生成的，能夠由于有反復(fù)形狀而被丟棄處理方案：1)修正Graph-Search算法使得可以進(jìn)展比較，只丟棄耗散值大的途徑2)保證到達(dá)任何反復(fù)形狀的最優(yōu)途徑總是第一條被跟隨的途徑—要求h(n)堅(jiān)持一致性(單調(diào)性)算法—請自行給出第2章搜索技術(shù)54h(n)的一致性(1)[定義]啟發(fā)函數(shù)的一致性—假設(shè)對于每個(gè)節(jié)點(diǎn)n和經(jīng)過恣意行動(dòng)a生成n的每個(gè)后繼節(jié)點(diǎn)n’，從節(jié)點(diǎn)n到達(dá)目的節(jié)點(diǎn)的估計(jì)耗散值h(n)不大于從n到n’的單步耗散與從n’到目的節(jié)點(diǎn)的估計(jì)耗散值之和，那么h(n)稱為一致的此即h(n)≤c(n,n’,a)+h(n’)/是三角不等式的某種方式每個(gè)一致的啟發(fā)函數(shù)都是可采用的證明要點(diǎn)：h(n)≤c(n,n’,a)+h(n’),h(n)≤c*(n,n’,a)+h(n’)可得h(n)–h*(n)≤h(n’)–h*(n’)目的節(jié)點(diǎn)h(T)=h*(T)=0回退可得恣意節(jié)點(diǎn)h(n)≤h*(n)第2章搜索技術(shù)55h(n)的一致性(2)通常我們選擇的啟發(fā)函數(shù)h(n)都滿足一致性要求(因此必定是可采用的)關(guān)于一致性的結(jié)論：假設(shè)h(n)是一致的，那么運(yùn)用Graph-Search的A*算法是最優(yōu)的附錄證明似乎沒有利用此條件假設(shè)h(n)是一致的，那么沿著任何途徑的f(n)值是非遞減的(由一致性定義可得)f(n)耗散值沿著任何途徑都是非遞減的結(jié)論允許在形狀空間中畫出等值線(見以下圖)第2章搜索技術(shù)56道路里程的等值線第2章搜索技術(shù)ZTLMDCGUONIVHE420A380BFPRS40057A*搜索節(jié)點(diǎn)的擴(kuò)展A*搜索由初始節(jié)點(diǎn)出發(fā)開場搜索，以同心帶狀增長f(n)耗散值的方式擴(kuò)展節(jié)點(diǎn)假設(shè)h(n)=0那么為代價(jià)一致搜索(只按g(n)值排序)那么同心帶為“圓型〞，運(yùn)用啟發(fā)函數(shù)那么同心帶向目的節(jié)點(diǎn)方向拉伸假設(shè)C*是最優(yōu)解途徑的耗散值，那么有以下結(jié)論：A*算法擴(kuò)展一切f(n)≤C*的節(jié)點(diǎn)A*算法在到達(dá)目的節(jié)點(diǎn)之前能夠會(huì)擴(kuò)展一些正益處于“目的等值線〞上的節(jié)點(diǎn)A*算法不擴(kuò)展f(n)>C*的節(jié)點(diǎn)(均被剪枝)第2章搜索技術(shù)58A*算法的性質(zhì)(1)A*算法是完備的—假設(shè)解存在，就一定能找到/由于找到解只需有限步A*算法是最優(yōu)的—即可采用的(一個(gè)普遍采用的證明見附錄)A*算法對于任何給定的啟發(fā)函數(shù)都是效率最優(yōu)的/沒有任何其他算法擴(kuò)展的節(jié)點(diǎn)少于A*算法但是，A*算法對于多數(shù)問題來說，搜索空間處于目的等值線內(nèi)的節(jié)點(diǎn)數(shù)量是求解途徑長度的指數(shù)級第2章搜索技術(shù)59A*算法的性質(zhì)(2)假設(shè)要求不以指數(shù)級增長，那么啟發(fā)函數(shù)需求滿足條件對于幾乎一切的啟發(fā)函數(shù)來說，偏向至少都是與途徑耗散成正比的，而不是途徑耗散的對數(shù)/所以，在實(shí)踐運(yùn)用中，往往不是堅(jiān)持找到最優(yōu)解，而是采用以下兩種方式：運(yùn)用A*算法的變種算法快速找到非最優(yōu)解設(shè)計(jì)準(zhǔn)確而非嚴(yán)厲可采用的啟發(fā)函數(shù)第2章搜索技術(shù)60A*算法在空間方面的改良A*算法在內(nèi)存中保管一切生成的節(jié)點(diǎn)，耗費(fèi)極大—因此對于許多大規(guī)模問題時(shí)不適用的A*算法要減少對內(nèi)存的需求—改良遞歸最正確優(yōu)先搜索RBFS—模擬規(guī)范的最正確優(yōu)先搜索的遞歸算法，只是用線性存儲(chǔ)空間假設(shè)h(n)是可采用的，那么RBFS最優(yōu)MA*(存儲(chǔ)限制A*)和SMA*(簡化的MA*)—充分利用可用的內(nèi)存SMA*的思想—當(dāng)內(nèi)存放滿時(shí)，就丟棄最差的一個(gè)子節(jié)點(diǎn)而參與新節(jié)點(diǎn)假設(shè)任何最優(yōu)解是可到達(dá)的，那么SMA*是最優(yōu)的第2章搜索技術(shù)612.3.3啟發(fā)函數(shù)A*搜索的關(guān)鍵就是設(shè)計(jì)可采用的或者一致的(單調(diào)的)啟發(fā)函數(shù)如何評價(jià)啟發(fā)函數(shù)/如何設(shè)計(jì)啟發(fā)函數(shù)例子—八數(shù)碼問題關(guān)于八數(shù)碼問題的一些數(shù)據(jù)：隨機(jī)產(chǎn)生的八數(shù)碼游戲的平均解的步數(shù)=22分支因子約為3窮舉搜索(盲目搜索)思索的形狀個(gè)數(shù)322≈3.1*1010實(shí)踐可到達(dá)的不同形狀個(gè)數(shù)9!/2=181440第2章搜索技術(shù)62八數(shù)碼問題的啟發(fā)函數(shù)啟發(fā)函數(shù)的中心—決不高估到達(dá)目的的步數(shù)/對于八數(shù)碼問題的常用候選：h1(n)=不在位棋子數(shù)—這是一個(gè)可采用的啟發(fā)函數(shù)，由于要把“不在位〞的棋子都挪動(dòng)到正確位置上，每個(gè)錯(cuò)位的棋子至少要挪動(dòng)一次/所以有h1(n)≤h*(n)h2(n)=一切棋子到達(dá)其目的位置的間隔和—計(jì)算程度間隔(曼哈頓間隔)/該函數(shù)也是可采用的，由于到達(dá)其目的位置至少要挪動(dòng)這些間隔長度第2章搜索技術(shù)63啟發(fā)函數(shù)準(zhǔn)確度對算法性能的影響描寫啟發(fā)函數(shù)質(zhì)量的一個(gè)度量是有效分支因子b*b*是深度為d的一致搜索樹為了可以包括N(生成的總節(jié)點(diǎn)數(shù))+1個(gè)節(jié)點(diǎn)所必需的分支因子N+1=1+b*+(b*)2+……+(b*)d例如：52個(gè)節(jié)點(diǎn)在第5層找到解，那么b*=1.92有效分支因子可以根據(jù)問題實(shí)例發(fā)生變化，但是在足夠難的問題中是穩(wěn)定的/因此小規(guī)模實(shí)驗(yàn)中測得b*值可以為啟發(fā)函數(shù)的總體有效性提供指點(diǎn)第2章搜索技術(shù)64八數(shù)碼問題啟發(fā)函數(shù)的比較良好設(shè)計(jì)的啟發(fā)函數(shù)使b*值接近1，允許對大規(guī)模的問題進(jìn)展求解啟發(fā)函數(shù)越接近于真實(shí)最優(yōu)解的值，那么相應(yīng)的搜索算法效率越高/顯然此時(shí)有—假設(shè)h1(n)≤h2(n)，那么h2(n)優(yōu)于h1(n)(此時(shí)h2(n)信息量比h1(n)多)p85頁給出了八數(shù)碼問題的啟發(fā)函數(shù)h1/h2的比較數(shù)據(jù)“優(yōu)于〞的含義—運(yùn)用h2的算法不會(huì)比運(yùn)用h1的算法擴(kuò)展更多的節(jié)點(diǎn)第2章搜索技術(shù)65如何設(shè)計(jì)啟發(fā)函數(shù)A*搜索的關(guān)鍵如何找到是一個(gè)適宜的啟發(fā)函數(shù)尋覓戰(zhàn)略：從松弛問題中獲得—松弛問題的最優(yōu)解的耗散是原問題的一個(gè)可采用的啟發(fā)函數(shù)從給定問題子問題的解耗散中獲得—建立方式數(shù)據(jù)庫，存儲(chǔ)每個(gè)能夠子問題實(shí)例從閱歷中學(xué)習(xí)—運(yùn)用歸納學(xué)習(xí)算法，運(yùn)用相關(guān)形狀特征來預(yù)測第2章搜索技術(shù)66松弛問題最優(yōu)解作為啟發(fā)函數(shù)松弛問題—降低了行動(dòng)限制的問題松弛問題的最優(yōu)解耗散是原問題的一個(gè)可采用的啟發(fā)函數(shù)根據(jù)定義，原始問題的最優(yōu)解也是該松弛問題的解，其耗散不低于松弛問題的最優(yōu)解松弛問題的最優(yōu)解是確切耗散，一定滿足三角不等式，因此是單調(diào)的，所以作為啟發(fā)函數(shù)一定是可采用的假設(shè)問題定義經(jīng)過方式化言語描畫，那么自動(dòng)地構(gòu)造