人工智能與或圖搜索

人工智能與或圖搜索第1頁，課件共35頁，創(chuàng)作于2023年2月4.1問題歸約法當(dāng)問題復(fù)雜時，可把初始問題分解成若干簡單的子問題，若子問題仍復(fù)雜，可再進(jìn)一步分解，直到這些子問題的解可直接得到。這種問題的描述和求解方法，稱為問題歸約法?？芍苯咏獯鸬膯栴}稱為本原問題，它是不必證明的、自然成立的。歸約法的問題表示可由下列三部分組成：1）一個初始問題的描述；2）一組把問題變成子問題的算子；3）

一組本原問題的描述問題歸約由問題出發(fā)，運(yùn)用操作算子產(chǎn)生一些子問題，對子問題再運(yùn)用操作算子產(chǎn)生子問題的一些子問題，……，一直進(jìn)行到產(chǎn)生的子問題都為本原問題，則問題得解。由于一問題所產(chǎn)生的若干子問題內(nèi)的關(guān)系是并列的、同時的，所以，用與或圖便能表示問題歸約的狀態(tài)空間。即對問題歸約的描述可以很方便地用一個與或圖的結(jié)構(gòu)來表示它。第2頁，課件共35頁，創(chuàng)作于2023年2月4.2與或圖與節(jié)點：一個歸約算子能夠把單個問題變?yōu)閹讉€子問題組成的集合，這時只有當(dāng)所有子問題都有解，該父輩節(jié)點才有解。這種關(guān)系稱為“與”關(guān)系，對應(yīng)的節(jié)點稱為與節(jié)點?；蚬?jié)點：幾個算子適用于同一個問題，從而產(chǎn)生不同的后繼問題集合。這時只要有一個后繼集合有解，則意味該父輩問題有解，此時關(guān)系是“或”關(guān)系，對應(yīng)節(jié)點稱為或節(jié)點。與節(jié)點由與運(yùn)算連接，如圖（a）中Q和R，并用一條弧線將相關(guān)的邊連接起來，這種弧線及所相關(guān)的邊被稱為超弧?；蚬?jié)點由或運(yùn)算連接，如圖4-1（b）中Q和R。第3頁，課件共35頁，創(chuàng)作于2023年2月與或圖是一種普遍圖，這種圖被稱為超圖。也就是說，超圖是存在超弧的圖。一超弧所相關(guān)的邊數(shù)（K）被稱為該超弧的度，實現(xiàn)的連接為K-連接。K—連接符：假設(shè)節(jié)點N被某個算子歸約為一個包含K個子問題的替換集合，K1，我們用一個叫做K—連接符的超弧線把它們和節(jié)點N連接起來。每個K—連接符從一個父節(jié)點指向一個含有K個后繼節(jié)點的集合，并說N有一個外向連接符K。問題歸約描述對應(yīng)的結(jié)構(gòu)就是一個與或圖，原始問題描述對應(yīng)于起始節(jié)點（或根節(jié)點），本原問題所對應(yīng)的節(jié)點叫做葉節(jié)點。在某些特殊情況下，不出現(xiàn)任何與節(jié)點（所有超弧的度都為1），此時的圖成了普通圖，問題歸約描述也就成為狀態(tài)空間描述。

第4頁，課件共35頁，創(chuàng)作于2023年2月從圖4-2所示的與或圖中，節(jié)點n0有兩個連接符：1-連接符指向節(jié)點n1；2-連接符指向節(jié)點集合{n4、n5}；對于節(jié)點n0來講，n1可稱為或節(jié)點，n4、n5可稱為與節(jié)點。

圖4-2、與或圖第5頁，課件共35頁，創(chuàng)作于2023年2月4.3與或圖搜索在與或圖上執(zhí)行搜索的過程，其目的在于表明起始節(jié)點是有解的，也就是說，搜索不是去尋找目標(biāo)節(jié)點，而是尋找一個解圖。一個節(jié)點被稱為是能解節(jié)點(SOLVED)，其遞歸定義為：1．終節(jié)點是能解節(jié)點（直接與本原問題相關(guān)聯(lián)）；2．若非終節(jié)點有“或”子節(jié)點時，當(dāng)且僅當(dāng)其子節(jié)點至少有一個能解，該非終節(jié)點才能解；3．若非終節(jié)點有“與”子節(jié)點時，當(dāng)且僅當(dāng)其子節(jié)點均能解，該非終節(jié)點才能解。一個節(jié)點被稱為是不能解節(jié)點(UNSOLVED)，其遞歸定義為:

