人工智能技術導論總復習

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

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

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