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

1、人工智能技術(shù)導(dǎo)論總復(fù)習(xí)2022/7/15人工智能技術(shù)導(dǎo)論總復(fù)習(xí)第3章 圖搜索技術(shù)狀態(tài)圖知識(shí)表示狀態(tài)圖搜索窮舉式搜索啟發(fā)式搜索加權(quán)狀態(tài)圖搜索與或圖知識(shí)表示與或圖搜索啟發(fā)式與或樹搜索博弈樹搜索極小極大分析法-剪枝人工智能技術(shù)導(dǎo)論總復(fù)習(xí)狀態(tài)圖知識(shí)表示狀態(tài)空間（State Space）問題的狀態(tài)空間是一個(gè)表示該問題全部的可能狀態(tài)及相互關(guān)系的圖。一般用賦值有向圖，包含S：問題的可能有的初始狀態(tài)的集合；F：操作的集合；G：目標(biāo)狀態(tài)的集合。狀態(tài)空間常記為三元序列人工智能技術(shù)導(dǎo)論總復(fù)習(xí)狀態(tài)空間中問題求解（1）在狀態(tài)空間圖中，問題求解過程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)S0出發(fā)到達(dá)目標(biāo)狀態(tài)Sg的路徑問題，也就是尋找操

2、作序列的問題。狀態(tài)空間的解為三元組S0 ：某個(gè)初始狀態(tài)Sg ：某個(gè)目標(biāo)狀態(tài)O：把Qs變換成Qg的有限的操作序列O1,O2,On狀態(tài)轉(zhuǎn)換圖S1S3S2O1O2O3O4S0SgOn人工智能技術(shù)導(dǎo)論總復(fù)習(xí)狀態(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è)解。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)狀態(tài)圖搜索（1）窮舉式搜索廣度優(yōu)先深度優(yōu)先有界深度優(yōu)先啟發(fā)式搜索全局擇優(yōu)（廣度優(yōu)先搜索+h(x)）局部擇優(yōu)（深度優(yōu)先搜索+h(x)）人工智能技術(shù)導(dǎo)論總

3、復(fù)習(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)）人工智能技術(shù)導(dǎo)論總復(fù)習(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ù)導(dǎo)論總復(fù)習(xí)與或圖知識(shí)表示一個(gè)復(fù)雜的問題P常?？梢詺w約為與之等價(jià)的一組子問題，當(dāng)這些問題全部可解時(shí)，問題可解；任何一個(gè)子問題無解時(shí)，都將導(dǎo)致原問題P無解。即一個(gè)問題與一組子問題的與等價(jià)。一個(gè)復(fù)雜的問題P常常可以分

4、別歸約為與之等價(jià)的一組子問題，其中任何一個(gè)子問題可解時(shí)，問題可解；全部子問題無解時(shí)，原問題P無解。即一個(gè)問題與一組子問題的或等價(jià)。與或圖知識(shí)表示是一個(gè)三元組（Q0 , F , Qn）Q0：表示初始問題F ：表示問題變換規(guī)則集Qn ：表示本原問題集人工智能技術(shù)導(dǎo)論總復(fù)習(xí)與或圖知識(shí)表示（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è)與或圖，與或圖的

5、節(jié)點(diǎn)一般代表問題，整個(gè)圖就表示問題空間。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)與或圖搜索（1）與或圖知識(shí)表示搜索盲目式搜索啟發(fā)式搜索博弈樹搜索窮舉式搜索盲目碰撞搜索廣度優(yōu)先深度優(yōu)先人工智能技術(shù)導(dǎo)論總復(fù)習(xí)與或圖搜索（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)。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)與或圖搜索（3）有序搜索解樹（樹根）代價(jià)的計(jì)算

6、方法和代價(jià)法最大代價(jià)法有序搜索過程人工智能技術(shù)導(dǎo)論總復(fù)習(xí)啟發(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)人工智能技術(shù)導(dǎo)論總復(fù)習(xí)啟發(fā)式與或樹搜索a1a2a3a4a5a6b1b2b4b3b5S4456245732443例：如下圖所示的與或樹，a4,a5,a6,b3,b5是

7、終止結(jié)點(diǎn)，求其解樹人工智能技術(shù)導(dǎo)論總復(fù)習(xí)啟發(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ù)導(dǎo)論總復(fù)習(xí)博弈樹搜索極小極大分析法剪枝技術(shù)人工智能技術(shù)導(dǎo)論總復(fù)習(xí)極小極大分析法（1）極小極大分析法的基本思想設(shè)博弈的雙方中一方為A，另一方為B。然后為其中的一方(始終站在A的立場上)尋找一個(gè)最優(yōu)行動(dòng)方案。為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對各個(gè)可能的方案所產(chǎn)生的后果進(jìn)行比較。為計(jì)算得分，需要根據(jù)問題的特性信息定

