人工智能技術(shù)導(dǎo)論總復(fù)習(xí)

第1章人工智能概述什么是人工智能？人工智能的研究目標(biāo)和意義？人工智能的研究學(xué)派、途徑與方法人工智能的研究目標(biāo)人工智能的分支領(lǐng)域（基于應(yīng)用領(lǐng)域）人工智能基本技術(shù)第3章圖搜索技術(shù)狀態(tài)圖知識(shí)表示狀態(tài)圖搜索窮舉式搜索啟發(fā)式搜索加權(quán)狀態(tài)圖搜索與或圖知識(shí)表示與或圖搜索啟發(fā)式與或樹(shù)搜索博弈樹(shù)搜索極小極大分析法α-β剪枝狀態(tài)圖知識(shí)表示狀態(tài)空間（StateSpace）問(wèn)題的狀態(tài)空間是一個(gè)表示該問(wèn)題全部的可能狀態(tài)及相互關(guān)系的圖。一般用賦值有向圖，包含S：?jiǎn)栴}的可能有的初始狀態(tài)的集合；F：操作的集合；G：目標(biāo)狀態(tài)的集合。狀態(tài)空間常記為三元序列<S，F(xiàn)，G>狀態(tài)空間中問(wèn)題求解（1）在狀態(tài)空間圖中，問(wèn)題求解過(guò)程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)S0出發(fā)到達(dá)目標(biāo)狀態(tài)Sg的路徑問(wèn)題，也就是尋找操作序列的問(wèn)題。狀態(tài)空間的解為三元組<S0,O,Sg>S0：某個(gè)初始狀態(tài)Sg：某個(gè)目標(biāo)狀態(tài)O：把Qs變換成Qg的有限的操作序列{O1,O2,…,On}狀態(tài)轉(zhuǎn)換圖S1S3S2…O1O2O3O4S0SgOn狀態(tài)空間中問(wèn)題求解（2）狀態(tài)圖搜索：從初始節(jié)點(diǎn)出發(fā)，沿著與之相連的邊試探地前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)的過(guò)程。狀態(tài)圖的解：搜索成功后，從目標(biāo)結(jié)點(diǎn)反向沿搜索樹(shù)按所作標(biāo)記追溯一直到初始結(jié)點(diǎn)，所得到一條從初始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑就是問(wèn)題的一個(gè)解。狀態(tài)圖搜索（1）窮舉式搜索廣度優(yōu)先深度優(yōu)先有界深度優(yōu)先啟發(fā)式搜索全局擇優(yōu)（廣度優(yōu)先搜索+h(x)）局部擇優(yōu)（深度優(yōu)先搜索+h(x)）狀態(tài)圖搜索（2）加權(quán)狀態(tài)圖搜索分支界限（廣度優(yōu)先搜索+g(x)）最近擇優(yōu)/瞎子爬山（深度優(yōu)先搜索+g(x)）A算法（一般樹(shù)式搜索算法+f(x)）A*算法（h(x)<=h*(x)）或圖（狀態(tài)圖）知識(shí)表示搜索窮舉式搜索啟發(fā)式搜索加權(quán)狀態(tài)圖搜索廣度優(yōu)先深度優(yōu)先全局擇優(yōu)(最好優(yōu)先)局部擇優(yōu)(瞎子爬山)分支界限(最小代價(jià)優(yōu)先)最近優(yōu)先(瞎子爬山)A算法和A*算法與或圖知識(shí)表示一個(gè)復(fù)雜的問(wèn)題P常?？梢詺w約為與之等價(jià)的一組子問(wèn)題，當(dāng)這些問(wèn)題全部可解時(shí)，問(wèn)題可解；任何一個(gè)子問(wèn)題無(wú)解時(shí)，都將導(dǎo)致原問(wèn)題P無(wú)解。即一個(gè)問(wèn)題與一組子問(wèn)題的與等價(jià)。一個(gè)復(fù)雜的問(wèn)題P常常可以分別歸約為與之等價(jià)的一組子問(wèn)題，其中任何一個(gè)子問(wèn)題可解時(shí)，問(wèn)題可解；全部子問(wèn)題無(wú)解時(shí)，原問(wèn)題P無(wú)解。即一個(gè)問(wèn)題與一組子問(wèn)題的或等價(jià)。與或圖知識(shí)表示是一個(gè)三元組（Q0,F,Qn）Q0：表示初始問(wèn)題F：表示問(wèn)題變換規(guī)則集Qn：表示本原問(wèn)題集與或圖知識(shí)表示（1）與或圖的幾個(gè)概念直接可解的問(wèn)題稱(chēng)為本原問(wèn)題。本原問(wèn)題對(duì)應(yīng)的節(jié)點(diǎn)稱(chēng)為終止節(jié)點(diǎn)。無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為端節(jié)點(diǎn)。子節(jié)點(diǎn)為與關(guān)系，則該節(jié)點(diǎn)為與節(jié)點(diǎn)。子節(jié)點(diǎn)為或關(guān)系，則該節(jié)點(diǎn)為或節(jié)點(diǎn)。與或圖一般表示問(wèn)題的變換過(guò)程，就是從原問(wèn)題出發(fā)，運(yùn)用某些規(guī)則不斷的進(jìn)行問(wèn)題的分解（得到與分支）和變換（得到或分支），而得到一個(gè)與或圖，與或圖的節(jié)點(diǎn)一般代表問(wèn)題，整個(gè)圖就表示問(wèn)題空間。與或圖搜索（1）與或圖知識(shí)表示搜索盲目式搜索啟發(fā)式搜索博弈樹(shù)搜索窮舉式搜索盲目碰撞搜索廣度優(yōu)先深度優(yōu)先與或圖搜索（2）與或樹(shù)搜索可解性判定廣度優(yōu)先、有界深度優(yōu)先與或圖搜索：與或圖中搜索不像在或圖（狀態(tài)圖）中只是尋找目標(biāo)節(jié)點(diǎn)，而是邊擴(kuò)展節(jié)點(diǎn)邊進(jìn)行邏輯判斷，以確定初始結(jié)點(diǎn)是否可解。一旦確定初始節(jié)點(diǎn)的可解性，搜索停止。根據(jù)返回指針可從搜索樹(shù)中得到一個(gè)解圖（樹(shù)）。與或圖的解：是由可解節(jié)點(diǎn)形成的一個(gè)子圖（樹(shù)），這個(gè)子圖（樹(shù)）的根為初始節(jié)點(diǎn)，葉為終止節(jié)點(diǎn)。與或圖搜索（3）有序搜索解樹(shù)（樹(shù)根）代價(jià)的計(jì)算方法和代價(jià)法最大代價(jià)法有序搜索過(guò)程啟發(fā)式與或樹(shù)搜索解樹(shù)代價(jià)的計(jì)算方法令：g(x)表示節(jié)點(diǎn)x的代價(jià)，c(x,yi)表示節(jié)點(diǎn)x到其子節(jié)點(diǎn)yi的代價(jià)(即邊xyi的代價(jià))，yi是x的子節(jié)點(diǎn).則(1)若x是終止節(jié)點(diǎn)，g(x)＝0；(2)若x是或節(jié)點(diǎn)(3)若x是與節(jié)點(diǎn)，則有兩種計(jì)算公式。①和代價(jià)法②最大代價(jià)法(4)對(duì)非終止的端節(jié)點(diǎn)x，g(x)＝∞xy1y2c(x,y1)c(x,y2)xy1y2c(x,y1)c(x,y2)啟發(fā)式與或樹(shù)搜索a1a2a3a4a5a6b1b2b4b3b5S4456245732443例：如下圖所示的與或樹(shù)，a4,a5,a6,b3,b5是終止結(jié)點(diǎn)，求其解樹(shù)啟發(fā)式與或樹(shù)搜索左解樹(shù)節(jié)點(diǎn)a6a5a4a3a2a1S和代價(jià)000462125最大代價(jià)000441014右解樹(shù)節(jié)點(diǎn)b5b4b3b2b1S和代價(jià)030151923最大代價(jià)030101418補(bǔ)充示例：如下圖所示的與或樹(shù)，其解樹(shù)和節(jié)點(diǎn)相應(yīng)代價(jià)如下博弈樹(shù)搜索極小極大分析法α－?剪枝技術(shù)極小極大分析法（1）極小極大分析法的基本思想設(shè)博弈的雙方中一方為A，另一方為B。然后為其中的一方(始終站在A(yíng)的立場(chǎng)上)尋找一個(gè)最優(yōu)行動(dòng)方案。為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)可能的方案所產(chǎn)生的后果進(jìn)行比較。為計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)f(p)(p是端節(jié)點(diǎn))，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分。這時(shí)估算出來(lái)的得分為靜態(tài)估值。極小極大分析法（2）當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算出父節(jié)點(diǎn)的得分，推算的方法是：對(duì)“或”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大的得分作為父節(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個(gè)對(duì)自己最有利的方案；對(duì)“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小的得分作為父節(jié)點(diǎn)的得分，這是為了立足于最壞的情況。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱(chēng)為倒推值。如果一個(gè)行動(dòng)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)方案。極小極大分析示例倒推值的計(jì)算2-12-234-51322343323α－?剪枝技術(shù)對(duì)于一個(gè)與節(jié)點(diǎn)MIN,若能估計(jì)出其倒推值的上確界β,并且這個(gè)β值不大于MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確界α,即α≥β,則就不必再擴(kuò)展該MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MIN父節(jié)點(diǎn)的倒推值已無(wú)任何影響了)。這一過(guò)程稱(chēng)為α剪枝。對(duì)于一個(gè)或節(jié)點(diǎn)MAX,若能估計(jì)出其倒推值的下確界α,并且這個(gè)α值不小于MAX的父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值的上確界β,即α≥β,則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MAX父節(jié)點(diǎn)的倒推值已無(wú)任何影響了)。這一過(guò)程稱(chēng)為β剪枝。α－?剪枝技術(shù)(1)2931－1－1368－1203－574－26－18－7－103ABCEHJKPQDLDRTIFGMUNVS2≥2≤1≤－12≤222≥26≥60≥0≤0≤－5060-3504568-3193α－?剪枝技術(shù)(2)3-3022-30-230-3≤0≥0≤-3≤03≥3≥0≤5≤41≥1≤-3≤1≤6≥61abcdefghijkmn當(dāng)前最佳走步0016610α－?剪枝技術(shù)(3)05-333-302-23541-3089－36N第4章基于遺傳算法的隨機(jī)優(yōu)化搜索遺傳算法的基本概念遺傳算法和圖搜索在優(yōu)化搜索和問(wèn)題求解方面的對(duì)比第5章基于謂詞邏輯的機(jī)器推理相關(guān)定義及概念化子句集的過(guò)程命題邏輯的歸結(jié)原理替換與合一謂詞邏輯中的歸結(jié)原理應(yīng)用歸結(jié)原理求取問(wèn)題答案歸結(jié)策略化子句集的過(guò)程1、消去蘊(yùn)含詞和等值詞。2、使否定詞僅作用于原子公式。3、適當(dāng)改名使量詞間不含同名指導(dǎo)變?cè)?、消去存在量詞。5、消去全稱(chēng)量詞。6、化公式為合取范式。7、適當(dāng)改名，使子句間無(wú)同名變?cè)?、消去合取詞，以子句為元素組成一個(gè)集合S。命題邏輯的歸結(jié)原理設(shè)C1，

