人工智能復習大綱

-.z.8．何為狀態(tài)圖和與或圖？圖搜索與問題求解有什么關系？狀態(tài)圖是描述尋找目標或路徑問題的有向圖，即描述一個實體基于事件反響的動態(tài)行為，顯示了該實體如何根據(jù)當前所處的狀態(tài)對不同的時間做出反響的。與或圖是一種系統(tǒng)地將問題分解為互相獨立的小問題，然后分而解決的方法。與或圖中有兩種代表性的節(jié)點："與節(jié)點〞和"或節(jié)點〞，"與節(jié)點〞指所有的后續(xù)節(jié)點都有解時它才有解；"或節(jié)點〞指各個后續(xù)節(jié)點均完全獨立，只要其中有一個有解它就有解。關系：問題求解就是在一個圖中尋找一個從初始節(jié)點到目標節(jié)點的路徑問題，圖搜索模擬的實際是人腦分析問題，解決問題的過程，它基于領域知識的問題求解過程。11.什么是與或樹？什么是可解節(jié)點？什么是解樹？答：一棵樹中的弧線表示所連樹枝為"與〞關系,不帶弧線的樹枝為或關系。這棵樹中既有與關系又有或關系，因此被稱為與或樹。滿足以下條件的節(jié)點為可解節(jié)點。①終止節(jié)點是可解節(jié)點；②一個與節(jié)點可解，當且僅當其子節(jié)點全都可解；③一個或節(jié)點可解，只要其子節(jié)點至少有一個可解。解樹實際上是由可解節(jié)點形成的一棵子樹,這棵子樹的根為初始節(jié)點，葉為終止節(jié)點，且這棵子樹一定是與樹14.請闡述狀態(tài)空間的一般搜索過程。OPEN表與CLOSED表的作用是什么？答：先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進展擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。假設出現(xiàn)，則搜索成功，找到了問題的解；假設沒出現(xiàn)，則再按照*種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。所謂對一個節(jié)點進展"擴展〞是指對該節(jié)點用*個可用操作進展作用，生成該節(jié)點的一組子節(jié)點。OPEN表用于存放剛生成的節(jié)點，對于不同的搜索策略，節(jié)點在OPEN表中的排序是不同的。CLOSED表用于存放將要擴展或者已擴展的節(jié)點。15.廣度優(yōu)先搜索與深度優(yōu)先搜索各有什么特點？答：廣度優(yōu)先搜索就是始終先在同一級節(jié)點中考察,只有當同一級節(jié)點考察完之后,才考察下一級節(jié)點?；蛘哒f,是以初始節(jié)點為根節(jié)點，向下逐級擴展搜索樹。所以,廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴展一個子節(jié)點,不斷地向縱深前進,直到不能再前進〔到達葉子節(jié)點或受到深度限制〕時，才從當前節(jié)點返回到上一級節(jié)點，沿另一方向又繼續(xù)前進。這種方法的搜索樹是從樹根開場一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝(即深度無限)，則不可能找到目標節(jié)點。所以，深度優(yōu)先搜索策略是不完備的。另外，應用此策略得到的解不一定是最正確解(最短路徑)。廣度優(yōu)先搜索與深度優(yōu)先搜索都屬于盲目搜索。3.8判斷以下公式是否為可合一，假設可合一，則求出其最一般合一。(1)P(a,b),P(*,y)(2)P(f(*),b),P(y,z)(3)P(f(*),y),P(y,f(b))(4)P(f(y),y,*),P(*,f(a),f(b))(5)P(*,y),P(y,*)解：(1)可合一，其最一般和一為：σ={a/*,b/y}。(2)可合一，其最一般和一為：σ={y/f(*),b/z}。(3)可合一，其最一般和一為：σ={f(b)/y,b/*}。(4)不可合一。(5)可合一，其最一般和一為：σ={y/*}。：緒論人工智能的主要學派：符號主義學派〔Sysmbolicism〕，又稱為邏輯主義學派，心理學派，計算機學派。符號主義認為知識是智能的根底，人工智能的核心問題是知識的表示與知識推理。〔功能模擬〕聯(lián)結主義學派〔Connectionism〕：又稱為仿生學派，生理學派。用人工神經(jīng)網(wǎng)絡模仿人類智能?！矘嬙炷M〕行為主義學派〔Actionism〕：又稱為進化主義學派，控制論學派。認為智能取決于感知，表現(xiàn)為行動?！残袨槟M〕人工智能的研究和應用領域〔10個〕定理證明專家系統(tǒng)機器學習自然語言理解智能檢索機器學習自動程序設計組合調度問題模式識別機器視覺：知識表示法一階謂詞邏輯表示法2.1.1：一階謂詞邏輯命題：它的取值為真或假謂詞謂詞公式謂詞公式的解釋：對于每一個解釋，謂詞公式都可以求出一個真值謂詞公式的永真性，可滿足性，不可滿足性永真性：如果謂詞公式P對個體域D上的任何一個解釋都取得真值T，則稱P在D上是永真的。可滿足性：對于謂詞公式P，如果至少存在一個解釋使得公式P在此解釋下的真值為T。不可滿足性：如果謂詞公式P對于個體域D的任何一個解釋都取得真值為F。謂詞公式的等價性。設P與Q是兩個謂詞公式，D是它們共同的個體域，假設對D上的任何一個解釋，P與Q都有一樣的真值，則稱公式P和Q在D上是等價的。如果D是任意的個體域，則稱P和Q是等價的。記為P<=>Q公式：2.1.2：一階謂詞表示方法一階謂詞表示方法例題：一階謂詞表示方法的優(yōu)點。自然性，準確性，嚴密性，容易實現(xiàn)。一階謂詞表示方法的缺點不能表示不確定性的知識，組合爆炸，效率低。產(chǎn)生式表示方法2.2.2：產(chǎn)生式系統(tǒng)的分類可交換的產(chǎn)生式系統(tǒng)可分解的產(chǎn)生式系統(tǒng)可恢復的產(chǎn)生式系統(tǒng)產(chǎn)生式表示法的特點：搜索方法3.1問題求解過程的形式表示狀態(tài)空間表示法與/或圖表示法3.2狀態(tài)空間的搜索方法盲目搜索算法無代價的寬度優(yōu)先搜索：在搜索樹的生成過程中，只有對搜索樹中同一層的所有節(jié)點都考察完之后，才對下一層的節(jié)點進展考察。無代價的深度優(yōu)先搜索：在搜索樹的生成過程中，對open表中同一層的節(jié)點只選擇表中一個節(jié)點進展考察和擴展，只有當這個節(jié)點是不可擴展的，才選擇同層的兄弟節(jié)點進展考察和擴展。寬度優(yōu)先和深度優(yōu)先的區(qū)別寬度優(yōu)先搜索生成的子節(jié)點放入open表的表尾，深度優(yōu)先搜索生成的子節(jié)點放入open表的表首。如果問題有解，則寬度優(yōu)先搜索總能找到最優(yōu)解。寬度優(yōu)先搜索時完備的，深度優(yōu)先搜索是非完備的。如果搜索最大深度設置合理，則深度優(yōu)先搜索能找到一條解路徑，但不一定是最優(yōu)解。深度優(yōu)先搜索的時空開銷小于寬度優(yōu)先。例子：提示：無代價深度優(yōu)先搜索的open表是將新擴展生成的子節(jié)點按節(jié)點序號從小到大排序后放入open表首有代價深度優(yōu)先搜索的open表是將新擴展的子節(jié)點按照價值從小到大放入open表首有代價寬度優(yōu)先搜索的open表中所有節(jié)點按代價從小到大排序啟發(fā)式搜索算法例子：3.3與或圖的搜索方法：啟發(fā)式搜索算法的解樹的代價例子：：邏輯推理4.1推理的根本概念推理的控制策略推理方向正向推理：從用戶提供的初始事實出發(fā)，在知識庫KD中找到當前可用的知識，構成可用知識集KS，然后按照*種沖突消解策略從KS中選中一條知識進展推理，并將推出的新事實參加到數(shù)據(jù)庫DB中作為下一次推理的事實，在此之后再在知識庫中選取可用知識進展推理，如此反復進展這一過程，知道求的要求的解或知識庫中再無可用的知識為止。逆向推理：首先選擇一個假設目標，然后尋找支持該假設的依據(jù)，假設所需的證據(jù)都能找到，則說明假設是成立的，假設無論如何都找不到，則說明不成立，此時需要選定新的假設?；旌贤评頉_突消解策略目前已有多種消解策略，其根本思想都是對知識進展排序按針對性排序按匹配度排序根據(jù)領域問題的特點排序4.1.3模式匹配及其變量代換4.2歸結演繹推理4.2.1謂詞公式化為子句集的方法4.2.2歸結原理4.2.3歸結反演4.3基于歸結反演的問題求解4.4歸結反演的改進策略刪除策略限制策略：專家系統(tǒng)1.專家系統(tǒng)的概念：專家系統(tǒng)是一種模擬人類專家解決領域問題的計算機軟件系統(tǒng)。2.專家系統(tǒng)的構造與開發(fā)方法知識庫：以*種存儲構造存儲領域專家的知識全局數(shù)據(jù)庫：〔黑板〕用于存儲求解問題的初始數(shù)據(jù)和推理過程中得到的中間數(shù)據(jù)，以及最終的推理結論。推理機：根據(jù)全局數(shù)據(jù)庫的當前內容，從知識庫中選擇匹配成功的可用規(guī)則，并通過執(zhí)行可用的規(guī)則修改數(shù)據(jù)庫中說的內容，直至推理出來問題的結論。解釋器：用于向用戶解釋專家系統(tǒng)的行為。用戶接口：系統(tǒng)與用戶進展對話的界面。知識獲?。喊阎R轉換為知識內部表示模式存儲到知識庫。：模糊推理模糊集合的定義與運算〔大題〕模糊知識表示與模糊匹配〔概念〕模糊知識表示模糊命題：含有模糊概念，模糊數(shù)據(jù)，