人工智能原理之搜索技術

人工智能原理

第2章搜索技術

（上）

1

本章內(nèi)容

2.1搜索與問題求解

2.2無信息搜索策略

2.3啟發(fā)式搜索策略

2.4局部搜索算法

2.5約束滿足問題

2.6博弈搜索

參考書目

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

2.1.1問題與問題的解

2.1.2問題實例

2.1.3搜索策略第2章搜索技術3搜索與問題求解問題求解過程是搜索答案(目標)的過程/所以問題求解技術也叫搜索技術—通過對狀態(tài)空間的搜索而求解問題的技術問題求解智能體是一種基于目標的智能體在尋找到達目標的過程中，當智能體面對多個未知的選項時，首先檢驗各個不同的導致已知評價的狀態(tài)的可能行動序列，然后選擇最佳序列—這個過程就是搜索第2章搜索技術42.1.1問題與問題的解問題可以形式化地定義為4個組成部分智能體的初始狀態(tài)(即搜索的開始)后繼函數(shù)—智能體采取的可能行動的描述，通常為<行動，后繼狀態(tài)>/初始狀態(tài)和后繼函數(shù)隱含地定義了問題的狀態(tài)空間/狀態(tài)空間中的一條路徑是通過行動序列連接起來的一個狀態(tài)序列目標測試—檢查給定的狀態(tài)是不是目標路徑耗散函數(shù)—每條路徑都有一個數(shù)值化的耗散值，反映了性能度量/求解問題的代價第2章搜索技術5問題的解問題的解就是初始狀態(tài)到目標狀態(tài)的路徑解的優(yōu)劣由路徑耗散函數(shù)量度(代價)最優(yōu)解就是路徑耗散函數(shù)值最小的路徑上述解題過程把解決一個問題的過程描述出來，稱之為解題知識的過程性表示過程性知識與陳述性知識相對搜索過程解題的特點—沒有直接的方法(公式)可以求解，而是一步一步的探索第2章搜索技術6狀態(tài)空間數(shù)據(jù)基：代表了所要解決的問題，有初始狀態(tài)，可能有目標狀態(tài)也可能沒有狀態(tài)空間：在解題過程中的每一時刻，數(shù)據(jù)基都處于一定的狀態(tài)，數(shù)據(jù)基所有可能狀態(tài)的集合稱為狀態(tài)空間有向圖：若把每個狀態(tài)看成一個節(jié)點，則整個狀態(tài)空間是一個有向圖/該圖不一定全連通，即從某些狀態(tài)不一定能到達另外一些狀態(tài)第2章搜索技術7問題的可解性可解的：在每個連通部分，每個弧代表一個運算符，將狀態(tài)改變/如果從代表初始狀態(tài)的節(jié)點出發(fā)，有一條路徑通向目標狀態(tài)，則稱此目標狀態(tài)所代表的問題在當前初始狀態(tài)下是可解的搜索空間：在解題過程中達到過的所有狀態(tài)的集合，稱為搜索空間不同于狀態(tài)空間，搜索空間只是其中一部分狀態(tài)空間和搜索空間都屬于過程性知識表示第2章搜索技術82.1.2問題實例玩具問題八數(shù)碼游戲(九宮圖)河內(nèi)塔八皇后問題真空吸塵器世界現(xiàn)實問題旅行商問題超大規(guī)模集成電路的布局自動裝配排序/蛋白質設計互聯(lián)網(wǎng)搜索第2章搜索技術9八數(shù)碼游戲八數(shù)碼游戲：1-8數(shù)字(棋子)/9個方格(棋盤格)/1個空格可用如下形式的規(guī)則來表示數(shù)字通過空格進行移動：<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)先移動行數(shù)小的棋子(數(shù)字) (2)同一行中優(yōu)先移動列數(shù)大的棋子約束規(guī)則：不使離開既定位置的數(shù)字數(shù)增加第2章搜索技術10八數(shù)碼游戲的搜索樹第2章搜索技術既定位置=終態(tài)11八數(shù)碼問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應的位置，各位置上的初始數(shù)字后繼函數(shù)移動規(guī)則—按照某條規(guī)則移動數(shù)字，將得到的新向量目標測試新向量是否是目標狀態(tài)(也是向量形式)路徑耗散函數(shù)每次移動代價為1第2章搜索技術12河內(nèi)塔(1)河內(nèi)塔問題：n個大小不等的圓盤從一個柱子移到另一個柱子，共有3個柱子(n階河內(nèi)塔問題)約束：從第1根柱子移動到第3根柱子上去，利用第2根柱子/每次移動1個盤子，且移動過程必須是小盤落大盤描述：設每個狀態(tài)為(a1,a2,a3,…,an),

