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

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

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