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

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

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

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