1．沒有后裔的非終節(jié)點是不能解的節(jié)點；2．若非終節(jié)點有“或”子節(jié)點時，當(dāng)且僅當(dāng)所有子節(jié)點均不能解時，該非終節(jié)點才不能解；3．若非終節(jié)點有“與”子節(jié)點時，當(dāng)至少有一子節(jié)點不能解時，該非終節(jié)點才不能解。第6頁，課件共35頁，創(chuàng)作于2023年2月一個解圖就是那些能解節(jié)點的子圖，是包含一節(jié)點（n）到目的節(jié)點集合（N）的、連通的能解節(jié)點的子圖。其定義如下：一個與或圖G中，從節(jié)點n到節(jié)點集N的解圖記為G，G是G的子圖。1．若n是N的一個元素，則G由單個節(jié)點n組成；2．若n有一個指向節(jié)點集{n1…,nk}的外向連接符K，使得從每一個節(jié)點ni到N有一個解圖(i=1,…,k)，則G由節(jié)點n，連接符K，以及{n1,…,nk}中的每一個節(jié)點到N的解圖所組成；3．否則n到N不存在解圖。第7頁，課件共35頁，創(chuàng)作于2023年2月如果n=s為初始節(jié)點，則此解圖即為所求解問題的解圖。在對普通圖的解路求解或搜索中，一般須計算或估計其路徑代價，同樣地，在搜索與或圖解圖的過程中，也需要進(jìn)行耗散值的計算。設(shè)連接符的耗散值規(guī)定為：k-連接符的耗散值=k，若解圖的耗散值記為k(n,N)，則可遞歸計算如下：1．若n是N的一個元素，則k(n,N)=0；2．若n有一個外向連接符指向后繼節(jié)點集合{n1…,ni}，并設(shè)該連接符的耗散值為Cn，則

k(n,N)=Cn+k(n1,N)+…+k(ni,N)。具有最小耗散值的解圖稱為最佳解圖，其值也用h*(n)標(biāo)記。求解問題的解圖的值為h*(s)。第8頁，課件共35頁，創(chuàng)作于2023年2月解圖的求法是：從節(jié)點n開始，正確選擇一個外向連接符，如此進(jìn)行下去直到由此產(chǎn)生的每一個后繼節(jié)點成為集合N中的一個元素為止。圖4-3給出了上圖所示與或圖中n0{n7，n8}的三個解圖（解圖的耗散值分別為8，7，5）。圖4-3、三個解圖

第9頁，課件共35頁，創(chuàng)作于2023年2月與或圖搜索與狀態(tài)空間圖搜索的不同：搜索目的是證明起始節(jié)點是否可解，而可解節(jié)點是遞歸定義的，取決于后繼節(jié)點是否可解，即搜索是否找到可解的葉節(jié)點。因此，搜索有可解標(biāo)示過程和不可解標(biāo)示過程。初始節(jié)點被標(biāo)示為可解，則搜索成功結(jié)束，初始節(jié)點被標(biāo)示為不可解，則搜索失敗。一旦發(fā)現(xiàn)不可解節(jié)點，應(yīng)把該節(jié)點從圖中刪去。第10頁，課件共35頁，創(chuàng)作于2023年2月4.4AO*算法假設(shè)：估價函數(shù)q(n)=h(n)；G為當(dāng)前擴(kuò)展生成的與或圖；G為一后選局部解圖，是G的一個子圖；h(n)是節(jié)點n的啟發(fā)函數(shù)；而q(n)是節(jié)點n的估價函數(shù)；是從節(jié)點n到一組終葉節(jié)點的一個最優(yōu)解圖的一個代價估計；

過程AO*:1.建立一個搜索圖G，G:=s，計算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；開始時圖G只包括s，耗散值估計為h(s)，若s是終節(jié)點,則標(biāo)記上能解。2.Untils已標(biāo)記為SOLVED,do:3.Begin4.G:=FIND(G)；根據(jù)連接符標(biāo)記（指針）找出一個待擴(kuò)展的局部解圖G（G的連接符將在第11步中標(biāo)記）。5.n:=G中的任一非終節(jié)點;選一個非終節(jié)點作為當(dāng)前節(jié)點。6.EXPAND(n),生成子節(jié)點集{ni}，G:=ADD({ni},G),計算

