人工智能課程回顧

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