ai=1,2,3—表示第i個盤子在第1/2/3根柱子上第2章搜索技術13河內(nèi)塔(2)遞歸定義：{(a1,a2,a3,…,an)}為n階河內(nèi)塔的狀態(tài)集合，則{(a1,a2,a3,…,an,1),(a1,a2,a3,…,an,2),(a1,a2,a3,…,an,3)}是n+1階河內(nèi)塔的狀態(tài)集合1階河內(nèi)塔有3個狀態(tài)，2階河內(nèi)塔有9個狀態(tài)，n階河內(nèi)塔有3n個狀態(tài)，給出1/2/3階河內(nèi)塔的狀態(tài)圖第2章搜索技術14河內(nèi)塔問題圖解第2章搜索技術15河內(nèi)塔問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應所有n個盤子，位置上數(shù)字代表3個柱子之一后繼函數(shù)移動規(guī)則—依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài)目標測試新向量是否是目標狀態(tài)(也是向量形式)路徑耗散函數(shù)每移動一個盤子的代價為1第2章搜索技術16河內(nèi)塔問題求解求最短路徑問題：狀態(tài)圖中從三角形1個頂點走到另一個頂點結論：(1)如果初始狀態(tài)或目標狀態(tài)在三角形頂點上，則最短路徑唯一；(2)對于任意2個狀態(tài)，最短求解路徑至多為2條。(中國某大學研究生證明)求解過程—對狀態(tài)空間的搜索—以2階河內(nèi)塔為例第2章搜索技術17河內(nèi)塔問題的搜索樹第2章搜索技術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求解過程—樹搜索求解問題的過程使用搜索樹形式每個狀態(tài)對應搜索樹中一個節(jié)點根節(jié)點對應于初始狀態(tài)每次從搜索樹的上層節(jié)點出發(fā)，根據(jù)約束條件進入下一個可能的狀態(tài)，即展開新的一層樹節(jié)點—節(jié)點擴展節(jié)點展開的順序即代表了不同的搜索策略當展開的節(jié)點為目標狀態(tài)時，就找到了問題的一個解第2章搜索技術192.1.3搜索策略研究搜索過程考慮的若干問題 (1)有限搜索還是無限搜索 (2)已知目標還是未知目標 (3)目標或目標+路徑 (4)有約束還是無約束 (5)數(shù)據(jù)驅動(向前搜索)還是目標驅動 (6)單向搜索還是雙向搜索第2章搜索技術20搜索的分類搜索過程的分類：狀態(tài)空間搜索(圖搜索方式)，問題空間搜索(層次方法)，博弈空間搜索無信息搜索與啟發(fā)式搜索啟發(fā)式：利用中間信息改進控制策略啟發(fā)式：(1)任何有助于找到問題的解，但不能保證找到解的方法是啟發(fā)式方法(2)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)式方法啟發(fā)式也叫啟發(fā)函數(shù)第2章搜索技術21搜索算法的性能4種途徑來評價搜索算法的性能完備性—當問題有解時，算法是否保證找到一個解最優(yōu)性—算法是否能找到一個最優(yōu)解(路徑耗散函數(shù)值最小的路徑)時間復雜性—找到一個解需要花費多少時間空間復雜性—在搜索過程中需要占用多少內(nèi)存第2章搜索技術22性能量度時空復雜性的量度—由狀態(tài)空間圖的大小來衡量/相關度量如下：分支因子b (每次展開的平均節(jié)點個數(shù))目標節(jié)點的深度d路徑的最大長度m 搜索深度限制l搜索耗散第2章搜索技術232.2無信息搜索策略

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

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

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

2.2.4無信息搜索策略性能比較

2.2.5圖搜索算法第2章搜索技術24盲目搜索策略無信息搜索也稱盲目搜索：沒有任何附加信息，只有生成后繼和區(qū)分目標與非目標狀態(tài)有5種盲目搜索策略廣度優(yōu)先搜索代價一致搜索深度優(yōu)先搜索深度有限搜索迭代深入深度優(yōu)先搜索第2章搜索技術252.2.1廣度優(yōu)先搜索廣度優(yōu)先搜索過程：首先擴展根節(jié)點接著擴展根節(jié)點的所有后繼節(jié)點然后再擴展后繼節(jié)點的后繼，依此類推在下一層任何節(jié)點擴展之前搜索樹上的本層深度的所有節(jié)點都已經(jīng)被擴展廣度優(yōu)先搜索可以調(diào)用樹搜索算法(Tree-Search)實現(xiàn)其參數(shù)fringe(邊緣/擴展分支)為先進先出隊列FIFO第2章搜索技術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章搜索技術27樹搜索算法(2)關鍵在于如何擴展節(jié)點function