q(ni)=h(ni)，如果ni

G，IFGOAL(ni)THENM(ni,SOLVED);對G中原未出現(xiàn)的n的子節(jié)點添加到G中,并計算其耗散值，若n的子節(jié)點為終節(jié)點則加能解標(biāo)記。第11頁，課件共35頁，創(chuàng)作于2023年2月7

、S:=(n);建立含n的單一節(jié)點集合S.（待修正的節(jié)點集合）8、UntilS為空,do:9、begin10、REMOVE(m,S),當(dāng)mc

(S);從集合S中移出一節(jié)點m，要求這個m在圖G中的子節(jié)點mc,不出現(xiàn)在S中。（從底層開始修正）11

、根據(jù)下面方法修改m的耗散值q(m):

對m指向節(jié)點集(n1i，n2i,…nki)的每一個連接符i分別計算qi,qi(m)=Ci+q(n1i)+…+q(nki),q(m):=minqi(m);對m的i個k-連接符,取計算結(jié)果最小的那個連接符的耗散值為節(jié)點m的q(m)。

加指針到minqi(m)的連接符上,或把指針修改到minqi(m)的連接符上,即原來指針與新確定的不一致時應(yīng)刪去.IFM(nji,SOLVED)THENM(m,SOLVED);（j=1，2，…，k）若該連接符的所有子節(jié)點都是能解的,則m也標(biāo)上能解.12

、IFM(m,SOLVED)(q(m)q0(m))THENADD(ma,S);m能解或修正的耗散值與原先估算q0不同,則把m的所有先輩節(jié)點ma,添加到S中.（修正向上傳遞）13、end14、

end第12頁，課件共35頁，創(chuàng)作于2023年2月AO*搜索算法可以理解為兩個主要過程的重復(fù)。首先，是一個自上而下的圖生長過程（4-6步），先通過有標(biāo)記的連接符，找到目前為止最好的一個局部解圖，然后對其中一個非終節(jié)點進(jìn)行擴(kuò)展，并對其后繼節(jié)點賦估計耗散值和加能解標(biāo)記。第2過程是一個自下而上的估價函數(shù)值的修正、連接符的標(biāo)記和SOLVED的標(biāo)注過程。耗散值的修正從剛被擴(kuò)展的節(jié)點n開始，其修正耗散值q(n)取對h*(n)的所有估計值中最小的一個，然后根據(jù)耗散值遞歸計算公式逐級向上修正其先輩節(jié)點的耗散值，只有下層節(jié)點耗散值修正后，才可能影響到上一層節(jié)點的耗散值，因此必須自底向上一直修正到初始節(jié)點。第13頁，課件共35頁，創(chuàng)作于2023年2月假設(shè)各節(jié)點的啟發(fā)函數(shù)值分別為：h(n0)=3，h(n1)=2，h(n2)=4，h(n3)=4，h(n4)=1，h(n5)=1，h(n6)=2，h(n7)=h(n8)=0（目標(biāo)節(jié)點），k-連接符的耗散值=k。應(yīng)用AO*算法，經(jīng)過四個循環(huán)，可找到解圖。在第一次循環(huán)中，擴(kuò)展節(jié)點n0；下一次循環(huán)擴(kuò)展節(jié)點n1；接著擴(kuò)展節(jié)點n5；最后擴(kuò)展節(jié)點n4。在節(jié)點n4被擴(kuò)展之后，節(jié)點n0便被標(biāo)注SOLVED，此時，通過向下跟蹤有標(biāo)記的連接符，便獲得了此狀態(tài)空間的解圖。

第14頁，課件共35頁，創(chuàng)作于2023年2月圖4.4、AO*搜索過程每個節(jié)點旁邊標(biāo)記的是啟發(fā)函數(shù)h(n)值（不帶括號）或估價函數(shù)q（n）的修正值（帶括號）；短箭頭用來標(biāo)記連接符，標(biāo)明侯選局部解圖；已經(jīng)標(biāo)注SOLVED的節(jié)點用實心圓來表示。

