人工智能導(dǎo)論-與或圖搜索問題

2章與或圖搜索問題的關(guān)系。這就是本章要的與或圖搜索問題。中法可以求解問題，則該問題被求解。也就是說，對(duì)求解該問題來說，方法之間是“或”的關(guān)系。但在用每法求解時(shí)，又可能需要求解幾個(gè)子問題，這些子通常要與或圖的一般情況（與或樹是其特例。在一個(gè)與或圖中，一個(gè)cab的后繼節(jié)點(diǎn)。在這關(guān)的。為了避免不清，通常不把與或圖點(diǎn)叫做與節(jié)點(diǎn)或者或節(jié)點(diǎn)，而是引入一個(gè)適合于與或圖的更一般的標(biāo)記而在稱謂上沿用仍把這種結(jié)構(gòu)稱作與或圖。當(dāng)然在與或樹時(shí)仍繼續(xù)用“與“或”節(jié)點(diǎn)的稱呼。2.1（或連接符kk（相當(dāng)于一條弧線然這就是一般圖的標(biāo)記法，得到的就是與或圖的特例——普通圖。2.12.1n0有兩個(gè)連接符：1-n1；2-連接符指向節(jié)點(diǎn)集{n4，n5}2-連接符還用一小段圓弧括起來（k＞1k-連接符都應(yīng)有小n0來說，n4、n5是兩個(gè)“與”節(jié)點(diǎn)，而n1n8n5n4的一個(gè)“或”節(jié)點(diǎn)，是對(duì)應(yīng)的一組終節(jié)點(diǎn)；產(chǎn)生式系統(tǒng)的任務(wù)是搜索從初始節(jié)點(diǎn)到一組終節(jié)點(diǎn)集N的一nN的一個(gè)解圖類似于普通圖中的一條解路徑。N2.2n0→{n7，n8}的三個(gè)解圖。 2.2GnN的解圖記為G，GG②nN的一個(gè)元素，則G②若n有一個(gè)指向節(jié)點(diǎn){n1，…，nk}的外向連接符K，使得從每一個(gè)niN有一個(gè)解圖（i=1，…，k，則G由節(jié)點(diǎn)n、連接符K、及{n1，…，nk}中的每一個(gè)節(jié)點(diǎn)到N的解圖所組成；n到N同樣可以遞歸定義局部圖：nnK，則該局部圖、KKnnNn是一個(gè)外向連接符指向后繼節(jié)點(diǎn){n1，…，ni}Cnk(n，N)＝Cn+k(n1，N)+…+根據(jù)這個(gè)定義，在假定k連接符的耗散值為k的情況下，圖2.2三個(gè)解圖的耗散值計(jì)算結(jié)果分別為8、7和5。具有最小耗散值的解圖稱為最佳解圖，其值也用h*(n)h*(n0)＝5。同樣，也可以計(jì)算一個(gè)局部圖的耗散值。如果同樣將局部圖的耗散值記②nn有一個(gè)外向連接符指向后繼節(jié)點(diǎn){n1，…，ni}Cnk(n，N)＝Cn+k(n1，N)+…+其中，h(n)n到目標(biāo)節(jié)點(diǎn)集的最佳解圖耗散值的估計(jì)。nn下面首先AO*算法本身，然后再通過示例說明搜索過程以及與A*算法的某AO*GG:＝sq(s)＝（sIF（sSOVED；Gsh(s)s是終節(jié)點(diǎn)，則標(biāo)記上能解。②Untils④G':＝FIND(G)；根據(jù)連接符標(biāo)記（指針）找出一個(gè)待擴(kuò)展的圖G'⑤n:＝G'⑥EXAND(n){nj}q(nj)＝h(nj)G)，IFGOAL(nj)THENM(nj，SOLVED)G中未出現(xiàn)的子節(jié)點(diǎn)計(jì)算耗散值，若有nG中。⑦S:＝{n}nS⑧UntilS⑨ REMOVE(m，S)，mcSmmcS ·m對(duì)m指向節(jié)點(diǎn)集{n1i，n2i，…，nki}的每接符i分別計(jì)算qi：q(m):＝minqi(m)mi個(gè)連接符，取計(jì)算結(jié)果最小的那個(gè)耗q(m)?！inqi(m)minqi(m)的連接符)m IFTHENADD(ma，S)；m能解或修正的耗散值與原先估算q0不mmaS中。 14這個(gè)算法可劃分成兩個(gè)操作階段：第一階段是4—6步，完成自頂向下的圖生成操作，先通過有標(biāo)記的連接符，找到目前為止最好的一個(gè)圖，然后對(duì)其中一個(gè)非終節(jié)點(diǎn)進(jìn)行擴(kuò)展，并對(duì)其后繼節(jié)點(diǎn)賦估計(jì)耗散值和加能解標(biāo)記。第二階段是7—12耗散值的修正從剛被擴(kuò)展的節(jié)點(diǎn)n開始，其修正耗散值q（n）取估計(jì)h（n）的h（n，為了使用方便，將h(n)函數(shù)對(duì)圖2.1中各節(jié)點(diǎn)的假想估值先列寫如下（實(shí)際應(yīng)用h(n)定義式計(jì)算：此外假設(shè)k-連接符的耗散值為k2.3AO*2.1n0n0nn4和n51－連n2n4n52，h(41，h(5)=1k。所以n01n0的耗散值（qq）為（01）＋（n1q值）1＋＝3n1q值用h（20的20q值為n024q（n5的q值）＝2＋1＋1＝4。在兩個(gè)不同計(jì)算得到的耗散值中取最小值作為q值，并設(shè)置一個(gè)指針指向提供該耗散值的連接符。在這里3<4n0q值為2.3（a）所示。n0開始，沿指針?biāo)赶虻倪B接符，尋找一個(gè)未擴(kuò)展的非終節(jié)點(diǎn)。這時(shí)找到的是n1節(jié)點(diǎn)。擴(kuò)展n1節(jié)點(diǎn)，生成出節(jié)點(diǎn)n2和n3，兩個(gè)節(jié)點(diǎn)分別通過1－連接符與n1連接。由于h(n2)=h(n3)=4，所以通過這兩個(gè)連接符計(jì)算的耗散值也一樣，均為5。取其最小者還是5，從而更新n1的q值為5。由于耗散值相等，所n3這一邊。由n1q25，所以需要從新計(jì)算n0q值。n0來說，此時(shí)1－連接符這邊算得的耗散值為6，大于從2－連接符這邊得到的耗散值4，所以n0的q412－連接符。注意，n1出發(fā)的指向連接符的指針并沒有被改變或刪除。至此第二循環(huán)結(jié)束，搜索2.3（b）所示。n0開始，沿指針?biāo)赶虻倪B接符，尋找未擴(kuò)展的非終選擇的是n5。n5生成出n6、n7和n8三個(gè)節(jié)點(diǎn)1－連接符指向n62－連接符指向n7和n8。計(jì)算的結(jié)果，得到n5q值為2，指針指向2－連接符。由于n5qn0的q5n0n0q值即可，不需要改變指向連接33211