8、義一個(gè)估價(jià)函數(shù)f(p)(p是端節(jié)點(diǎn))，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。這時(shí)估算出來的得分為靜態(tài)估值。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)極小極大分析法（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)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)方案。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)極小極大分析示例倒推值的計(jì)算 2-12-234-51322343323人

9、工智能技術(shù)導(dǎo)論總復(fù)習(xí)剪枝技術(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ù)導(dǎo)論總復(fù)習(xí)剪枝技術(shù)(1)293111368120357426187103ABCE

10、HJKPQDLDRTIFGMUNVS221122222660005060人工智能技術(shù)導(dǎo)論總復(fù)習(xí)-3504568-3193剪枝技術(shù)(2)3-3022-30-230-300-303305411-31661abcdefghijkmn當(dāng)前最佳走步0016610人工智能技術(shù)導(dǎo)論總復(fù)習(xí)剪枝技術(shù)(3)05-333-302-23541-308936N人工智能技術(shù)導(dǎo)論總復(fù)習(xí)第4章基于遺傳算法的隨機(jī)優(yōu)化搜索遺傳算法的基本概念遺傳算法和圖搜索在優(yōu)化搜索和問題求解方面的對比人工智能技術(shù)導(dǎo)論總復(fù)習(xí)第5章基于謂詞邏輯的機(jī)器推理相關(guān)定義及概念化子句集的過程命題邏輯的歸結(jié)原理替換與合一謂詞邏輯中的歸結(jié)原理應(yīng)用歸結(jié)原理求取問題

11、答案歸結(jié)策略人工智能技術(shù)導(dǎo)論總復(fù)習(xí)化子句集的過程1、消去蘊(yùn)含詞和等值詞。2、使否定詞僅作用于原子公式。3、適當(dāng)改名使量詞間不含同名指導(dǎo)變元。4、消去存在量詞。5、消去全稱量詞。6、化公式為合取范式。7、適當(dāng)改名，使子句間無同名變元。8、消去合取詞，以子句為元素組成一個(gè)集合S。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)命題邏輯的歸結(jié)原理設(shè)C1， C2是命題邏輯中的兩個(gè)子句 C1中有文字L1 ，C2中有文字L2 ，且L1與L2互補(bǔ)， 從C1 、 C2中分別刪除L1 、L2 ，再將剩余部分析取起來，記構(gòu)成的新子句為C1 2，則C1 2為C1 、 C2的歸結(jié)式。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)替換與合一一個(gè)替換（Substitut

12、ion）是形如 t1/x1, t2/x2, , tn/xn的有限集合設(shè)是原子公式集S的一個(gè)合一，如果對S的任何一個(gè)合一都存在一個(gè)替換，使得 則稱為S的最一般合一(Most General Unifier),簡稱MGU。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)謂詞邏輯中的歸結(jié)原理C1，C2為無相同變元的子句； L1，L2為其中的兩個(gè)文字， L1和L2有最一般合一； C1，C2的二元?dú)w結(jié)式（二元消解式）為： C1 L1 ）（ C2 L2 ）人工智能技術(shù)導(dǎo)論總復(fù)習(xí)應(yīng)用歸結(jié)原理求取問題答案（1）先為待求解的問題找一個(gè)合適的求證目標(biāo)謂詞；（2）再對目標(biāo)否定子句增配（以析取形式）一個(gè)輔助謂詞，該謂詞的變元必須與對應(yīng)目標(biāo)謂詞

13、中的變元完全一致；（3）進(jìn)行歸結(jié)；（4）當(dāng)歸結(jié)是剛好只剩下輔助謂詞時(shí)，輔助謂詞中原變元位置上的項(xiàng)就是所求的結(jié)果。人工智能技術(shù)導(dǎo)論總復(fù)習(xí)歸結(jié)策略刪除策略支持集策略線性歸結(jié)策略輸入歸結(jié)策略單元?dú)w結(jié)策略祖先過濾型策略人工智能技術(shù)導(dǎo)論總復(fù)習(xí)第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)的控制策略與常用算法（正向，反向）人工智能技術(shù)導(dǎo)論總復(fù)習(xí)第7章 知識(shí)表示框架語義網(wǎng)絡(luò)類和對象人工智能技術(shù)導(dǎo)論總復(fù)習(xí)第8章 不確定性知識(shí)的表示和推理確定性理論主觀貝葉斯方法證據(jù)理論貝葉斯網(wǎng)絡(luò)模糊邏輯人工智能技術(shù)導(dǎo)論總復(fù)習(xí)第9章 機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)的原理機(jī)器學(xué)習(xí)分類機(jī)器學(xué)習(xí)的方法符號(hào)學(xué)習(xí)：決策樹學(xué)習(xí)