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

ArtificialIntelligence(AI)

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

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

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

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

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

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

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