Expend(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章搜索技術28廣度優(yōu)先搜索的性能在上述算法中，廣度優(yōu)先搜索以Tree-Search(problem,FIFO-Queue)調(diào)用樹搜索算法從4種度量來評價廣度優(yōu)先搜索：完備性—總能找到一個解如果每步擴展的耗散相同時，廣度優(yōu)先搜索能找到最優(yōu)解內(nèi)存消耗是比執(zhí)行時間消耗更大的問題指數(shù)級的時間消耗(空間和時間消耗的例子參見p60圖3.11)第2章搜索技術292.2.2深度優(yōu)先搜索和深度有限搜索深度優(yōu)先搜索過程：總是擴展搜索樹的當前擴展分支(邊緣)中最深的節(jié)點搜索直接伸展到搜索樹的最深層，直到那里的節(jié)點沒有后繼節(jié)點那些沒有后繼節(jié)點的節(jié)點擴展完畢就從邊緣中去掉然后搜索算法回退下一個還有未擴展后繼節(jié)點的上層節(jié)點繼續(xù)擴展搜索算法參見深度有限搜索算法(l=∞)第2章搜索技術30深度優(yōu)先搜索的性能深度優(yōu)先搜索通過后進先出隊列LIFO(棧)調(diào)用Tree-Search實現(xiàn)/通常使用遞歸函數(shù)實現(xiàn)，依次對當前節(jié)點的子節(jié)點調(diào)用該函數(shù)性能：內(nèi)存需求少—如分支因子=b/最大深度=m的狀態(tài)空間深度優(yōu)先搜索只需要存儲bm+1個節(jié)點(比較廣度優(yōu)先O(bd+1))不是完備的/不是最優(yōu)的最壞情況下時間復雜性也很高O(bm)第2章搜索技術31深度有限搜索深度優(yōu)先搜索的無邊界問題可以通過提供一個預先設定的深度限制l來解決深度=l的節(jié)點當作無后繼節(jié)點看待雖然解決了無限路徑問題，但如果l<d則找不到解如果選擇d>l則深度優(yōu)先搜索也不是最優(yōu)的時間復雜度O(bl)空間復雜度O(bl)深度優(yōu)先搜索可看作是一種特例即l=∞第2章搜索技術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章搜索技術33搜索步數(shù)的限制上面算法中可能有兩類失敗cutoff表示到達了有限深度而無解failure表示一般的返回值無解有時深度有限搜索基于問題本身的知識，如狀態(tài)空間的直徑即問題求解的最大步數(shù)但對于大多數(shù)問題，不到問題解決時是無法知道求解步數(shù)的限制第2章搜索技術342.2.3疊代深入深度優(yōu)先搜索如果每次改變限制深度，多次調(diào)用深度有限搜索算法，就得到了疊代深入深度優(yōu)先搜索算法其深度限制依次為0/1/2…這樣，當搜索到達最淺的目標節(jié)點深度時就可以發(fā)現(xiàn)目標節(jié)點這種搜索結合了廣度優(yōu)先和深度優(yōu)先兩種算法的優(yōu)點(算法見p63)分支因子有限時是完備的/路徑耗散是節(jié)點深度的非遞增函數(shù)時是最優(yōu)的空間需求為O(bd)/時間復雜性為O(bd)第2章搜索技術35狀態(tài)的生成疊代深入搜索中因為多次重復搜索，因此部分狀態(tài)被多次生成，看起來很浪費但是因為在分支因子比較平衡的搜索樹中，多數(shù)節(jié)點都在最底層(即葉子節(jié)點)，所以上層節(jié)點的多次生成影響不是很大/與廣度優(yōu)先搜索相比，效率還是更高一般來講，當搜索空間很大而解的深度未知時，疊代深入搜索是一個首選的無信息搜索方法第2章搜索技術362.2.4無信息搜索策略比較第2章搜索技術評價標準廣度優(yōu)先代價一致深度優(yōu)先深度有限疊代深入雙向搜索是否完備時間空間是否最優(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

關于A/B/C/D的解釋：A—如果b有限則是完備的/B—單步耗散≥e則是完備的/C—如果單步耗散都是相同的則是最優(yōu)的/D—兩個方向上都使用廣度優(yōu)先搜索372.2.5圖搜索算法已經(jīng)看到搜索過程中會出現(xiàn)重復的狀態(tài)擴展，應該避免/如果算法不檢測重復狀態(tài)的話，有可能使一個本來可解的問題變?yōu)椴豢山鈾z測就是把要擴展的節(jié)點與已擴展的節(jié)點進行比較，把遇到的相同狀態(tài)去掉所以要記錄已經(jīng)擴展的節(jié)點—引入兩個表—存儲已擴展的節(jié)點closed表和未擴展的節(jié)點open表(即前述fringe)新算法稱為圖搜索算法第2章搜索技術38圖搜索算法第2章搜索技術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é)點的合并圖搜索算法與樹搜索算法比較：只是增加了對展開節(jié)點的判斷，因此由不同的待擴展節(jié)點排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先)的性能仍然同樹搜索算法對于含很多重復狀態(tài)的問題，其搜索效率比樹搜索算法有效很多討論參見p67第2章搜索技術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章搜索技術41“農(nóng)夫過河”—廣度優(yōu)先搜索第2章搜索技術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章搜索技術000010101100×001011100100110101011111closed表<0000><1010><0010><1110><0100><1101>所用規(guī)則序列3/5/2/7/4所用規(guī)則序列3/5/2/7/4/5/3只使用一個搜索分支/所擴展的第一個節(jié)點是最新節(jié)點432.3啟發(fā)式搜索策略

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

2.3.2A*搜索

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

2.3.4聯(lián)機搜索第2章搜索技術44啟發(fā)式搜索通用算法啟發(fā)式搜索也稱有信息搜索，其通用算法稱為最佳優(yōu)先搜索(Best-First-Search)最佳優(yōu)先搜索基于評價函數(shù)擴展節(jié)點—按照距離目標最短的評價值來擴展并不是真正的最佳—只是表現(xiàn)得最佳/近似最佳算法的關鍵因素是啟發(fā)函數(shù)(Heuristicfunction)，記為f(n)/f(n)=從節(jié)點n到目標節(jié)點的最低耗散路徑的耗散估計值啟發(fā)函數(shù)引導搜索兩種方式—貪婪最佳優(yōu)先搜索/A*搜索(A*算法)第2章搜索技術452.3.1貪婪最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索的評價函數(shù)f(n)=h(n)在貪婪最佳優(yōu)先搜索中總是選擇當前離目標最近(最小代價)的節(jié)點進行擴展(搜索)局部最佳未必全局最佳—不是最優(yōu)的(下例)使用貪婪最佳優(yōu)先搜索算法搜索從Arad到首都的行車最短路線Arad的下一站有3個城市S(253)/T(329)/Z(374)→擴展Sibiu有3個城市F(176)/O(380)/R(193)→擴展Fagaras直接可到目的地然而實際不是最優(yōu)的：S→F→B實際全長310/S→RV→P→B實際全長278，多了32km第2章搜索技術46問題實例—Romania公路圖第2章搜索技術47問題實例(1)第2章搜索技術尋找從Arad到首都的行車最短路線評價函數(shù)f(n)=h(n)直線距離啟發(fā)式hSLD與實際距離相關但需另外給出，見下表Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti100Eforie161RimnicuVilcea193Fagaras176Sibiu253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind37448問題實例(2)第2章搜索技術啟發(fā)函數(shù)h(n)最小化會對錯誤的起點比較敏感例子：地圖中Iasi到Fagaras的行車路線(走入死路的可能)需要仔細檢查重復狀態(tài)，否則可能永遠找不到解與深度優(yōu)先搜索類似，非最優(yōu)、非完備最壞情況下時空復雜度都是O(bm)/m為最大搜索深度492.3.2A*搜索A*搜索的評價函數(shù)為f(n)=g(h)+h(n)g(n)是從初始節(jié)點到該節(jié)點n的路徑耗散h(n)是從節(jié)點n到目標節(jié)點的最低耗散路徑的估計耗散值，稱為啟發(fā)式或啟發(fā)函數(shù)因此，f(n)=經(jīng)過節(jié)點n、具有最低耗散值的解的估計耗散找到g(n)+h(n)值最小的節(jié)點當然是合理的(參見書中p79圖4.3對于地圖的搜索)若啟發(fā)函數(shù)h(n)滿足一定條件，則A*搜索是完備的和最優(yōu)的第2章搜索技術50搜索算法的可采納性[定義]搜索算法的可采納性(可采用性)

