西電人工智能確定性推理part

ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理搜索策略搜索策略搜索的基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性與效率與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索過程實際上是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。算法的每一步都試圖找到一個最有希望成為最優(yōu)解樹的子樹。最優(yōu)解樹是指代價最小的那棵解樹。它涉及到解樹的代價與希望樹。與/或樹的啟發(fā)式搜索解樹的代價:解樹的代價可按如下規(guī)則計算(1)若n為終止節(jié)點(diǎn)，則其代價h(n)=0；(2)若n為或節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1,n2,…,nk，則n的代價為：其中，c(n,ni)是節(jié)點(diǎn)n到其子節(jié)點(diǎn)ni的邊代價。(3)若n為與節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1,n2,…,nk，則n的代價可用和代價法或最大代價法。與/或樹的啟發(fā)式搜索解樹的代價:解樹的代價可按如下規(guī)則計算若用和代價法，則其計算公式為：若用最大代價法，則其計算公式為：(4)若n是端節(jié)點(diǎn)，但又不是終止節(jié)點(diǎn)，則n不可擴(kuò)展，其代價定義為h(n)=∝。(5)根節(jié)點(diǎn)的代價即為解樹的代價。與/或樹的啟發(fā)式搜索解樹的代價:設(shè)下圖是一棵與/或樹，它包括兩棵解樹左邊的解樹由S0、A、t1、C及t2組成；右邊的解樹由S0、B、t2、D及t4組成。在此與或樹中，t1、t2、t3、t4為終止節(jié)點(diǎn)；E、F是端節(jié)點(diǎn)；邊上的數(shù)字是該邊的代價。請計算解樹的代價。4635S022ABt1Ct2D21t3Et4F與/或樹的啟發(fā)式搜索解樹的代價:解：先計算左邊的解樹按和代價：h(S0)=2+4+6+2=14按最大代價：h(S0)=(2+6)+2=10再計算右邊的解樹按和代價：h(S0)=1+5+3+2=11按最大代價：h(S0)=(1+5)+2=84635S022ABt1Ct2D21t3Et4F與/或樹的啟發(fā)式搜索希望樹：希望樹是指搜索過程中最有可能成為最優(yōu)解樹的那棵樹。與/或樹的啟發(fā)式搜索過程就是不斷地選擇、修正希望樹的過程，在該過程中，希望樹是不斷變化的。希望樹的定義：(1)初始節(jié)點(diǎn)S0在希望樹T中(2)如果節(jié)點(diǎn)n在希望樹中，則一定有：如果n是具有子節(jié)點(diǎn)n1,n2,…,nk的或節(jié)點(diǎn)，則具有

值的那個子節(jié)點(diǎn)ni也應(yīng)在T中。如果n是與節(jié)點(diǎn)，則n的全部子節(jié)點(diǎn)都在希望樹T中。與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索過程(1)把初始節(jié)點(diǎn)S0放入OPEN表中；(2)求出希望樹T，即根據(jù)當(dāng)前搜索樹中節(jié)點(diǎn)的代價h求出以S0為根的希望樹T；(3)依次在OPEN表中取出T的端節(jié)點(diǎn)放入CLOSED表，并記該節(jié)點(diǎn)為n；節(jié)點(diǎn)n有三種不同情況：①n為終止節(jié)點(diǎn)，②n不是終止節(jié)點(diǎn)，但可擴(kuò)展，③n不是終止節(jié)點(diǎn)，且不可擴(kuò)展，對三種情況分別進(jìn)行步驟(4)(5)(6)的操作過程；與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索過程(4)如果節(jié)點(diǎn)n為終止節(jié)點(diǎn)，則：①標(biāo)記節(jié)點(diǎn)n為可解節(jié)點(diǎn)；②在T上應(yīng)用可解標(biāo)記過程，對n的先輩節(jié)點(diǎn)中的所有可解解節(jié)點(diǎn)進(jìn)行標(biāo)記；③如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn)，則T就是最優(yōu)解樹，成功退出；④否則，從OPEN表中刪去具有可解先輩的所有節(jié)點(diǎn)。⑤轉(zhuǎn)第(2)步。與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索過程(5)如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn)，但可擴(kuò)展，則：

①擴(kuò)展節(jié)點(diǎn)n，生成n的所有子節(jié)點(diǎn)；②把這些子節(jié)點(diǎn)都放入OPEN表中，并為每一個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)n的指針；③計算這些子節(jié)點(diǎn)及其先輩節(jié)點(diǎn)的h值；④轉(zhuǎn)第(2)步。與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索過程(6)如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn)，且不可擴(kuò)展，則：