第15頁，課件共35頁，創(chuàng)作于2023年2月4.5博弈樹的搜索博弈一直是啟發(fā)式搜索的一個重要應(yīng)用領(lǐng)域，早在20世紀(jì)60年代就已經(jīng)出現(xiàn)若干個博弈系統(tǒng)，美國IBM公司的“深藍(lán)”系統(tǒng)已達(dá)到了國際特級大師級的水平（97年勝了卡斯帕羅夫）。2001年，德國的“更弗里茨”軟件擊敗了世界排名10位中的9位。本節(jié)所指博弈問題是指二人完備博弈：1．由二人對壘，二人嚴(yán)格地輪流走步，自己的走步自己選擇，2．任何一方都完全知道對方過去的走步情況和今后可能的走步，不包括碰運(yùn)氣的情況。由于在決定自己走步時只需考慮對自己有利的一步——或，而考察對方時，則應(yīng)考慮對方所有可能的走步——與，因此，能夠利用與或圖搜索算法來解決博弈問題。另外，由于兩人嚴(yán)格地輪流走步，使博弈狀態(tài)圖呈現(xiàn)出嚴(yán)格的與或圖的交替層次，所以，可設(shè)計特殊的與或圖搜索算法——博弈樹搜索算法，使搜索更有效。第16頁，課件共35頁，創(chuàng)作于2023年2月4.5.1Grundy博弈例：假設(shè)桌上放有一堆（7個）錢幣，由兩人輪流進(jìn)行分堆，要求每人每次只把其中某堆錢幣分成數(shù)目不相等的兩小堆，最后不能分下去的人為負(fù)。該問題的描述：綜合數(shù)據(jù)庫：用無序數(shù)字序列x1，x2，…，xn表示n堆錢幣不同的個數(shù)，再用兩個說明符號MIN方和MAX方代表選手，無序數(shù)列和符號M組合（x1，x2，…，xn，M）就代表該由某個選手走步的狀態(tài)。MAX方代表努力贏的一方，或盡力將其贏的幾率最大化的一方；而MIN方代表力圖使MAX方偏離取勝目標(biāo)的另一方。博弈雙方總是偏向最有利于自己的狀態(tài)前進(jìn)，反過來說，也就是MIN方和MAX方總是移向最不利于對方的狀態(tài)。規(guī)則：第17頁，課件共35頁，創(chuàng)作于2023年2月圖4-5、Grundy博弈問題狀態(tài)空間圖設(shè)初始狀態(tài)為（7，MIN），則該問題的狀態(tài)空間圖如圖4-5所示，圖中所有終節(jié)點均表示要走步的選手必輸?shù)那闆r，取勝方的目標(biāo)是設(shè)法使棋局發(fā)展為結(jié)束在對方走步時的終節(jié)點上，因此節(jié)點A是MAX的搜索目標(biāo)，而節(jié)點B，C則為MIN的搜索目標(biāo)。第18頁，課件共35頁，創(chuàng)作于2023年2月搜索策略要考慮的問題是（以MAX方的角度）對MIN走步后的每一個MAX節(jié)點（該狀態(tài)由MIN控制），必須證明MAX對MIN所有可能走的每一個棋局對弈后都能夠獲勝，即MAX必須考慮應(yīng)付MIN的所有招法，這是一個與的含義，因此含有MAX符號的節(jié)點可看成與節(jié)點。對MAX走步后的每一個MIN節(jié)點（該狀態(tài)由MAX控制），只需要證明MAX有一步能走贏就可以，即MAX只要考慮能走出一步棋使MIN無法招架就成，因此含有MIN符號的節(jié)點可看成或節(jié)點。 于是對弈過程的搜索圖就呈現(xiàn)出與或圖表示的形式，從搜索圖可以看出，MAX方存在完全取勝的策略，圖中所示部分就代表了這種策略，這時不論MIN怎么走，MAX方均可取勝。因而尋找MAX的取勝的策略便和求與或圖的解圖(能解→能勝)一致起來，即MAX要獲勝，必須對所有與節(jié)點取勝，但只需對一個或節(jié)點取勝，這就是一個解圖。因此實現(xiàn)一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。第19頁，課件共35頁，創(chuàng)作于2023年2月4.5.2博弈樹的極大極小搜索法極大極小搜索法是考慮雙方對弈若干步之后，從可能的走步中選一步相對好的走步來走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。這需定義一個評價函數(shù)f，以便對棋局的勢態(tài)（節(jié)點）作出優(yōu)劣估值。一般規(guī)定有利于MAX的勢態(tài)，f(n)取正值;有利于MIN的勢態(tài)，f(n)取負(fù)值;勢均力敵，f(n):=0。若f(n):=，表示MAX方獲勝;若f(n):=-，表示MIN方獲勝。假定開始由MAX選擇走一步棋，如何選擇一步好棋？

