西電人工智能11確定性推理part4

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ù)術(shù)與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索過程程實(shí)際上上是一種種利用搜搜索過程程所得到到的啟發(fā)發(fā)性信息息尋找最最優(yōu)解樹樹的過程程。算法的每每一步都都試圖找找到一個個最有希望望成為最最優(yōu)解樹樹的子樹樹。最優(yōu)解樹樹是指代價價最小的的那棵解解樹。它涉及到到解樹的代代價與希望樹。與/或樹的啟啟發(fā)式搜搜索解樹的代代價:解樹的代代價可按按如下規(guī)規(guī)則計(jì)算算(1)若n為終止節(jié)點(diǎn)點(diǎn)，則其代代價h(n)=0；(2)若n為或節(jié)點(diǎn)，且子節(jié)節(jié)點(diǎn)為n1,n2,…,,nk，則n的代價為為：其中，c(n,ni)是節(jié)點(diǎn)n到其子節(jié)節(jié)點(diǎn)ni的邊代價價。(3)若n為與節(jié)點(diǎn)，且子節(jié)節(jié)點(diǎn)為n1,n2,…,,nk，則n的代價可可用和代價法法或最大代價價法。與/或樹的啟啟發(fā)式搜搜索解樹的代代價:解樹的代代價可按按如下規(guī)規(guī)則計(jì)算算若用和代代價法，，則其計(jì)計(jì)算公式式為：若用最大大代價法法，則其其計(jì)算公公式為：：(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é)節(jié)點(diǎn)；E、F是端節(jié)點(diǎn)點(diǎn)；邊上上的數(shù)字字是該邊邊的代價價。請計(jì)算解解樹的代代價。4635S022ABt1Ct2D21t3Et4F與/或樹的啟啟發(fā)式搜搜索解樹的代代價:解：先計(jì)計(jì)算左邊邊的解樹樹按和代價價：h(S0)=2++4+6+2==14按最大代代價：h(S0)=(2+6))+2==10再計(jì)算右右邊的解解樹按和代價價：h(S0)=1++5+3+2==11按最大代代價：h(S0)=(1+5))+2==84635S022ABt1Ct2D21t3Et4F與/或樹的啟啟發(fā)式搜搜索希望樹：：希望樹是是指搜索索過程中中最有可可能成為為最優(yōu)解解樹的那那棵樹。。與/或樹的啟啟發(fā)式搜搜索過程程就是不不斷地選擇、修修正希望樹的的過程，，在該過過程中，，希望樹是是不斷變變化的。希望樹的的定義：：(1)初始節(jié)點(diǎn)點(diǎn)S0在希望樹樹T中(2)如果節(jié)點(diǎn)點(diǎn)n在希望樹樹中，則則一定有有：如果n是具有子子節(jié)點(diǎn)n1,n2,…,,nk的或節(jié)點(diǎn)，則具有有

