人工智能原理之搜索技術(shù)

人工智能原理

第2章搜索技術(shù)

（上）

1

本章內(nèi)容

2.1搜索與問題求解

2.2無信息搜索策略

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

2.4局部搜索算法

2.5約束滿足問題

2.6博弈搜索

參考書目

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

2.1.1問題與問題的解

2.1.2問題實(shí)例

2.1.3搜索策略第2章搜索技術(shù)3搜索與問題求解問題求解過程是搜索答案(目標(biāo))的過程/所以問題求解技術(shù)也叫搜索技術(shù)—通過對狀態(tài)空間的搜索而求解問題的技術(shù)問題求解智能體是一種基于目標(biāo)的智能體在尋找到達(dá)目標(biāo)的過程中，當(dāng)智能體面對多個(gè)未知的選項(xiàng)時(shí)，首先檢驗(yàn)各個(gè)不同的導(dǎo)致已知評價(jià)的狀態(tài)的可能行動(dòng)序列，然后選擇最佳序列—這個(gè)過程就是搜索第2章搜索技術(shù)42.1.1問題與問題的解問題可以形式化地定義為4個(gè)組成部分智能體的初始狀態(tài)(即搜索的開始)后繼函數(shù)—智能體采取的可能行動(dòng)的描述，通常為<行動(dòng)，后繼狀態(tài)>/初始狀態(tài)和后繼函數(shù)隱含地定義了問題的狀態(tài)空間/狀態(tài)空間中的一條路徑是通過行動(dòng)序列連接起來的一個(gè)狀態(tài)序列目標(biāo)測試—檢查給定的狀態(tài)是不是目標(biāo)路徑耗散函數(shù)—每條路徑都有一個(gè)數(shù)值化的耗散值，反映了性能度量/求解問題的代價(jià)第2章搜索技術(shù)5問題的解問題的解就是初始狀態(tài)到目標(biāo)狀態(tài)的路徑解的優(yōu)劣由路徑耗散函數(shù)量度(代價(jià))最優(yōu)解就是路徑耗散函數(shù)值最小的路徑上述解題過程把解決一個(gè)問題的過程描述出來，稱之為解題知識的過程性表示過程性知識與陳述性知識相對搜索過程解題的特點(diǎn)—沒有直接的方法(公式)可以求解，而是一步一步的探索第2章搜索技術(shù)6狀態(tài)空間數(shù)據(jù)基：代表了所要解決的問題，有初始狀態(tài)，可能有目標(biāo)狀態(tài)也可能沒有狀態(tài)空間：在解題過程中的每一時(shí)刻，數(shù)據(jù)基都處于一定的狀態(tài)，數(shù)據(jù)基所有可能狀態(tài)的集合稱為狀態(tài)空間有向圖：若把每個(gè)狀態(tài)看成一個(gè)節(jié)點(diǎn)，則整個(gè)狀態(tài)空間是一個(gè)有向圖/該圖不一定全連通，即從某些狀態(tài)不一定能到達(dá)另外一些狀態(tài)第2章搜索技術(shù)7問題的可解性可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將狀態(tài)改變/如果從代表初始狀態(tài)的節(jié)點(diǎn)出發(fā)，有一條路徑通向目標(biāo)狀態(tài)，則稱此目標(biāo)狀態(tài)所代表的問題在當(dāng)前初始狀態(tài)下是可解的搜索空間：在解題過程中達(dá)到過的所有狀態(tài)的集合，稱為搜索空間不同于狀態(tài)空間，搜索空間只是其中一部分狀態(tài)空間和搜索空間都屬于過程性知識表示第2章搜索技術(shù)82.1.2問題實(shí)例玩具問題八數(shù)碼游戲(九宮圖)河內(nèi)塔八皇后問題真空吸塵器世界現(xiàn)實(shí)問題旅行商問題超大規(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ì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ù)碼問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應(yīng)的位置，各位置上的初始數(shù)字后繼函數(shù)移動(dòng)規(guī)則—按照某條規(guī)則移動(dòng)數(shù)字，將得到的新向量目標(biāo)測試新向量是否是目標(biāo)狀態(tài)(也是向量形式)路徑耗散函數(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è)狀態(tài)為(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)塔的狀態(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個(gè)狀態(tài)，2階河內(nèi)塔有9個(gè)狀態(tài)，n階河內(nèi)塔有3n個(gè)狀態(tài)，給出1/2/3階河內(nèi)塔的狀態(tài)圖第2章搜索技術(shù)14河內(nèi)塔問題圖解第2章搜索技術(shù)15河內(nèi)塔問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應(yīng)所有n個(gè)盤子，位置上數(shù)字代表3個(gè)柱子之一后繼函數(shù)移動(dòng)規(guī)則—依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài)目標(biāo)測試新向量是否是目標(biāo)狀態(tài)(也是向量形式)路徑耗散函數(shù)每移動(dòng)一個(gè)盤子的代價(jià)為1第2章搜索技術(shù)16河內(nèi)塔問題求解求最短路徑問題：狀態(tài)圖中從三角形1個(gè)頂點(diǎn)走到另一個(gè)頂點(diǎn)結(jié)論：(1)如果初始狀態(tài)或目標(biāo)狀態(tài)在三角形頂點(diǎn)上，則最短路徑唯一；(2)對于任意2個(gè)狀態(tài)，最短求解路徑至多為2條。(中國某大學(xué)研究生證明)求解過程—對狀態(tài)空間的搜索—以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求解過程—樹搜索求解問題的過程使用搜索樹形式每個(gè)狀態(tài)對應(yīng)搜索樹中一個(gè)節(jié)點(diǎn)根節(jié)點(diǎn)對應(yīng)于初始狀態(tài)每次從搜索樹的上層節(jié)點(diǎn)出發(fā)，根據(jù)約束條件進(jìn)入下一個(gè)可能的狀態(tài)，即展開新的一層樹節(jié)點(diǎn)—節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)展開的順序即代表了不同的搜索策略當(dāng)展開的節(jié)點(diǎn)為目標(biāo)狀態(tài)時(shí)，就找到了問題的一個(gè)解第2章搜索技術(shù)192.1.3搜索策略研究搜索過程考慮的若干問題 (1)有限搜索還是無限搜索 (2)已知目標(biāo)還是未知目標(biāo) (3)目標(biāo)或目標(biāo)+路徑 (4)有約束還是無約束 (5)數(shù)據(jù)驅(qū)動(dòng)(向前搜索)還是目標(biāo)驅(qū)動(dòng) (6)單向搜索還是雙向搜索第2章搜索技術(shù)20搜索的分類搜索過程的分類：狀態(tài)空間搜索(圖搜索方式)，問題空間搜索(層次方法)，博弈空間搜索無信息搜索與啟發(fā)式搜索啟發(fā)式：利用中間信息改進(jì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ù)雜性的量度—由狀態(tài)空間圖的大小來衡量/相關(guān)度量如下：分支因子b (每次展開的平均節(jié)點(diǎn)個(gè)數(shù))目標(biāo)節(jié)點(diǎn)的深度d路徑的最大長度m 搜索深度限制l搜索耗散第2章搜索技術(shù)232.2無信息搜索策略

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

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

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

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