首先，對給定的格局MAX給出可能的走法，然后MIN對MAX的每一步走法，又給出可能的走法，這樣進(jìn)行若干次（一定深度），得到一組端節(jié)點，每個端節(jié)點有相應(yīng)的靜態(tài)函數(shù)值，然后由底向上逐級計算倒推估值，在MIN處取其下層估值中最小者，在MAX處取其下層估值最大者。一直到MAX的開始棋局，取其下層估值中最大的格局作為要走的第一步。第20頁，課件共35頁，創(chuàng)作于2023年2月圖4-6是一個表示考慮兩步棋的例子，圖中端節(jié)點的數(shù)字是用靜態(tài)函數(shù)f(n)計算得到，其他節(jié)點應(yīng)用倒推的方法取值。

圖中A、B、C是MIN方要走步的節(jié)點，MAX方應(yīng)考慮其最壞的情況，故其估值應(yīng)分別取其子節(jié)點估值中最小者，而s是MAX走步的節(jié)點，可考慮最好的情況，故其估值應(yīng)取A、B、C值中最大者。這樣，確定了f(s)=-2，也就是說，相對較優(yōu)的走步是走向B，因為從B出發(fā)，對手不可能產(chǎn)生比f(s)=-2更差的效果。當(dāng)用端節(jié)點的靜態(tài)估計函數(shù)值求倒推值時，兩位選手應(yīng)采用不同的策略，從下往上逐層交替使用極大和極小的選值方法，故稱為極大極小過程。圖4-6、f(n)求值過程

第21頁，課件共35頁，創(chuàng)作于2023年2月下面說明極大極小過程MINLMAX(思維過程)：1.T:=(s,MAX)，OPEN:=(s)，CLOSED:=();開始時樹由初始節(jié)點構(gòu)成，OPEN表只含有S.2.LOOP1:IFOPEN=()THENGOLOOP2;3.n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);將n放到CLOSED表的前面，使第5步操作時深度大的節(jié)點優(yōu)先被取出。(OPEN表先進(jìn)先出,CLOSED表后進(jìn)先出)4.IFn可直接判定為贏,輸或平局THENf(n):=-0，GOLOOP1ELSEEXPAND(n){ni}，ADD({ni}，T)IFd{ni}kTHENADD({ni},OPEN),GOLOOP1ELSE計算f(ni);ni達(dá)到深度k,計算各端節(jié)點f值.第22頁，課件共35頁，創(chuàng)作于2023年2月5.LOOP2：IFCLOSED=NIL,THENGOLOOP3ELSEnd=FIRST(CLOSED);6.IF(nd

MAX)(f(nciMIN)有值)THENf(nd):=max{f(nci)},REMOVE(nd，CLOSED),GOLOOP2;

若MAX所有子節(jié)點均有值,則該MAX取其極大值.ELSEIF(nd

MIN)(f(nciMAX)有值)THENf(nd):=min{f(nci)},REMOVE(nd，CLOSED),GOLOOP2;

若MIN所有子節(jié)點均有值，則該MIN取其極小值.7.ELSEGOLOOP1;若有子節(jié)點的值待確定,進(jìn)入其它分支繼續(xù)進(jìn)行節(jié)點的擴(kuò)展.8.LOOP3:IFf(s)≠NILTHENEXIT(ENDM(Move,T));s有值,或則結(jié)束或標(biāo)記走步。第23頁，課件共35頁，創(chuàng)作于2023年2月例：在九宮格棋盤上，甲乙（MAX和MIN）二人輪流在空格中放入自己的棋子（一次一枚），誰先使自己的三子成一線就獲勝，設(shè)甲先走用（）表示，乙用（）表示，p表示某種格局，f(p)表示對格局的評價值。為便于討論，將棋盤的整行、整列或整條對角線稱為贏線。如果一條贏線上只有（）方的棋子或為空，而沒有對方的棋子，那么這條贏線就稱為（）方的贏線。f(p)定義如下：

1）MAX勝，f(p)=+2）MIN勝，f(p)=-