(Hart,Nilsson,Raphel,1968)如果狀態(tài)空間中的目標狀態(tài)存在，并且從初始狀態(tài)到目標狀態(tài)有一條通路，而搜索算法一定能在有限步內(nèi)終止并找到一個最優(yōu)解(代價最低)，則這個狀態(tài)空間搜索算法稱為可采納的對于A*搜索來說，使用樹搜索算法(Tree-Search)，則它是可采納的如果對啟發(fā)函數(shù)h(n)作一定限制，則使用圖搜索算法(Graph-Search)也是可采納的第2章搜索技術51可采納的啟發(fā)函數(shù)算法的可采納性取決于啟發(fā)函數(shù)的可采納性啟發(fā)函數(shù)h(n)是可采納的—h(n)從來不會過高地估計到達目標的耗散值此即—h(n)滿足h(n)≤h*(n)，h*(n)是從當前節(jié)點n到達目標的最低耗散值此即—f(n)永遠不會高估經(jīng)過節(jié)點n的解的實際耗散—f(n)≤f*(n)，所以是最優(yōu)解如果h(n)是可采納的，那么使用Tree-Search的A*算法是可采納的(最優(yōu)的)自己嘗試證明，參考附錄證明過程第2章搜索技術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章搜索技術53A*搜索的Graph-Search算法如果A*搜索使用圖搜索算法，則A*必然返回最優(yōu)解的結論就不成立—原因是如果最優(yōu)路徑不是第一個生成的，可能因為有重復狀態(tài)而被丟棄解決方案：1)修改Graph-Search算法使得能夠進行比較，只丟棄耗散值大的路徑2)保證到達任何重復狀態(tài)的最優(yōu)路徑總是第一條被追隨的路徑—要求h(n)保持一致性(單調(diào)性)算法—請自行給出第2章搜索技術54h(n)的一致性(1)[定義]啟發(fā)函數(shù)的一致性—如果對于每個節(jié)點n和通過任意行動a生成n的每個后繼節(jié)點n’，從節(jié)點n到達目標節(jié)點的估計耗散值h(n)不大于從n到n’的單步耗散與從n’到目標節(jié)點的估計耗散值之和，則h(n)稱為一致的此即h(n)≤c(n,n’,a)+h(n’)/是三角不等式的某種形式每個一致的啟發(fā)函數(shù)都是可采納的證明要點：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é)點h(T)=h*(T)=0回退可得任意節(jié)點h(n)≤h*(n)第2章搜索技術55h(n)的一致性(2)通常我們選擇的啟發(fā)函數(shù)h(n)都滿足一致性要求(因而必定是可采納的)關于一致性的結論：如果h(n)是一致的，那么使用Graph-Search的A*算法是最優(yōu)的附錄證明似乎沒有利用此條件如果h(n)是一致的，那么沿著任何路徑的f(n)值是非遞減的(由一致性定義可得)f(n)耗散值沿著任何路徑都是非遞減的結論允許在狀態(tài)空間中畫出等值線(見下圖)第2章搜索技術56道路里程的等值線第2章搜索技術ZTLMDCGUONIVHE420A380BFPRS40057A*搜索節(jié)點的擴展A*搜索由初始節(jié)點出發(fā)開始搜索，以同心帶狀增長f(n)耗散值的方式擴展節(jié)點如果h(n)=0則為代價一致搜索(只按g(n)值排序)則同心帶為“圓型”，使用啟發(fā)函數(shù)則同心帶向目標節(jié)點方向拉伸如果C*是最優(yōu)解路徑的耗散值，則有以下結論：A*算法擴展所有f(n)≤C*的節(jié)點A*算法在到達目標節(jié)點之前可能會擴展一些正好處于“目標等值線”上的節(jié)點A*算法不擴展f(n)>C*的節(jié)點(均被剪枝)第2章搜索技術58A*算法的性質(1)A*算法是完備的—如果解存在，就一定能找到/因為找到解只要有限步A*算法是最優(yōu)的—即可采納的(一個普遍采用的證明見附錄)A*算法對于任何給定的啟發(fā)函數(shù)都是效率最優(yōu)的/沒有任何其他算法擴展的節(jié)點少于A*算法但是，A*算法對于多數(shù)問題來說，搜索空間處于目標等值線內(nèi)的節(jié)點數(shù)量是求解路徑長度的指數(shù)級第2章搜索技術59A*算法的性質(2)如果要求不以指數(shù)級增長，則啟發(fā)函數(shù)需要滿足條件對于幾乎所有的啟發(fā)函數(shù)來說，偏差至少都是與路徑耗散成正比的，而不是路徑耗散的對數(shù)/所以，在實際應用中，往往不是堅持找到最優(yōu)解，而是采用以下兩種方式：使用A*算法的變種算法快速找到非最優(yōu)解設計準確而非嚴格可采納的啟發(fā)函數(shù)第2章搜索技術60A*算法在空間方面的改進A*算法在內(nèi)存中保留所有生成的節(jié)點，消耗極大—因而對于許多大規(guī)模問題時不實用的A*算法要減少對內(nèi)存的需求—改進遞歸最佳優(yōu)先搜索RBFS—模仿標準的最佳優(yōu)先搜索的遞歸算法，只是用線性存儲空間如果h(n)是可采納的，則RBFS最優(yōu)MA*(存儲限制A*)和SMA*(簡化的MA*)—充分利用可用的內(nèi)存SMA*的思想—當內(nèi)存放滿時，就丟棄最差的一個子節(jié)點而加入新節(jié)點如果任何最優(yōu)解是可到達的，則SMA*是最優(yōu)的第2章搜索技術612.3.3啟發(fā)函數(shù)A*搜索的關鍵就是設計可采納的或者一致的(單調(diào)的)啟發(fā)函數(shù)如何評價啟發(fā)函數(shù)/如何設計啟發(fā)函數(shù)例子—八數(shù)碼問題關于八數(shù)碼問題的一些數(shù)據(jù)：隨機產(chǎn)生的八數(shù)碼游戲的平均解的步數(shù)=22分支因子約為3窮舉搜索(盲目搜索)考慮的狀態(tài)個數(shù)322≈3.1*1010實際可到達的不同狀態(tài)個數(shù)9!/2=181440第2章搜索技術62八數(shù)碼問題的啟發(fā)函數(shù)啟發(fā)函數(shù)的核心—決不高估到達目標的步數(shù)/對于八數(shù)碼問題的常用候選：h1(n)=不在位棋子數(shù)—這是一個可采納的啟發(fā)函數(shù)，因為要把“不在位”的棋子都移動到正確位置上，每個錯位的棋子至少要移動一次/所以有h1(n)≤h*(n)h2(n)=所有棋子到達其目標位置的距離和—計算水平距離(曼哈頓距離)/該函數(shù)也是可采納的，因為到達其目標位置至少要移動這些距離長度第2章搜索技術63啟發(fā)函數(shù)精確度對算法性能的影響刻畫啟發(fā)函數(shù)質量的一個度量是有效分支因子b*b*是深度為d的一致搜索樹為了能夠包括N(生成的總節(jié)點數(shù))+1個節(jié)點所必需的分支因子N+1=1+b*+(b*)2+……+(b*)d例如：52個節(jié)點在第5層找到解，則b*=1.92有效分支因子可以根據(jù)問題實例發(fā)生變化，但是在足夠難的問題中是穩(wěn)定的/因此小規(guī)模實驗中測得b*值可以為啟發(fā)函數(shù)的總體有效性提供指導第2章搜索技術64八數(shù)碼問題啟發(fā)函數(shù)的比較良好設計的啟發(fā)函數(shù)使b*值接近1，允許對大規(guī)模的問題進行求解啟發(fā)函數(shù)越接近于真實最優(yōu)解的值，則相應的搜索算法效率越高/顯然此時有—如果h1(n)≤h2(n)，則h2(n)優(yōu)于h1(n)(此時h2(n)信息量比h1(n)多)p85頁給出了八數(shù)碼問題的啟發(fā)函數(shù)h1/h2的比較數(shù)據(jù)“優(yōu)于”的含義—使用h2的算法不會比使用h1的算法擴展更多的節(jié)點第2章搜索技術65如何設計啟發(fā)函數(shù)A*搜索的關鍵如何找到是一個合適的啟發(fā)函數(shù)尋找策略：從松弛問題中獲得—松弛問題的最優(yōu)解的耗散是原問題的一個可采納的啟發(fā)函數(shù)從給定問題子問題的解耗散中獲得—建立模式數(shù)據(jù)庫，存儲每個可能子問題實例從經(jīng)驗中學習—使用歸納學習算法，使用相關狀態(tài)特征來預測第2章搜索技術66松弛問題最優(yōu)解作為啟發(fā)函數(shù)松弛問題—降低了行動限制的問題松弛問題的最優(yōu)解耗散是原問題的一個可采納的啟發(fā)函數(shù)根據(jù)定義，原始問題的最優(yōu)解也是該松弛問題的解，其耗散不低于松弛問題的最優(yōu)解松弛問題的最優(yōu)解是確切耗散，一定滿足三角不等式，因而是單調(diào)的，所以作為啟發(fā)函數(shù)一定是可采納的如果問題定義通過形式化語言描述，則自動地構造其松弛問題是可能的/例子—八數(shù)碼問題第2章搜索技術67子問題的解耗散作為啟發(fā)函數(shù)子問題的最優(yōu)解耗散是完整問題的耗散下界建立模式數(shù)據(jù)庫—存儲每個可能子問題實例的精確解耗散從目標狀態(tài)向后搜索并記錄下每個子問題模式的耗散，存儲于數(shù)據(jù)庫搜索中遇到的每個完整狀態(tài)通過在數(shù)據(jù)庫中查找出相應子問題布局而設計出一個可采納的啟發(fā)函數(shù)對于八數(shù)碼問題，這樣的啟發(fā)函數(shù)要比曼哈頓距離精確得多(具體數(shù)值見p87)第2章搜索技術68從經(jīng)驗中學習啟發(fā)函數(shù)從實例中學習—每個實例包含了解路徑上的各狀態(tài)及其到達解的耗散每個最優(yōu)解實例提供了可學習h(n)的實例收集實際解消耗的統(tǒng)計數(shù)據(jù)，以此產(chǎn)生可預測其他狀態(tài)解消耗的啟發(fā)函數(shù)h(n)使用歸納學習方法八數(shù)碼問題的討論(p87)第2章搜索技術69A*搜索的例子(1)積木塊移動游戲初始狀態(tài)：目標狀態(tài)：移動規(guī)則：

