人工智能課程回顧

第一章緒論AI的概念A(yù)I的歷史AI的應(yīng)用AI探討領(lǐng)域AI探討方法其次章產(chǎn)生式系統(tǒng)產(chǎn)生系統(tǒng)基本結(jié)構(gòu)綜合數(shù)據(jù)庫、產(chǎn)生式規(guī)則、限制系統(tǒng)產(chǎn)生系統(tǒng)基本過程匹配、選擇、執(zhí)行其次章產(chǎn)生式系統(tǒng)問題的表示綜合數(shù)據(jù)庫和規(guī)則集的描述狀態(tài)空間法(S,O,G)、問題歸約法(S0,O,P)限制策略不行撤回方式摸索方式回溯方式圖搜尋方式第三章產(chǎn)生式系統(tǒng)的搜尋策略“狀態(tài)空間”的圖描述圖的節(jié)點表示問題的狀態(tài)圖的弧表示求解問題的步驟（應(yīng)用的規(guī)則）初始狀態(tài)對應(yīng)問題的已知信息，是圖的根節(jié)點限制策略回溯策略圖搜尋策略盲目的圖搜尋過程啟發(fā)式圖搜尋過程第三章產(chǎn)生式系統(tǒng)的搜尋策略盲目的圖搜尋過程寬度優(yōu)先搜尋深度優(yōu)先搜尋啟發(fā)式圖搜尋過程啟發(fā)式圖搜尋算法A最佳圖搜尋算法A*第三章產(chǎn)生式系統(tǒng)的搜尋策略啟發(fā)式圖搜尋算法A對結(jié)點n定義評價函數(shù)f(n)=g(n)+h(n)g0，f=h爬山法h0，f=g分支限界法f=g=d，寬度優(yōu)先搜尋分支限界法中只考慮f值最小的一條局部路徑，動態(tài)規(guī)劃法第三章產(chǎn)生式系統(tǒng)的搜尋策略最佳圖搜尋算法A*評價函數(shù)f(n)=g(n)+h(n)滿足條件h(n)h*(n)的啟發(fā)式圖搜尋算法AA*算法的改進針對節(jié)點重復(fù)擴展問題，改進方法：定義單調(diào)的啟發(fā)函數(shù)h待擴展節(jié)點的選擇：已擴展節(jié)點的最大f值記為fm，擴展f值小于fm的節(jié)點，且選擇滿足條件的節(jié)點中g(shù)值最小者進行擴展。第四章與或圖搜尋“問題歸約”對應(yīng)的與或圖原始問題描述對應(yīng)根節(jié)點本原問題對應(yīng)葉節(jié)點圖中的弧是1-連接符或k-連接符與或圖搜尋找尋解圖AO*算法第四章與或圖搜尋博弈樹搜尋二人完備博弈目的是給出最好走步博弈樹的極大微小搜尋法-搜尋過程極大值層的下界值記為，微小值層的上界值記為-剪枝在一個分支上進行-剪枝的規(guī)則描述如下：1．剪枝：若任一微小值層節(jié)點的值小于或等于它任一先輩極大值層節(jié)點的值，即（先輩層）≥（后繼層），則可以終止該微小值層中這個MIN節(jié)點以下的搜尋，并設(shè)置這個MIN節(jié)點的最終的倒推值為。(微小值層節(jié)點的剪枝)2．剪枝：若任一極大值層節(jié)點的值大于或等于它任一先輩微小值層節(jié)點的值，即（后繼層）≥（先輩層），則可以終止該極大值層中這個MAX節(jié)點以下的搜尋過程，并設(shè)置這個MAX節(jié)點的最終倒推值為。(極大值層節(jié)點的剪枝)第五章 高級搜尋局部搜尋算法遺傳算法第五章 高級搜尋局部搜尋算法改進1：針對陷入局部最優(yōu)，依確定概率選擇鄰域內(nèi)的點；改進2：針對等步長跳過全局最優(yōu)，改固定步長搜尋為變步長搜尋；改進３：針對初始點可能距離局部最優(yōu)點近，隨機選擇多個初始點。第五章 高級搜尋遺傳算法問題解的編碼定義適應(yīng)函數(shù)交配規(guī)則變異規(guī)則第六章基于邏輯的問題求解方法一階謂詞邏輯謂詞邏輯演算公式謂詞演算的基本等價式及推理規(guī)則謂詞公式的規(guī)范化前束范式SKOLEM范式謂詞公式化為子句集第六章基于邏輯的問題求解方法謂詞邏輯公式化為子句集的步驟：1.` 消去多余的前束（量詞），即在母式中無相應(yīng)變量的量詞。利用蘊涵等價式消去蘊涵符號（→）；利用摩根律內(nèi)移否定詞~的轄區(qū)范圍，使其僅作用于原子公式。4.變量標準化。將各約束變量換成不同的名字以免混淆。在一量詞的轄區(qū)內(nèi)，受該量詞約束的變量名可隨意設(shè)定（只要沒出現(xiàn)過），該過程不影響合式公式的真值。5. 利用量詞轄區(qū)變換律把量詞的轄區(qū)范圍擴充至整個WFF，得到一個前束范式。即把全部的量詞都集中在公式的左邊，移動時不要變更其相對依次。6.消去存在量詞，把所得的前束范式化為S范式。7. 把母式化成合取范式。反復(fù)運用結(jié)合律和支配律，將母式表達成合取范式的標準式（即用連接的公式)。8.略去全稱量詞。由于母式的變量均受全稱量詞的約束，可省略掉全稱量詞（不顯式地受全稱量詞量化）。9．用子句集表示母式。把母式中每一個合取元稱為一個子句，省去合取連接詞，這樣就可把母式寫成集合的形式表示，每個元素就是一個子句。10．子句變量標準化。將子句集合中的變量作分別標準化，即對某些變量重新命名，使隨意兩個子句不會有相同的變量出現(xiàn)。第六章基于邏輯的問題求解方法歸結(jié)法命題邏輯的歸結(jié)謂詞邏輯的歸結(jié)置換合一求最一般合一mgu第六章基于邏輯的問題求解方法歸結(jié)反演產(chǎn)生式系統(tǒng)基本算法（歸結(jié)反演樹）搜尋策略寬度優(yōu)先策略支持集策略單元子句優(yōu)先策略線性輸入策略祖先過濾形策略第六章基于邏輯的問題求解方法基于歸結(jié)法的問題解答系統(tǒng)提取問答的方法歸結(jié)反演樹：證明目標公式是前提公式集的邏輯推論；修改證明樹：歸結(jié)反演樹中目標公式的否定式用“目標公式的否定與目標公式的析取”替代，找出目標公式中變量的例。第七章基本推理技術(shù)基于規(guī)則的演繹推理正向演繹推理逆向演繹推理雙向演繹推理表達式化為標準與或形正向系統(tǒng)逆向系統(tǒng)skolem函數(shù)消去事實表達式中的存在量詞，化簡的公式受全稱量詞約束。skolem函數(shù)（對偶形）消去目標公式中的全稱量詞，化簡的公式受存在量詞約束。對規(guī)則的處理同上。對規(guī)則的處理同下。skolem函數(shù)（對偶形）消去目標公式中的全稱量詞，化簡的公式受存在量詞約束。skolem函數(shù)消去事實表達式中的存在量詞，化簡的公式受全稱量詞約束。表達式化為與或圖正向系統(tǒng)逆向系統(tǒng)根節(jié)點表示事實表達式；葉節(jié)點表示單文字；n連接符連接具有析取關(guān)系的子表達式；１連接符連接具有合取關(guān)系的子表達式；根節(jié)點表示目標表達式；葉節(jié)點表示單文字；n連接符連接具有合取關(guān)系的子表達式；１連接符連接具有析取關(guān)系的子表達式；演繹推理過程正向系統(tǒng)逆向系統(tǒng)規(guī)則的左部和與或圖的葉節(jié)點匹配；匹配成功的規(guī)則的結(jié)論加入與或圖；直到產(chǎn)生一個含有以目標節(jié)點作為終止節(jié)點的解圖為止。規(guī)則的右部和與或圖的葉節(jié)點匹配；匹配成功的規(guī)則的前提加入與或圖；直到產(chǎn)生一個含有已知事實節(jié)點作為終止節(jié)點的解圖為止。第七章基本推理技術(shù)雙向演繹推理分別從正反兩個方向進行推理，兩個與或圖分別擴展；當正反兩個方向的與或圖對應(yīng)的葉節(jié)點都可合一時，推理結(jié)束。第七章基本推理技術(shù)不確定性推理概率方法條件概率、全概率公式、Bayes公式概率推理復(fù)習要點及思索題其次章產(chǎn)生式系統(tǒng):通過八數(shù)碼游戲，了解產(chǎn)生式系統(tǒng)的問題描述(綜合數(shù)據(jù)庫、產(chǎn)生式規(guī)則、限制系統(tǒng))。思索習題：N=3時梵塔問題的產(chǎn)生式系統(tǒng)的描述(參考P55頁1.1題)第三章產(chǎn)生式系統(tǒng)的搜尋策略在深刻理解圖搜尋算法的基礎(chǔ)上，通過八數(shù)碼問題、傳教士和野人問題駕馭啟發(fā)式圖搜尋算法A和A*算法。思索習題：1.P55頁，1.3：旅行商問題中啟發(fā)式函數(shù)定義及A算法求解過程.（通過列出OPEN、CLOSED表確定擴展依次）2.P55頁，1.2：滑動積木塊游戲的A算法求解：BBWWEBWEWB初始狀態(tài)目標狀態(tài)第四章與或圖搜尋理解能解節(jié)點的定義，通過實例駕馭AO*搜尋過程；了解博弈問題的產(chǎn)生式描述；駕馭博弈樹的極大微小、-搜尋過程。思索習題:1.P75頁2.5題。2.P75頁2.6題。第五章高級搜尋理解組合優(yōu)化問題的特點，領(lǐng)域的概念。了解局部搜尋算法和遺傳算法的原理、過程、和特點。第六章基于邏輯的問題求解方法清晰一階謂詞邏輯的基本定義;深化理解歸結(jié)原理,通過實例駕馭謂詞邏輯的歸結(jié)過程(包括置換和合一)；并能利用歸結(jié)反演系統(tǒng)證明和求解一些簡潔的實際問題。思