2.2.5圖搜索算法第2章搜索技術(shù)24盲目搜索策略無信息搜索也稱盲目搜索：沒有任何附加信息，只有生成后繼和區(qū)分目標(biāo)與非目標(biāo)狀態(tài)有5種盲目搜索策略廣度優(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)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章搜索技術(shù)28廣度優(yōu)先搜索的性能在上述算法中，廣度優(yōu)先搜索以Tree-Search(problem,FIFO-Queue)調(diào)用樹搜索算法從4種度量來評價(jià)廣度優(yōu)先搜索：完備性—總能找到一個(gè)解如果每步擴(kuò)展的耗散相同時(shí)，廣度優(yōu)先搜索能找到最優(yōu)解內(nèi)存消耗是比執(zhí)行時(shí)間消耗更大的問題指數(shù)級的時(shí)間消耗(空間和時(shí)間消耗的例子參見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ìn)先出隊(duì)列LIFO(棧)調(diào)用Tree-Search實(shí)現(xiàn)/通常使用遞歸函數(shù)實(shí)現(xiàn)，依次對當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)調(diào)用該函數(shù)性能：內(nèi)存需求少—如分支因子=b/最大深度=m的狀態(tài)空間深度優(yōu)先搜索只需要存儲bm+1個(gè)節(jié)點(diǎn)(比較廣度優(yōu)先O(bd+1))不是完備的/不是最優(yōu)的最壞情況下時(shí)間復(fù)雜性也很高O(bm)第2章搜索技術(shù)31深度有限搜索深度優(yōu)先搜索的無邊界問題可以通過提供一個(gè)預(yù)先設(shè)定的深度限制l來解決深度=l的節(jié)點(diǎn)當(dāng)作無后繼節(jié)點(diǎn)看待雖然解決了無限路徑問題，但如果l<d則找不到解如果選擇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í)深度有限搜索基于問題本身的知識，如狀態(tài)空間的直徑即問題求解的最大步數(shù)但對于大多數(shù)問題，不到問題解決時(shí)是無法知道求解步數(shù)的限制第2章搜索技術(shù)342.2.3疊代深入深度優(yōu)先搜索如果每次改變限制深度，多次調(diào)用深度有限搜索算法，就得到了疊代深入深度優(yōu)先搜索算法其深度限制依次為0/1/2…這樣，當(dāng)搜索到達(dá)最淺的目標(biāo)節(jié)點(diǎn)深度時(shí)就可以發(fā)現(xiàn)目標(biāo)節(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狀態(tài)的生成疊代深入搜索中因?yàn)槎啻沃貜?fù)搜索，因此部分狀態(tài)被多次生成，看起來很浪費(fèi)但是因?yàn)樵诜种б蜃颖容^平衡的搜索樹中，多數(shù)節(jié)點(diǎn)都在最底層(即葉子節(jié)點(diǎn))，所以上層節(jié)點(diǎn)的多次生成影響不是很大/與廣度優(yōu)先搜索相比，效率還是更高一般來講，當(dāng)搜索空間很大而解的深度未知時(shí)，疊代深入搜索是一個(gè)首選的無信息搜索方法第2章搜索技術(shù)362.2.4無信息搜索策略比較第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—如果b有限則是完備的/B—單步耗散≥e則是完備的/C—如果單步耗散都是相同的則是最優(yōu)的/D—兩個(gè)方向上都使用廣度優(yōu)先搜索372.2.5圖搜索算法已經(jīng)看到搜索過程中會出現(xiàn)重復(fù)的狀態(tài)擴(kuò)展，應(yīng)該避免/如果算法不檢測重復(fù)狀態(tài)的話，有可能使一個(gè)本來可解的問題變?yōu)椴豢山鈾z測就是把要擴(kuò)展的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)進(jìn)行比較，把遇到的相同狀態(tài)去掉所以要記錄已經(jīng)擴(kuò)展的節(jié)點(diǎn)—引入兩個(gè)表—存儲已擴(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)排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先)的性能仍然同樹搜索算法對于含很多重復(fù)狀態(tài)的問題，其搜索效率比樹搜索算法有效很多討論參見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只使用一個(gè)搜索分支/所擴(kuò)展的第一個(gè)節(jié)點(diǎn)是最新節(jié)點(diǎn)432.3啟發(fā)式搜索策略

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)—按照距離目標(biāo)最短的評價(jià)值來擴(kuò)展并不是真正的最佳—只是表現(xiàn)得最佳/近似最佳算法的關(guān)鍵因素是啟發(fā)函數(shù)(Heuristicfunction)，記為f(n)/f(n)=從節(jié)點(diǎn)n到目標(biāo)節(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)前離目標(biāo)最近(最小代價(jià))的節(jié)點(diǎn)進(jìn)行擴(kuò)展(搜索)局部最佳未必全局最佳—不是最優(yōu)的(下例)使用貪婪最佳優(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)最小化會對錯(cuò)誤的起點(diǎn)比較敏感例子：地圖中Iasi到Fagaras的行車路線(走入死路的可能)需要仔細(xì)檢查重復(fù)狀態(tài)，否則可能永遠(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到目標(biāo)節(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對于地圖的搜索)若啟發(fā)函數(shù)h(n)滿足一定條件，則A*搜索是完備的和最優(yōu)的第2章搜索技術(shù)50搜索算法的可采納性[定義]搜索算法的可采納性(可采用性)

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

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

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

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

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

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

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

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

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

人工智能的長期研究目標(biāo)：構(gòu)造智能計(jì)算機(jī)。

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

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

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

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