①標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；②在T上應(yīng)用不可解標(biāo)記過程，對n的先輩節(jié)點(diǎn)中的所有不可解解節(jié)點(diǎn)進(jìn)行標(biāo)記；③如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為不可解節(jié)點(diǎn)，則問題無解，失敗退出；④否則，從OPEN表中刪去具有不可解先輩的所有節(jié)點(diǎn)。⑤轉(zhuǎn)第(2)步。與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索：設(shè)初始節(jié)點(diǎn)為S0，要求搜索過程每次擴(kuò)展節(jié)點(diǎn)時都同時擴(kuò)展兩層，且按一層或節(jié)點(diǎn)、一層與節(jié)點(diǎn)的間隔方式進(jìn)行擴(kuò)展。它實際上就是下一節(jié)將要討論的博弈樹的結(jié)構(gòu)。S0經(jīng)過擴(kuò)展后得到的與/或樹如右圖所示。其中，端節(jié)點(diǎn)B、C、E、F，下面的數(shù)字是用啟發(fā)函數(shù)估算出的h值；各個父節(jié)點(diǎn)到其子節(jié)點(diǎn)的代價為1。S0ADBCEF3332h(B)=3，h(C)=3h(E)=3，h(F)=2按照和代價計算得到：h(A)=8，h(D)=7h(S0)=8此時S0的右子樹是希望樹與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索：依次對當(dāng)前希望樹的端節(jié)點(diǎn)進(jìn)行擴(kuò)展。對節(jié)點(diǎn)E擴(kuò)展兩層后得到的與/或樹如右圖所示。節(jié)點(diǎn)S0、A、D、E、G、H旁邊的數(shù)字是按和代價法計算出來的節(jié)點(diǎn)代價。此時，由右子樹求出的h(S0)=12，由左子樹求出的h(S0)=9。顯然，左子樹的代價小。因此，當(dāng)前的希望樹應(yīng)改為左子樹。S09A8D11BCEF3372322276GH與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索：對節(jié)點(diǎn)B進(jìn)行擴(kuò)展，擴(kuò)展兩層后得到的與/或樹如下圖所示。2S09A8D11BCEF337232276LMNOPQ002226GH由于節(jié)點(diǎn)N和O是可解節(jié)點(diǎn)，故調(diào)用可解標(biāo)記過程，得節(jié)點(diǎn)L、B也為可解節(jié)點(diǎn)，但不能標(biāo)記S0為可解節(jié)點(diǎn)，須繼續(xù)擴(kuò)展。當(dāng)前的希望樹仍然是左子樹。與/或樹的啟發(fā)式搜索與/或樹的啟發(fā)式搜索：對節(jié)點(diǎn)C進(jìn)行擴(kuò)展，擴(kuò)展兩層后得到的與/或樹如下圖所示。S09A8D11BCEF3372322276LMNOPQ002226RST005229GH調(diào)用可解標(biāo)記過程，可標(biāo)記S0為可解節(jié)點(diǎn)，這就的到了代價最小的解樹。按和代價法，該最優(yōu)解的代價為9。

與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)博弈樹的啟發(fā)式搜索博弈的概念：博弈是一類具有智能行為的競爭活動，如下棋、戰(zhàn)爭等。博弈的類型：雙人完備信息博弈：兩位選手對壘，輪流走步，每一方不僅知道對方已經(jīng)走過的棋步，而且還能估計出對方未來的走步。機(jī)遇性博弈：存在不可預(yù)測性的博弈，例如擲幣等。博弈樹若把雙人完備信息博弈過程用圖表示出來，就得到一棵與/或樹，這種與/或樹被稱為博弈樹。博弈樹的啟發(fā)式搜索博弈樹在雙人完備信息博弈中，若將兩位對壘選手分別記為MAX和MIN，則博弈樹中，下一步該MAX走步的節(jié)點(diǎn)稱為MAX節(jié)點(diǎn)，該MIN走步的節(jié)點(diǎn)稱為MIN節(jié)點(diǎn)。博弈樹的特點(diǎn)：(1)博弈的初始狀態(tài)是初始節(jié)點(diǎn)；(2)博弈樹中的“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)逐層交替出現(xiàn)；(3)整個博弈過程始終站在某一方的立場上。所有能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。博弈樹的啟發(fā)式搜索極大極小分析法對簡單的博弈問題，可生成整個博弈樹，找到必勝的策略。對于復(fù)雜的博弈問題，不可能生成整個搜索樹，如國際象棋，大約有10120個節(jié)點(diǎn)。一種可行的方法是用當(dāng)前正在考察的節(jié)點(diǎn)生成一棵部分博弈樹，并利用估價函數(shù)f(n)對葉節(jié)點(diǎn)進(jìn)行靜態(tài)估值。對葉節(jié)點(diǎn)的估值方法：那些對MAX有利的節(jié)點(diǎn)，其估價函數(shù)取正值那些對MIN有利的節(jié)點(diǎn)，其估價函數(shù)取負(fù)值那些使雙方均等的節(jié)點(diǎn)，其估價函數(shù)取接近于0的值博弈樹的啟發(fā)式搜索極大極小分析法對非葉節(jié)點(diǎn)的估值方法：必須從葉節(jié)點(diǎn)開始向上倒推對于MAX節(jié)點(diǎn)，由于MAX方總是選擇估值最大的走步，因此，MAX節(jié)點(diǎn)的倒推值應(yīng)該取其后繼節(jié)點(diǎn)估值的最大值。對于MIN節(jié)點(diǎn)，由于MIN方總是選擇使估值最小的走步，因此MIN節(jié)點(diǎn)的倒推值應(yīng)取其后繼節(jié)點(diǎn)估值的最小值。這樣一步一步的計算倒推值，直至求出初始節(jié)點(diǎn)的倒推值為止。這一過程稱為極大極小過程。博弈樹的啟發(fā)式搜索博弈樹的例子：一子棋游戲設(shè)有一個三行三列的棋盤，如下圖所示，兩個棋手輪流走步，每個棋手走步時往空格上擺一個自己的棋子，誰先使自己的棋子成三子一線為贏。設(shè)MAX方的棋子用×標(biāo)記，MIN方的棋子用○標(biāo)記，并規(guī)定MAX方先走步。一子棋棋盤棋局1博弈樹的啟發(fā)式搜索博弈樹的例子：一子棋游戲解：定義估價函數(shù)：e(P)=e(+P)-e(-P)