(1)積木移到空格/代價=1 (2)積木跨越1個積木移到空格/代價=1 (3)積木跨越2個積木移到空格/代價=2第2章搜索技術70A*搜索的例子(2)A*搜索：至少代價=每個W左邊B的個數(shù)(B到W右邊的必須跨越W的代價)令h(n)=至少代價，則h(n)≤h*(n)且滿足單調(diào)性

h(ni)≤h(ni+1)+g(ni+1)-g(ni)(實際是=)g(n)=到達當前狀態(tài)實際付出的代價搜索過程中括號里的數(shù)字分別為h/g值第2章搜索技術71A*搜索的例子(3)第2章搜索技術722.3.4

聯(lián)機搜索脫機搜索—不需感知，只要計算例子：簡單游戲，通過有限的規(guī)則作用即可推算出目標所在聯(lián)機搜索—必須通過行動/觀察與計算交叉進行才能決定下一步搜索兩種情況：環(huán)境未知—只有行動才能得知如何正確走向目標/環(huán)境空間過大—雖然理論上已知，但是實際不可計算(如棋類比賽)第2章搜索技術73例子：迷宮問題第2章搜索技術GS321123

如左圖所示，聯(lián)機搜索問題只能通過行動來解決，因為障礙是不能事先預知的智能體初始位置在S，其已知信息為：ACTION(s)—狀態(tài)S下的行動列表c(s,a,s’)—通過行動a從s狀態(tài)到達s’狀態(tài)