C2是命題邏輯中的兩個(gè)子句C1中有文字L1，C2中有文字L2，且L1與L2互補(bǔ)，從C1、C2中分別刪除L1、L2，再將剩余部分析取起來(lái)，記構(gòu)成的新子句為C12，則C12為C1、C2的歸結(jié)式。替換與合一一個(gè)替換（Substitution）是形如{t1/x1,t2/x2,…,tn/xn}的有限集合設(shè)σ是原子公式集S的一個(gè)合一，如果對(duì)S的任何一個(gè)合一θ都存在一個(gè)替換λ，使得θ＝σ?λ則稱(chēng)σ為S的最一般合一(MostGeneralUnifier),簡(jiǎn)稱(chēng)MGU。謂詞邏輯中的歸結(jié)原理C1，C2為無(wú)相同變?cè)淖泳?；L1，L2為其中的兩個(gè)文字，L1和?L2有最一般合一σ；C1，C2的二元?dú)w結(jié)式（二元消解式）為：C1σ－{L1σ}）∪（C2σ－{L2σ}）應(yīng)用歸結(jié)原理求取問(wèn)題答案

（1）先為待求解的問(wèn)題找一個(gè)合適的求證目標(biāo)謂詞；（2）再對(duì)目標(biāo)否定子句增配（以析取形式）一個(gè)輔助謂詞，該謂詞的變?cè)仨毰c對(duì)應(yīng)目標(biāo)謂詞中的變?cè)耆恢?；?）進(jìn)行歸結(jié)；（4）當(dāng)歸結(jié)是剛好只剩下輔助謂詞時(shí)，輔助謂詞中原變?cè)恢蒙系捻?xiàng)就是所求的結(jié)果。歸結(jié)策略刪除策略支持集策略線(xiàn)性歸結(jié)策略輸入歸結(jié)策略單元?dú)w結(jié)策略祖先過(guò)濾型策略第6章產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)的組成產(chǎn)生式系統(tǒng)的運(yùn)行過(guò)程產(chǎn)生式系統(tǒng)有哪幾種推理方式？各自有什么特點(diǎn).產(chǎn)生式系統(tǒng)的控制策略與常用算法（正向，反向）第7章知識(shí)表示框架語(yǔ)義網(wǎng)絡(luò)類(lèi)和對(duì)象第8章不確定性知識(shí)的表示和推理確定性理論主觀(guān)貝葉斯方法證據(jù)理論貝葉斯網(wǎng)絡(luò)模糊邏輯第9章機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)的原理機(jī)器學(xué)習(xí)分類(lèi)機(jī)器學(xué)習(xí)的方法符號(hào)學(xué)習(xí)：決策樹(shù)學(xué)習(xí)（ID3算