4454415554242055424200 1

51 0

2.3AO*4（e）在本次循環(huán)中，由于n7和n8都是目標(biāo)節(jié)點(diǎn)，是能解節(jié)點(diǎn)，而n5通過一個(gè)2－連接符連接n7n8，所以n5也被標(biāo)記為能解節(jié)點(diǎn)。雖然n5是能解節(jié)點(diǎn)，但由于n0是通第四次循環(huán)，同樣的道理，從n0開始沿指針?biāo)赶虻倪B接符，尋找未擴(kuò)展的非n4n4n5n81－連接符連接。n4n53（n5q2，n4qn5h值n8這邊計(jì)1n4的q1n8這邊的n4qn0q值也不需重新計(jì)算了。由于n8n41n8n4也被標(biāo)記為n0n0n0開始，沿2.3（e）為得到的解圖。6n時(shí)，若不存在后繼節(jié)點(diǎn)（即陷入死胡同，則可在第11步中對(duì)m（即n）賦一個(gè)高的q值，這個(gè)高的q值會(huì)依次傳遞到s，使得含有節(jié)點(diǎn)n的子圖具有高的q（s，從而排除了被當(dāng)作候選圖的可能性。5G′中的一個(gè)非終節(jié)點(diǎn)來擴(kuò)展呢？一般可以選一個(gè)最可能導(dǎo)致該圖耗散值發(fā)生較大變化的那個(gè)節(jié)點(diǎn)先擴(kuò)展，因?yàn)檫x這個(gè)節(jié)點(diǎn)先擴(kuò)展，會(huì)促使及時(shí)修改圖的標(biāo)記。單調(diào)限制條件時(shí)，則AO*一定能找到最佳解圖，即AO*具有可采納性。當(dāng)h（n）≡0這里單調(diào)限制條件是指：對(duì)隱含圖中，從節(jié)點(diǎn)n→{n1，…，nk}的每接符h（n）≤C+h（n1）+…+h（nk）C是連接符的耗散值。h（ti）＝0（ti∈Nh（n）≤h*（n*A*算法不能Ak有關(guān)子節(jié)點(diǎn)，對(duì)父節(jié)點(diǎn)能解與否以及耗散值都有影響，因而顯然不能象A*AENCLOSED*有關(guān)AO*算法的具體應(yīng)用及一些提高搜索效率的修正算法，可進(jìn)一步參閱人工這里所講的博弈指的是類似于象棋這樣的問題這類問題有以下一些特點(diǎn)（2）信息完備，對(duì)壘雙方所得到的信息是一（3零和。即對(duì)一方有利的棋，而另一方輸，或者雙方和棋。60年代就已經(jīng)出現(xiàn)若干博弈程序，并達(dá)到一定水平。博弈問題的研究還不斷提出一方則輸，或者雙方和局。這類博弈的實(shí)例有：一字棋、、西洋跳棋、國(guó)際面舉一個(gè)簡(jiǎn)單的例子說明博弈問題可用與或圖表示并搜索策略應(yīng)考慮的實(shí)際(2,2,2,1,(3,3,1,(2,2,2,1,(3,3,1,Grundy(4,2,1,(5,1,1,(5,2,(6,1,undy博是一個(gè)分錢幣的。有一堆數(shù)目為N的錢幣，由兩位選手輪流(4,2,1,(5,1,1,(5,2,(6,1,(4,3,(4,3,(7,(3,2,1,1,(3,2,1,1,(4,1,1,1,(3,2,2,C(3,1,1,1,1,(3,1,1,1,1,(2,2,1,1,1,A(2,1,1,1,1,1,B(2,1,1,1,1,1,2.4Grundy（7，MINAMAXB，CMIN的搜索目標(biāo)。MIN走步后的每一個(gè)MAX節(jié)點(diǎn)，必須證明MAXMIN可能走的每一個(gè)棋MAXMIN的所有招法，這是一個(gè)與的含意，因MAX符號(hào)的節(jié)點(diǎn)可看成與節(jié)點(diǎn)。MAXMINMAX有一步能走贏就可以，即MAXMINMIN符號(hào)的節(jié)點(diǎn)可看么走，MAXMAX的取勝策略便和求與或圖的解圖一致起來，MAX要取勝，必須對(duì)所有與節(jié)點(diǎn)取勝，但只需對(duì)一個(gè)或節(jié)點(diǎn)取勝，這就是一個(gè)解Grundy這種較簡(jiǎn)單的博弈，或者復(fù)雜博弈的殘局，可以用類似于與或圖的4050步，則搜索的位置有（402）50≈10160100用策略的基本點(diǎn)。下面就來這種機(jī)理的搜索策略——極小極大搜索過程。00時(shí)，表示棋局對(duì)我方不利，對(duì)對(duì)方有利。而評(píng)價(jià)函數(shù)值越大，表示對(duì)我有利。當(dāng)評(píng)價(jià)函數(shù)值等于正無窮大時(shí)，表示我方必勝評(píng)價(jià)函數(shù)值越小表示對(duì)我不利當(dāng)評(píng)價(jià)函數(shù)值等于負(fù)無窮大時(shí)，應(yīng)MIN的勢(shì)態(tài)，f（p）取負(fù)值，勢(shì)均力敵的勢(shì)態(tài)，f（p）0f（p）＝＋∞，則表示MAX贏，若f（p）＝－∞，則表示MIN贏。下面的規(guī)定：頂節(jié)點(diǎn)d＝0，MAX代表程序方，MIN代表對(duì)手方，MAX先走。f（p）估計(jì)，因?yàn)椴粔蚓_，而應(yīng)用倒推的辦法取值。例如A、B、C是MIN走步的節(jié)點(diǎn)，MAX應(yīng)考慮的情況，故其估值應(yīng)分別取其子節(jié)f（p）sMAX走步的節(jié)點(diǎn)，可考慮最好的情況，故估值應(yīng)取A、B、Cf（s）＝－2，依此確定了相對(duì)較優(yōu)的走步應(yīng)是走BBf（s）＝－2更差的效果。實(shí)際上可根據(jù)資源條件，考慮層次的搜索過程，從而可得到更準(zhǔn)確的倒推值，供MAX選取更正f（p）求倒推值時(shí)，兩位選手應(yīng)采取不同的策ss

MAX

MINDEFGHIJ(-(-(-(-2.5f(p) OPENs。②LOOP1:IF )THENGO③n:＝④IFnTHENf(n):＝∞∨－∞∨0，GOLOOP1IFd(ni)＜kTHENADD({ni}，OPEN)，GOELSEf(ni)，GOLOOP1；nIkf⑤LOOP2：IFCLOSED＝NILTHENGOELSEnp:＝MAX取其極大值。(THENf(np):＝min{f(ncj)}，REMOVE(LOSED)；若MIN所有子節(jié)點(diǎn)均MIN取其極小值。⑦GO—f（s）為止，此時(shí)f(s): minf(niii

1 s，重復(fù)調(diào)用該過3×3MAX-1-6-MAX-1-6- 5- 6-5-5-6-1 5- 6- 110MAX110MAX4-3- 5-3-4-3-14- 3- 5-3-4-3=14-04- 4- 5-3-4-4- 2.7

4- 4- 3-f(p)規(guī)定如下：ppMAXf(p)＝∞；pMINf(p)＝－∞。p111-2- 3- 2- 3--1-2- 3- 2- 3---2- 2-2---ABCD- 3- 2- 3--2- 3- 3-ABCD

初始節(jié) - 2-

3-2.82.6f(p)值，非端節(jié)點(diǎn)的倒推值標(biāo)記在圓圈MAX走完第一步后，MAXMAX就要2.8所示。至此MAX走完最好的走步后，不論MIN怎么走，都無法挽回?cái)【?，因?β2.8MINA、B、C、D四個(gè)節(jié)點(diǎn)，然后還要逐個(gè)計(jì)算MIN節(jié)點(diǎn)的倒推值－∞。其實(shí)，如MIN節(jié)點(diǎn)賦倒推值－∞，而絲毫不

s1

MAX

-

9

6- 5- 6- 5- 5- 6-2.9一字棋第一階段α-β定其倒推值時(shí)就立即計(jì)算賦值從圖2.9中標(biāo)記的節(jié)點(diǎn)生成順序（也表示節(jié)點(diǎn)）61個(gè)節(jié)點(diǎn)倒推值完全確定，可立即賦給倒推值－1s屬極大值層，可以推斷其倒推值不會(huì)小于－1，稱極大值層的這個(gè)下界值為α，即可以確定s的＝－1s實(shí)際的倒推值決不會(huì)比－1817個(gè)節(jié)點(diǎn)的倒推值不可能大于－1，極小值層的這個(gè)上界值為β，即可確定節(jié)點(diǎn)７的β＝－1β值，很容易發(fā)現(xiàn)若α≥β7的其他sβ值αβ剪枝，統(tǒng)稱為α-β剪枝技術(shù)。在實(shí)際修剪過程中，α、β還可以隨時(shí)修正，但極大值層的倒推值下界αβ歸納一下以上，可將α-β過程的剪枝規(guī)則描述如下MIN節(jié)點(diǎn)最終的倒推值就確定為這個(gè)β值MAX節(jié)點(diǎn)的最終倒推值就確定為這個(gè)α值。在進(jìn)行α-β（1）比較都是在極小節(jié)點(diǎn)和極大節(jié)23（4）α-β剪枝方法搜索得到的最佳走步與極小極大方法得到的結(jié)果是一致的，α-β剪枝并沒有因?yàn)樘岣咝剩档偷玫阶?上進(jìn)行剪枝。如果這樣，就失去了α-β剪枝方法的意義。在實(shí)際程序?qū)崿F(xiàn)時(shí)，首先MINIMAX方法所得完全相同，因而α-β過程具有較高的效 14 32β9 14 32β91325 31581221 2430β24720181623 27 29 101517192226 28

-

- -2.10α-β210d4的博弈樹的αβ態(tài)估值及倒推值過程的次序。該圖詳細(xì)表示出α-β剪枝過程的若干細(xì)節(jié)。初始節(jié)點(diǎn)的最終倒推值為1該值等于某一個(gè)端節(jié)點(diǎn)的靜態(tài)估值最好優(yōu)先走步是1這條路徑走下去，這要看對(duì)手的實(shí)際響應(yīng)而定。2.10的搜索，來說明α-β首先，從根節(jié)點(diǎn)開始，向下生成出到達(dá)指定節(jié)點(diǎn)深度的節(jié)點(diǎn)1，由1的值為0，可知2≤0，繼續(xù)擴(kuò)展生成節(jié)點(diǎn)3，由于3的值52的值0，并且節(jié)點(diǎn)2再也沒有其它的子節(jié)點(diǎn)了，所以4（與2是同一個(gè)節(jié)點(diǎn)）的值確定為04的值，可以確定5≥0。擴(kuò)展節(jié)點(diǎn)5，按順序生成節(jié)點(diǎn)766的值-37≤-37是極小節(jié)點(diǎn)，其值小于它的先輩節(jié)點(diǎn)5的值，滿足α剪枝條件7的其他子節(jié)點(diǎn)被剪掉，不5899序生成節(jié)點(diǎn)12110，由10＝3得到1＝312≥312是極大節(jié)點(diǎn)，其值大于其先912全部被剪掉。這樣9的子節(jié)點(diǎn)也全部搜索完，得到13＝0，并上推到14≥0。擴(kuò)展14的151617191719182021212322232321所以在23處發(fā)生剪枝（注意，此處即便是23的值不小于21的值，但由于23的值小于1424＝1252526＝627≤628＝8293030253031＝1。至此全部搜索結(jié)束，根節(jié)點(diǎn)32的值就是對(duì)當(dāng)前棋局的評(píng)判。由于該值來自于根節(jié)點(diǎn)的右邊一個(gè)子節(jié)點(diǎn)