Goal-Test(s)/G目標位置智能體可使用曼哈頓距離啟發(fā)式74競爭率(1)代價—智能體實際走過的路經(jīng)總耗散理想耗散—沒有無用搜索步驟的走過路徑耗散/也就是應該走過路徑的耗散競爭率—代價÷理想耗散該值要盡可能地小第2章搜索技術75競爭率(2)影響競爭率的因素，使其無窮大行動不可逆—進入一個不可到達目標的狀態(tài)又不可回溯沒有算法能夠在所有的狀態(tài)空間中避免死路(p98圖4.19a)因此，通常需要假設狀態(tài)空間是可安全探索的—具有可逆的狀態(tài)空間/從每個可達狀態(tài)出發(fā)都有可達的目標狀態(tài)不過，在可逆狀態(tài)空間中，因為對手的存在，也會出現(xiàn)無界競爭率的情況(p98圖4.19b)第2章搜索技術76聯(lián)機搜索智能體聯(lián)機搜索智能體需要行動和感知，然后擴展當前狀態(tài)的環(huán)境地圖區(qū)別：聯(lián)機—規(guī)劃與行動交叉/脫機—只要規(guī)劃例子：A*搜索在不同子空間節(jié)點的跳躍式擴展，模擬而非實際行動/聯(lián)機算法只擴展目前實際占據(jù)的節(jié)點—采用深度優(yōu)先搜索聯(lián)機搜索必須維護一個回溯表第2章搜索技術77演講完畢，謝謝觀看！附錄資料：人工智能簡介?AboutTeachingPlan基本要求：人工智能是計算機科學中涉及研究、設計和應用智能機器的一個分支，是目前迅速發(fā)展的一門新興學科，新思想新方法層出不窮。其基本思想是利用機器來模仿和執(zhí)行人腦的功能，如判斷、推理、證明、識別、感知、理解、設計、思考、規(guī)劃、學習和問題求解等思維活動。對于培養(yǎng)學生計算機技術的應用能力，開闊思路和視野，有重要意義。

?AboutTeachingPlan因此，要求學生掌握知識表示和問題求解的幾種常用方法，尤其是不確定性推理；掌握機器學習基本概念，了解幾種機器學習方法尤其是神經(jīng)網(wǎng)絡學習方法；掌握專家系統(tǒng)的概念，了解專家系統(tǒng)設計方法，掌握一些智能控制方法，了解國內(nèi)外人工智能研究尤其是機器人的最新進展；具有一定的人工智能編程設計能力（利用Lisp或Prolog語言）。?AboutTeachingPlan課程內(nèi)容以及學時分配人工智能引論(1) 人工智能概念及與計算機的關系，研究途徑、內(nèi)容和應用領域概況介紹，其他最新材料。符號主義、連接主義、行為主義三大流派人工智能數(shù)學基礎(1)知識表示方法（2） 狀態(tài)空間法、問題歸約法，謂詞邏輯法、產(chǎn)生式表示法（動物識別系統(tǒng)）；CLIPS語言；語義網(wǎng)絡法、框架法（這是結構化表示）；劇本、過程、Petri網(wǎng)、面向對象的表示。?AboutTeachingPlan 搜索技術和策略（3-4）狀態(tài)空間法，盲目搜索和啟發(fā)式搜索，A*算法；海伯倫理論、消解原理和策略；與\或形推理和搜索策略；其他求解技術。 不確定推理技術（3-4）主觀Bayes理論；可信度方法和證據(jù)理論；系統(tǒng)組織技術；非單調(diào)推理；Rete快速算法；模糊推理技術；基于語義網(wǎng)絡和框架不確定推理； 專家系統(tǒng)（2）專家系統(tǒng)概念、結構和知識獲?。缓诎迥Ｐ?、知識組織、管理及系統(tǒng)建造和開發(fā)工具；專家系統(tǒng)舉例及編程。