e(+P)：P上有可能使×成三子為一線的數(shù)目；e(-P)：P上有可能使○成三子為一線的數(shù)目；

當(dāng)MAX必勝時，e(P)為正無窮大當(dāng)MIN必勝時，e(P)為負(fù)無窮大具有對稱性的棋盤可認(rèn)為是同一棋盤，例如：e(P)=e(+P)-e(-P)=5-4=1博弈樹的啟發(fā)式搜索一子棋的極大極小搜索S01S1S2S3-16-5=15-5=06-5=15-5=04-5=-15-4=16-4=25-6=-15-5=05-6=-16-6=04-6=-2S4S5-21MAX節(jié)點(diǎn)MAX節(jié)點(diǎn)MIN節(jié)點(diǎn)與/或樹的搜索策略與/或樹的搜索策略與/或樹的一般搜索過程與/或樹的廣度優(yōu)先搜索與/或樹的深度優(yōu)先搜索與/或樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索α-β剪枝技術(shù)α-β剪枝技術(shù)剪枝的概念：極大極小過程是先生成與/或樹，然后再計算各節(jié)點(diǎn)的估值，這種生成節(jié)點(diǎn)和計算估值相分離的搜索方式，需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn)，因此搜索效率較低。鑒于博弈樹具有“與”節(jié)點(diǎn)和“或”節(jié)點(diǎn)逐層交替出現(xiàn)的特點(diǎn)，如果能邊生成節(jié)點(diǎn)邊對節(jié)點(diǎn)估值，就有可能刪去一些不必要的節(jié)點(diǎn)，從而減少搜索及計算的工作量。例如：S0S452S1S2S33S5S63α-β剪枝技術(shù)α-β剪枝方法(1)MAX節(jié)點(diǎn)的α值為當(dāng)前子節(jié)點(diǎn)的最大到推值；(2)MIN節(jié)點(diǎn)的β值為當(dāng)前子節(jié)點(diǎn)的最小倒推值；(3)α-β剪枝的規(guī)則如下：任何MAX節(jié)點(diǎn)n的α值如果不能降低其父節(jié)點(diǎn)的β值，則n以下的分枝可停止搜索，并令節(jié)點(diǎn)n的倒推值為α。這種剪枝稱為β剪枝。任何MIN節(jié)點(diǎn)n的β值如果不能升高其父節(jié)點(diǎn)的α值，則n以下的分枝可停止搜索，并令節(jié)點(diǎn)n的倒推值為β。這種剪枝稱為α剪枝。α-β剪枝技術(shù)α-β剪枝的例子：≥4S0≤4A≦0≥4≥5≥0CDE0-6×IJ4≦1KLN461×FG5P58H×M8β值α值β值α值QR×≤0≦-6S××在α-β剪枝技術(shù)中：對于一個MAX節(jié)點(diǎn)，如果估值最高的子節(jié)點(diǎn)最先生成，或者對于一個MIN節(jié)點(diǎn)，如果估值最低的子節(jié)點(diǎn)最先生成，則被剪除的節(jié)點(diǎn)數(shù)最多，搜索效率最高。這稱為最優(yōu)α-β剪枝搜索策略搜索策略搜索的基本概念狀態(tài)空間的搜索策略與/或樹的搜索策略搜索的完備性與效率搜索的完備性與效率完備性對于一類可解的問題和一個搜索過程，如果運(yùn)用該搜索過程一定能求得該類問題的解，則稱該搜索過程為完備的，否則為不完備的。完備的搜索過程稱為“