3）若p不是可定勝負(fù)的格局，則f(p)=fMAX(p)-fMIN(p)其中，fMAX(p)表示當(dāng)前棋局所有空格都放上MAX的棋子后，MAX的三個棋子成線的總數(shù)。同理，fMIN(p)表示當(dāng)前棋局所有空格都放上MIN的棋子后，MIN的三個棋子成線的總數(shù)。設(shè)考慮走兩步的搜索過程，利用棋盤對稱性的條件，則第一次調(diào)用算法產(chǎn)生的搜索樹如圖4-7所示，圖中端節(jié)點下面是計算的f(p)值，非端節(jié)點的倒推值標(biāo)記在圓圈內(nèi)。為了使初始節(jié)點具有最大的倒推值，可以看出第1步的最好走法是把棋子下到中央位置。第24頁，課件共35頁，創(chuàng)作于2023年2月圖4-7、一字棋第1階段的搜索樹√√√√√√√√√√√√√√√√

第25頁，課件共35頁，創(chuàng)作于2023年2月設(shè)MAX走完第一步后，MAX的對手是在上的格子下子，這時MAX就要在新的格局下調(diào)用算法，第2次產(chǎn)生的搜索樹如圖4-8所示。

圖4-8、一字棋第2階段的搜索樹

√√第26頁，課件共35頁，創(chuàng)作于2023年2月類似地第3次的搜索樹如圖4-9所示。至此MAX走完最好的走步后，不論MIN怎么走，都無法挽回敗局，因此只好認(rèn)輸了，否則還要進(jìn)行下面的搜索。圖4-9、一字棋第3階段的搜索樹

第27頁，課件共35頁，創(chuàng)作于2023年2月4.5.3-搜索過程在極大極小過程中，把生成樹和棋局估值兩個過程完全分離，即先生成全部的搜索樹，然后再進(jìn)行端節(jié)點靜態(tài)估值和倒推值計算，這使效率大大降低。如圖4-9中，其中一個MIN節(jié)點要全部生成A、B、C、D四個節(jié)點，然后還要逐個計算其靜態(tài)估值，最后在求倒推值階段，才賦給這個MIN節(jié)點的倒推值-。若兩個過程同時進(jìn)行，再根據(jù)一定的條件判斷，有可能盡早剪掉一些無用的分支，那么就可能減少搜索工作量，這是-搜索過程的基本思想。如：生成節(jié)點A后，馬上進(jìn)行靜態(tài)估值，得知f（A）=-后，就可以斷定再生成其余節(jié)點及進(jìn)行靜態(tài)計算是多余的，可以馬上對MIN節(jié)點賦倒推值-，絲毫不會影響MAX的最好優(yōu)先走步的選擇。為了使生成和估值過程緊密結(jié)合，采用有界深度優(yōu)先策略進(jìn)行搜索，這樣當(dāng)生成達(dá)到規(guī)定深度的節(jié)點時，就立即計算其靜態(tài)估值函數(shù)，而一旦某個非端節(jié)點有條件確定其倒推值時就立即計算賦值。第28頁，課件共35頁，創(chuàng)作于2023年2月圖4-10、一字棋第1階段-剪枝方法第29頁，課件共35頁，創(chuàng)作于2023年2月從圖4-10中標(biāo)記的節(jié)點生成順序號（也表示節(jié)點編號）看出，生成并計算完第6個節(jié)點后，第1個節(jié)點倒推值完全確定，可立即賦給倒推值-1。這時對初始節(jié)點來說，雖然其他子節(jié)點尚未生成，但由于S屬極大值層，可以推斷其倒推值不會小于

-1，我們稱極大值層的這個下界值為，即可以確定S的=-1。這說明S實際的倒推值絕不會比-1更小，具體的取值還取決于其他后繼節(jié)點的倒推值，因此繼續(xù)生成搜索樹。當(dāng)?shù)?個節(jié)點生成出來并計算得靜態(tài)估值為-1后，就可以斷定第7個節(jié)點的倒推值不可能大于-1，我們稱極小值層的這個上界值為，即可確定節(jié)點7的=-1。第30頁，課件共35頁，創(chuàng)作于2023年2月有了極小值層的值，很容易發(fā)現(xiàn)若≥時，節(jié)點7的其他子節(jié)點不必再生成，這不影響高一層極大值的選取，因S的極大值不可能比這個值還小，再生成無疑是多余的，因