人工智能程序設計（1）人工智能語言基本機制：LISP和PROLOG。?AboutTeachingPlan 模式識別導論（3）模式識別專題：概率模式識別。模式識別專題：結構模式識別 機器學習（1）：機械,解釋經(jīng)驗,事例,歸納,概念,類比學習等；統(tǒng)計,結構,模糊模式識別。 專題講座（3次） 1)神經(jīng)網(wǎng)絡基本理論和應用 (史奎凡課程：安排于人工智能理論與應用課程內(nèi))； 2)智能體（Agent）； 3)自然語言處理； 4)智能控制和機器人科學 智能控制的結構理論和研究領域，智能控制系統(tǒng)及應用示例；機器人規(guī)劃、機器視覺和自然語言理解等。?AboutTeachingPlan 實踐：1) 搜索技術和策略2) 不確定推理技術3) 專家系統(tǒng)：動物識別系統(tǒng)4) 模式識別技術5) 調(diào)研： 搜索技術和策略、不確定推理技術、統(tǒng)計模式識別、機器學習等四個領域進展報告。?ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（ArtificialIntelligence,AI）是當前科學技發(fā)展的一門前沿學科，同時也是一門新思想，新觀念，新理論，新技術不斷出現(xiàn)的新興學科以及正在發(fā)展的學科。它是在計算機科學，控制論，信息論，神經(jīng)心理學，哲學，語言學等多種學科研究的基礎發(fā)展起來的，因此又可把它看作是一門綜合性的邊緣學科。它的出現(xiàn)及所取得的成就引起了人們的高度重視,并取得了很高的評價。有的人把它與空間技術，原子能技術一起并譽為20世紀的三大科學技術成就。?Intelligence智能是知識與智力的總合。 知識——智能行為的基礎； 智力——獲取知識并運用知識求解問題的能力。智能具有以下特征：(1)具有感知能力——指人們通過視覺、聽覺、觸覺、味覺、嗅覺等感覺器官感知外部世界的能力；(2)具有記憶與思維的能力——這是人腦最重要的功能，亦是人之所以有智能的根本原因；(3)具有學習能力及自適應能力；(4)具有行為能力。ArtificialIntelligence人工智能——計算機科學的一個分支，是智能計算機系統(tǒng)，即人類智慧在機器上的模擬，或者說是人們使機器具有類似于人的智慧（對語言能理解、能學習、能推理）。?2.BriefHistoryofAI (1) 孕育（1956年前）古希臘的Aristotle（亞里士多德）（前384-322），給出了形式邏輯的基本規(guī)律。英國的哲學家、自然科學家Bacon（培根）（1561-1626），系統(tǒng)地給出了歸納法?！爸R就是力量”德國數(shù)學家、哲學家Leibnitz（布萊尼茨）（1646-1716）。提出了關于數(shù)理邏輯的思想，把形式邏輯符號化，從而能對人的思維進行運算和推理。做出了能做四則運算的手搖計算機英國數(shù)學家、邏輯學家Boole（布爾）（1815-1864）實現(xiàn)了布萊尼茨的思維符號化和數(shù)學化的思想，提出了一種嶄新的代數(shù)系統(tǒng)——布爾代數(shù)。?美籍奧地利數(shù)理邏輯學家Godel（哥德爾）（1906-1978），證明了一階謂詞的完備性定；任何包含初等數(shù)論的形式系統(tǒng)，如果它是無矛盾的，那么一定是不完備的。意義在于，人的思維形式化和機械化的某種極限，在理論上證明了有些事是做不到的。英國數(shù)學家Turing(圖靈)（1912-1954）,1936年提出了一種理想計算機的數(shù)學模型（圖靈機），1950年提出了圖靈試驗，發(fā)表了“計算機與智能”的論文。圖靈獎。美國數(shù)學家Mauchly，1946發(fā)明了電子數(shù)字計算機ENIAC美國神經(jīng)生理學家McCulloch，建立了第一個神經(jīng)網(wǎng)絡數(shù)學模型。美國數(shù)學家Shannon（香農(nóng)）,1948年發(fā)表了《通訊的數(shù)學理論》，代表了“信息論”的誕生。? (2) 形成（1956-1969）1956年提出了“ArtificialIntelligence（人工智能）”1956年夏由麻省理工學院的J.McCarthy、M.L.Minsky,IBM公司信息研究中心的N.Rochester,貝爾實驗室的C.E.Shannon共同發(fā)起，邀請了Moore,Samuel,Selfridge,Solomonff,Simon,Newell等人，10位數(shù)學家、信息學家、心理學家、神經(jīng)生理學家、計算機科學家，在Dartmouth大學召開了一次關于機器智能的研討會，會上McCarthy提議正式采用了ArtificialIntelligence（人工智能）這一術語。這次會議，標志著人工智能作為一門新興學科正式誕生了。 McCarthy（麥卡錫）——人工智能之父。這次會議之后的10年間，人工智能的研究取得了許多引人矚目的成就.機器學習方面：塞繆爾于1956年研制出了跳棋程序，該程序能從棋譜中學習，也能從下棋實踐中提高棋藝；?在定理證明方面：王浩于1958年在IBM機上證明了《數(shù)學原理》中有關命題演算的全部定理（220條），還證明了謂詞演算中150條定理85%；1965年，魯賓遜（Robinson）提出了消解原理；在模式識別方面：1959年塞爾夫里奇推出了一個模式識別程序；1965年羅伯特（Robert）編制出可辨別積木構造的程序；在問題求解方面：1960年紐厄爾等人通過心理學試驗總結出了人們求解問題的思維規(guī)律，編制了通用問題求解程序GPS,可以用來求解11種不同類型的問題；在專家系統(tǒng)方面：斯坦福大學的費根鮑姆（E.A.Feigenbaum）自1965年開始進行專家系統(tǒng)DENDRAL（化學分析專家系統(tǒng)），1968年完成并投入使用；在人工智能語言方面：1960年McCarthy等人建立了人工智能程序設計語言Lisp，該語言至今仍是建造智能系統(tǒng)的重要工具；1969年成立了國際人工智能聯(lián)合會議（InternationalJointConferencesOnArtificialIntelligence）? (3) 發(fā)展（1970年以后）70年代，開始從理論走向實踐，解決一些實際問題。同時很快就發(fā)現(xiàn)問題：歸結法費時、下棋贏不了全國冠軍、機器翻譯一團糟。以Feigenbaum為首的一批年輕科學家改變了戰(zhàn)略思想，1977年提出知識工程的概念，以知識為基礎的專家咨詢系統(tǒng)開始廣泛的應用。著名專家系統(tǒng)的有：DENDRAL化學分析專家系統(tǒng)（斯坦福大學1968）MACSYMA符號數(shù)學專家系統(tǒng)（麻省理工1971）MYCIN診斷和治療細菌感染性血液病的專家咨詢系統(tǒng)（斯坦福大學1973）CASNET(CausalASsciationalNetwork)診斷和治療青光眼的專家咨詢系統(tǒng)（拉特格爾斯（Rutgers）大學70年代中）CADUCEUS(原名INTERNIST)醫(yī)療咨詢系統(tǒng)（匹茲堡大學）；HEARSAYI和II語音理解系統(tǒng)（卡內(nèi)基-梅隆大學）PROSPECTOR地質勘探專家系統(tǒng)（斯坦福大學1976）XCON計算機配置專家系統(tǒng)（卡內(nèi)基-梅隆大學1978）??80年代，人工智能發(fā)展達到階段性的頂峰。?87,89年世界大會有６－７千人參加。硬件公司有上千個。并進行Lisp硬件、Lisp機的研究。?在專家系統(tǒng)及其工具越來越商品化的過程中,國際軟件市場上形成了一門旨在生產(chǎn)和加工知識的新產(chǎn)業(yè)——知識產(chǎn)業(yè)。應該說，知識工程和專家系統(tǒng)是近十余年來人工智能研究中最有成就的分支之一。?同年代，1986年Rumlhart領導的并行分布處理研究小組提出了神經(jīng)元網(wǎng)絡的反向傳播學習算法，解決了神經(jīng)網(wǎng)絡的根本問題之一。從此，神經(jīng)網(wǎng)絡的研究進入新的高潮。?90年代，計算機發(fā)展趨勢為小型化、并行化、網(wǎng)絡化、智能化。?人工智能技術逐漸與數(shù)據(jù)庫、多媒體等主流技術相結合，并融合在主流技術之中，旨在使計算機更聰明、更有效、與人更接近。?日本政府于1992年結束了為期十年的稱為“知識信息處理體統(tǒng)”的第五代計算機系統(tǒng)研究開發(fā)計劃。并開始了為期十年的實況計算（RealWordComputing）計劃。?3.ResearchObjectsandMainContents