值的那個個子節(jié)點(diǎn)點(diǎn)ni也應(yīng)在T中。如果n是與節(jié)點(diǎn)，則n的全部子節(jié)節(jié)點(diǎn)都在希望望樹T中。與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索過程程(1)把初始節(jié)節(jié)點(diǎn)S0放入OPEN表中；(2)求出希望望樹T，即根據(jù)據(jù)當(dāng)前搜搜索樹中中節(jié)點(diǎn)的的代價h求出以S0為根的希希望樹T；(3)依次在OPEN表中取出出T的端節(jié)點(diǎn)點(diǎn)放入CLOSED表，并記記該節(jié)點(diǎn)點(diǎn)為n；節(jié)點(diǎn)n有三種不不同情況況：①n為終止節(jié)節(jié)點(diǎn)，②n不是終止止節(jié)點(diǎn)，，但可擴(kuò)擴(kuò)展，③n不是終止止節(jié)點(diǎn)，，且不可可擴(kuò)展，，對三種種情況分分別進(jìn)行行步驟(4)((5))(6)的操作過過程；與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索過程程(4)如果節(jié)點(diǎn)點(diǎn)n為終止節(jié)點(diǎn)點(diǎn)，則：①標(biāo)記節(jié)節(jié)點(diǎn)n為可解節(jié)節(jié)點(diǎn)；②在T上應(yīng)用可可解標(biāo)記記過程，，對n的先輩節(jié)節(jié)點(diǎn)中的的所有可可解解節(jié)節(jié)點(diǎn)進(jìn)行行標(biāo)記；；③如果初初始解節(jié)節(jié)點(diǎn)S0能夠被標(biāo)標(biāo)記為可可解節(jié)點(diǎn)點(diǎn)，則T就是最優(yōu)優(yōu)解樹，，成功退退出；④否則，，從OPEN表中刪去去具有可可解先輩輩的所有有節(jié)點(diǎn)。。⑤轉(zhuǎn)第(2)步。與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索過程程(5)如果節(jié)點(diǎn)點(diǎn)n不是終止止節(jié)點(diǎn)，，但可擴(kuò)擴(kuò)展，則則：①擴(kuò)展節(jié)節(jié)點(diǎn)n，生成n的所有子子節(jié)點(diǎn)；；②把這些些子節(jié)點(diǎn)點(diǎn)都放入入OPEN表中，并并為每一一個子節(jié)節(jié)點(diǎn)設(shè)置置指向父父節(jié)點(diǎn)n的指針；；③計(jì)算這這些子節(jié)節(jié)點(diǎn)及其其先輩節(jié)節(jié)點(diǎn)的h值；④轉(zhuǎn)第(2)步。與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索過程程(6)如果節(jié)點(diǎn)點(diǎn)n不是終止止節(jié)點(diǎn)，，且不可可擴(kuò)展，，則：①標(biāo)記節(jié)節(jié)點(diǎn)n為不可解解節(jié)點(diǎn)；；②在T上應(yīng)用不不可解標(biāo)標(biāo)記過程程，對n的先輩節(jié)節(jié)點(diǎn)中的的所有不不可解解解節(jié)點(diǎn)進(jìn)進(jìn)行標(biāo)記記；③如果初初始解節(jié)節(jié)點(diǎn)S0能夠被標(biāo)標(biāo)記為不不可解節(jié)節(jié)點(diǎn)，則則問題無無解，失失敗退出出；④否則則，從OPEN表中刪去去具有不不可解先先輩的所所有節(jié)點(diǎn)點(diǎn)。⑤轉(zhuǎn)第第(2)步。與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索：設(shè)初始節(jié)節(jié)點(diǎn)為S0，要求搜搜索過程程每次擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)時都同同時擴(kuò)展展兩層，，且按一一層或節(jié)節(jié)點(diǎn)、一一層與節(jié)節(jié)點(diǎn)的間間隔方式式進(jìn)行擴(kuò)擴(kuò)展。它實(shí)際上上就是下下一節(jié)將將要討論論的博弈弈樹的結(jié)結(jié)構(gòu)。S0經(jīng)過擴(kuò)展展后得到到的與/或樹如右右圖所示示。其中中，端節(jié)節(jié)點(diǎn)B、C、E、F，下面的的數(shù)字是是用啟發(fā)發(fā)函數(shù)估估算出的的h值；各個父節(jié)節(jié)點(diǎn)到其其子節(jié)點(diǎn)點(diǎn)的代價價為1。S0ADBCEF3332h(B)=3，h(C)=3h(E)=3，h(F)=2按照和代代價計(jì)算算得到：：h(A)=8，h(D)=7h(S0)=8此時S0的右子樹樹是希望望樹與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索：依次對當(dāng)當(dāng)前希望望樹的端端節(jié)點(diǎn)進(jìn)進(jìn)行擴(kuò)展展。對節(jié)節(jié)點(diǎn)E擴(kuò)展兩層層后得到到的與/或樹如右右圖所示示。節(jié)點(diǎn)點(diǎn)S0、A、D、E、G、H旁邊的數(shù)數(shù)字是按按和代價價法計(jì)算算出來的的節(jié)點(diǎn)代代價。此時，由由右子樹樹求出的的h(S0)=12，由左子子樹求出出的h(S0)=9。顯然，，左子樹樹的代價價小。因因此，當(dāng)前的希希望樹應(yīng)應(yīng)改為左左子樹。S09A8D11BCEF3372322276GH與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索：對節(jié)點(diǎn)B進(jìn)行擴(kuò)展展，擴(kuò)展展兩層后后得到的的與/或樹如下下圖所示示。2S09A8D11BCEF337232276LMNOPQ002226GH由于節(jié)點(diǎn)點(diǎn)N和O是可解節(jié)節(jié)點(diǎn)，故故調(diào)用可可解標(biāo)記記過程，，得節(jié)點(diǎn)點(diǎn)L、B也為可解解節(jié)點(diǎn)，，但不能能標(biāo)記S0為可解節(jié)節(jié)點(diǎn)，須須繼續(xù)擴(kuò)擴(kuò)展。當(dāng)前的希希望樹仍仍然是左左子樹。與/或樹的啟啟發(fā)式搜搜索與/或樹的啟啟發(fā)式搜搜索：對節(jié)點(diǎn)C進(jìn)行擴(kuò)展展，擴(kuò)展展兩層后后得到的的與/或樹如下下圖所示示。S09A8D11BCEF3372322276LMNOPQ002226RST005229GH調(diào)用可解解標(biāo)記過過程，可可標(biāo)記S0為可解節(jié)節(jié)點(diǎn)，這這就的到到了代價價最小的的解樹。。按和代代價法，，該最優(yōu)解解的代價價為9。與/或樹的搜搜索策略略與/或樹的搜搜索策略略與/或樹的一一般搜索索過程與/或樹的廣廣度優(yōu)先先搜索與/或樹的深深度優(yōu)先先搜索與/或樹的啟啟發(fā)式搜搜索博弈樹的的啟發(fā)式式搜索α-β剪枝技術(shù)術(shù)博弈樹的的啟發(fā)式式搜索博弈的概概念：博弈是一一類具有有智能行行為的競競爭活動動，如下下棋、戰(zhàn)戰(zhàn)爭等。。博弈的類類型：雙人完備備信息博博弈：兩位選手手對壘，，輪流走走步，每每一方不不僅知道道對方已已經(jīng)走過過的棋步步，而且且還能估估計(jì)出對對方未來來的走步步。機(jī)遇性博博弈：存在不可可預(yù)測性性的博弈弈，例如如擲幣等等。博弈樹若把雙人人完備信信息博弈弈過程用用圖表示示出來，，就得到到一棵與與/或樹，這這種與/或樹被稱稱為博弈樹。博弈樹的的啟發(fā)式式搜索博弈樹在雙人完完備信息息博弈中中，若將將兩位對對壘選手手分別記記為MAX和MIN，則博弈弈樹中，，下一步步該MAX走步的節(jié)節(jié)點(diǎn)稱為為MAX節(jié)點(diǎn)，該該MIN走步的節(jié)節(jié)點(diǎn)稱為為MIN節(jié)點(diǎn)。博弈樹的的特點(diǎn)：：(1)博弈的初初始狀態(tài)態(tài)是初始始節(jié)點(diǎn)；；(2)博弈樹中中的“或或”節(jié)點(diǎn)點(diǎn)和“與與”節(jié)點(diǎn)點(diǎn)逐層交交替出現(xiàn)現(xiàn)；(3)整個博弈弈過程始始終站在在某一方方的立場場上。所所有能使使自己一一方獲勝勝的終局局都是本本原問題題，相應(yīng)應(yīng)的節(jié)點(diǎn)點(diǎn)是可解節(jié)點(diǎn)點(diǎn)；所有使使對方獲獲勝的終終局都是是不可解節(jié)節(jié)點(diǎn)。博弈樹的的啟發(fā)式式搜索極大極小小分析法法對簡單的的博弈問問題，可可生成整整個博弈弈樹，找找到必勝勝的策略略。對于復(fù)雜雜的博弈弈問題，，不可能能生成整整個搜索索樹，如如國際象象棋，大大約有10120個節(jié)點(diǎn)。。一種種可行的的方法是是用當(dāng)前前正在考考察的節(jié)節(jié)點(diǎn)生成成一棵部分博弈弈樹，并利用用估價函數(shù)數(shù)f(n)對葉節(jié)點(diǎn)點(diǎn)進(jìn)行靜靜態(tài)估值值。對葉節(jié)點(diǎn)點(diǎn)的估值值方法：：那些對MAX有利的節(jié)節(jié)點(diǎn)，其其估價函函數(shù)取正值那些對MIN有利的節(jié)節(jié)點(diǎn)，其其估價函函數(shù)取負(fù)值那些使雙雙方均等等的節(jié)點(diǎn)點(diǎn)，其估估價函數(shù)數(shù)取接近近于0的值博弈樹的的啟發(fā)式式搜索極大極小小分析法法對非葉節(jié)節(jié)點(diǎn)的估估值方法法：必須從葉葉節(jié)點(diǎn)開開始向上上倒推對于MAX節(jié)點(diǎn)，由由于MAX方總是選擇估值值最大的的走步，因此，，MAX節(jié)點(diǎn)的倒倒推值應(yīng)應(yīng)該取其其后繼節(jié)節(jié)點(diǎn)估值值的最大大值。對于MIN節(jié)點(diǎn)，由由于MIN方總是選擇使估估值最小小的走步步，因此MIN節(jié)點(diǎn)的倒倒推值應(yīng)應(yīng)取其后后繼節(jié)點(diǎn)點(diǎn)估值的的最小值值。這樣一步步一步的的計(jì)算倒倒推值，，直至求求出初始始節(jié)點(diǎn)的的倒推值值為止。。這一過過程稱為為極大極小小過程。博弈樹的的啟發(fā)式式搜索博弈樹的的例子：：一子棋游游戲設(shè)有一個個三行三三列的棋棋盤，如如下圖所所示，兩兩個棋手手輪流走走步，每每個棋手手走步時時往空格格上擺一一個自己己的棋子子，誰先先使自己己的棋子子成三子子一線為為贏。設(shè)設(shè)MAX方的棋子子用×標(biāo)記，MIN方的棋子子用○標(biāo)標(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)認(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ù)α-β剪枝技術(shù)術(shù)剪枝的概概念：極大極小小過程是是先生成成與/或樹，然然后再計(jì)計(jì)算各節(jié)節(jié)點(diǎn)的估估值，這這種生成成節(jié)點(diǎn)和和計(jì)算估估值相分分離的搜搜索方式式，需要要生成規(guī)規(guī)定深度度內(nèi)的所所有節(jié)點(diǎn)點(diǎn)，因此此搜索效效率較低低。鑒于博弈弈樹具有有“與””節(jié)點(diǎn)和和“或””節(jié)點(diǎn)逐逐層交替替出現(xiàn)的的特點(diǎn)，，如果能能邊生成節(jié)節(jié)點(diǎn)邊對對節(jié)點(diǎn)估估值，就就有可能能刪去一一些不必必要的節(jié)節(jié)點(diǎn)，從從而減少少搜索及及計(jì)算的的工作量量。例如：S0S452S1S2S33S5S63α-β剪枝技術(shù)術(shù)α-β剪枝方法法(1)MAX節(jié)點(diǎn)的α值為當(dāng)前前子節(jié)點(diǎn)點(diǎn)的最大大到推值值；(2)MIN節(jié)點(diǎn)的β值為當(dāng)前前子節(jié)點(diǎn)點(diǎn)的最小小倒推值值；(3)α-β剪枝的規(guī)規(guī)則如下下：任何MAX節(jié)點(diǎn)n的α值如果不不能降低低其父節(jié)節(jié)點(diǎn)的β值，則n以下的分分枝可停停止搜索索，并令令節(jié)點(diǎn)n的倒推值值為α。這種剪剪枝稱為為β剪枝。任何MIN節(jié)點(diǎn)n的β值如果不不能升高高其父節(jié)節(jié)點(diǎn)的α值，則n以下的分分枝可停停止搜索索，并令令節(jié)點(diǎn)n的倒推值值為β。這種剪剪枝稱為為α剪枝。α-β剪枝技術(shù)術(shù)α-β剪枝的例例子：≥4S0≤4A≦0≥4≥5≥0CDE0-6×IJ4≦1KLN461×FG5P58H×M8β值α值β值α值QR×≤0≦-6S××在α-β剪枝技術(shù)術(shù)中：對對于一個個MAX節(jié)點(diǎn)，如如果估值值最高的的子節(jié)點(diǎn)點(diǎn)最先生生成，或或者對于于一個MIN節(jié)點(diǎn)，如如果估值值最低的的子節(jié)點(diǎn)點(diǎn)最先生生成，則則被剪除除的節(jié)點(diǎn)點(diǎn)數(shù)最多多，搜索索效率最最高。這這稱為最優(yōu)α-β剪枝搜索策略略搜索策略略搜索的基基本概念念狀態(tài)空間間的搜索索策略與/或樹的搜搜索策略略搜索的完完備性與與效率搜索的完完備性與與效率完備性對于一類類可解的問問題和一個搜搜索過程程，如果果運(yùn)用該該搜索過過程一定定能求得得該類問問題的解解，則稱稱該搜索索過程為為完備的，否則為為不完備的的。完備的搜搜索過程程稱為““搜索算算法”。。不完備備的搜索索過程不不是算法法，稱為為“過程程”。廣度優(yōu)先先搜索、、代價樹樹的廣度度優(yōu)先搜搜索、改改進(jìn)后的的有界深深度優(yōu)先先搜索以以及A*算法都是是完備的的搜索過過程，其其它搜索索過程都都是不完完備的。。搜索的完完備性與與效率搜索效率率一個搜索索過程的的搜索效效率不僅僅取決于于過程自自身的啟啟發(fā)能