(1)人工智能的研究目標

人工智能的長期研究目標：構造智能計算機。

人工智能的近期研究目標：使現(xiàn)有的電子計算機更聰明，更有用，使它不僅能做一般的數(shù)值計算及非數(shù)值信息的數(shù)據(jù)處理，而且能運用知識處理問題，能模擬人類的部分智能行為。?(2)人工智能研究的基本內(nèi)容

1.機器感知以機器視覺與機器聽覺為主。機器感知是機器獲取外部信息的基本途徑，是使機器具有智能不可或缺的組成部分，對此人工智能中已形成兩個專門的研究領域——

模式識別和自然語言理解。2.機器思維指通過感知的外部信息及機器內(nèi)部的各種工作信息進行有目的的處理。主要開展以下幾方面的研究：(1)知識表示(2)知識的組織，累計，管理技術(3)知識的推理(4)各種啟發(fā)式搜索及控制策略(5)神經(jīng)網(wǎng)絡，人腦的結構及其工作原理?3.機器學習

使計算能自動獲取知識，能直接向書本學習，能通過與人談話學習，能通過對環(huán)境的觀察學習，并能在實踐中自我完善。4.機器行為機器行為主要指計算機的表達能力，即“說”、“寫”、“畫”等，對智能機器人，還應該有人的四肢功能，即能走路，能取物，能操作等。5.智能系統(tǒng)及智能計算機的構造技術?4.ResearchObjectsandMainContents人工智能面世以來，其研究途徑存在兩種不同的觀點：以符號處理為核心的方法——主張通過運用計算機科學的方法進行研究，實現(xiàn)人工智能在計算機的模擬。以網(wǎng)絡連接為主的連接機制方法——主張用生物學的方法進行研究，搞清楚人類智能的本質。(1)以符號處理為核心的方法該方法起源于紐厄爾等人的通用問題求解系統(tǒng)（GPS），用于模擬人類求解問題的心理過程，逐漸形成為物理符號系統(tǒng)，這種方法認為： 人類研究的目標是實現(xiàn)機器智能，而計算機自身具有符號處理能力，這種能力本身就蘊含著演繹推理的內(nèi)涵，因而可通過運行相