第4章與或圖搜索

第四章與或圖搜索1問(wèn)題歸約法2與或圖3與或圖搜索4AO*算法5博弈樹(shù)的搜索問(wèn)題:在邊長(zhǎng)為2的正方形內(nèi)，任意放置5個(gè)點(diǎn)，求證其中必存在兩個(gè)點(diǎn)，它們之間的距離不大于2。問(wèn)題可轉(zhuǎn)化為：在四個(gè)單位正方形內(nèi)，任意放置5個(gè)點(diǎn)，至少有兩個(gè)點(diǎn)在同一正方形內(nèi)。1問(wèn)題歸約法問(wèn)題:假定我們已經(jīng)會(huì)求矩形的面積，現(xiàn)在要求如圖所示的五邊形的面積。方法分析:五邊形的面積轉(zhuǎn)化為矩形面積。IIIII①②③123I求解步驟：求五邊形面積求1面積求2面積求3面積求I面積求II面積求III面積求①面積求②面積求③面積123IIIIII①②③問(wèn)題歸約法:當(dāng)問(wèn)題復(fù)雜時(shí)，可把初始問(wèn)題分解成若干簡(jiǎn)單的子問(wèn)題，若子問(wèn)題仍復(fù)雜，可再進(jìn)一步分解，直到這些子問(wèn)題的解可直接得到。這種問(wèn)題的描述和求解方法，稱(chēng)為~.本原問(wèn)題:可直接解答的問(wèn)題稱(chēng)為~，它是不必證明的、自然成立的.歸約法的組成：1）一個(gè)初始問(wèn)題的描述；2）一組把問(wèn)題變成子問(wèn)題的算子(分解或轉(zhuǎn)換)；3）

一組本原問(wèn)題的描述不同的算子對(duì)應(yīng)不同的關(guān)系,從而使問(wèn)題歸約的描述可用一個(gè)與或圖的結(jié)構(gòu)來(lái)表示.小結(jié):

2與或圖與節(jié)點(diǎn)：把單個(gè)問(wèn)題分解為幾個(gè)子問(wèn)題來(lái)求解。只有當(dāng)所有子問(wèn)題都有解，該父輩節(jié)點(diǎn)才有解。表示一種“與”關(guān)系。或節(jié)點(diǎn)：同一問(wèn)題被轉(zhuǎn)換為幾種不同的后繼問(wèn)題。只要有一個(gè)后繼問(wèn)題有解，則原問(wèn)題有解。表示一種“或”關(guān)系。與節(jié)點(diǎn)由與運(yùn)算連接（超弧），如圖（a）.或節(jié)點(diǎn)由或運(yùn)算連接，如圖（b）.定義：與或圖就是包含與節(jié)點(diǎn)和或節(jié)點(diǎn)的圖，即存在超弧的圖，也稱(chēng)為超圖.超圖與狀態(tài)空間圖有什么區(qū)別？與或圖是一種更一般的圖.定義：一超弧所相關(guān)的邊數(shù)（K）被稱(chēng)為該超弧的度，實(shí)現(xiàn)的連接稱(chēng)為K-連接.K—連接符：從一個(gè)父節(jié)點(diǎn)指向一組含有K個(gè)后繼節(jié)點(diǎn)的節(jié)點(diǎn)集.在與或圖中，節(jié)點(diǎn)n0有兩個(gè)連接符：1-連接符指向節(jié)點(diǎn)n1；2-連接符指向節(jié)點(diǎn)集合{n4、n5}；對(duì)于節(jié)點(diǎn)n0來(lái)講，n1可稱(chēng)為或節(jié)點(diǎn)，n4、n5可稱(chēng)為與節(jié)點(diǎn)。

與或圖

3與或圖搜索含義：在與或圖上執(zhí)行搜索的過(guò)程，其目的在于標(biāo)明起始節(jié)點(diǎn)是有解的，即，搜索不是去尋找到目標(biāo)節(jié)點(diǎn)的一條路徑，而是尋找一個(gè)解圖。定義：一個(gè)節(jié)點(diǎn)被稱(chēng)為能解節(jié)點(diǎn)，其遞歸定義為：1．終節(jié)點(diǎn)是能解節(jié)點(diǎn)（直接與本原問(wèn)題相關(guān)聯(lián)）；2．若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一個(gè)能解，該非終節(jié)點(diǎn)才能解；3．若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解，該非終節(jié)點(diǎn)才能解。定義：不能解節(jié)點(diǎn)的遞歸定義為:

1．沒(méi)有后裔的非終節(jié)點(diǎn)是不能解的節(jié)點(diǎn)；2．若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí)，該非終節(jié)點(diǎn)才不能解；3．若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)至少有一子節(jié)點(diǎn)不能解時(shí)，該非終節(jié)點(diǎn)才不能解.是由能解節(jié)點(diǎn)構(gòu)成的一個(gè)子圖，是包含一節(jié)點(diǎn)（n）到目的(終)節(jié)點(diǎn)集合（N）的、連通的能解節(jié)點(diǎn)的子圖.在一個(gè)與或圖G中，從節(jié)點(diǎn)n到節(jié)點(diǎn)集N的解圖記為G，G是G的子圖.1．若n是N的一個(gè)元素，則G由單個(gè)節(jié)點(diǎn)n組成；2．若n有一個(gè)指向節(jié)點(diǎn)集{n1…,nk}的外向連接符K，使得從每一個(gè)節(jié)點(diǎn)ni到N有一個(gè)解圖(i=1,…,k)，則G由節(jié)點(diǎn)n，連接符K，以及{n1,…,nk}中的每一個(gè)節(jié)點(diǎn)到N的解圖所組成；3．否則n到N不存在解圖.如果n=s為初始節(jié)點(diǎn)，則解圖為所求解問(wèn)題的解圖.解圖的定義：若解圖的耗散值記為k(n,N)，則可遞歸計(jì)算如下：若n是N的一個(gè)元素，則k(n,N)=0；若n有一個(gè)外向連接符指向其后繼節(jié)點(diǎn)集合{n1…,ni}，并設(shè)該連接符的耗散值為Cn（一般k-連接符的耗散值=k），則

k(n,N)=Cn+k(n1,N)+…+k(ni,N)具有最小耗散值的解圖稱(chēng)為最佳解圖，其值也用h*(n)標(biāo)記。解圖耗散值的計(jì)算：例：從節(jié)點(diǎn)n開(kāi)始，正確選擇一個(gè)外向連接符，一直進(jìn)行下去直到產(chǎn)生的每一個(gè)后繼節(jié)點(diǎn)成為集合N中的一個(gè)元素為止。下圖給出了n0→{n7，n8}的三個(gè)解圖（耗散值分別為8，7，5）.解圖的求法與或圖搜索與狀態(tài)空間圖搜索的區(qū)別：搜索目的不同：是證明起始節(jié)點(diǎn)是否可解，而可解節(jié)點(diǎn)是遞歸定義的，取決于后繼節(jié)點(diǎn)是否可解，即搜索過(guò)程是能否找到可解的葉節(jié)點(diǎn).結(jié)果不同：若初始節(jié)點(diǎn)被標(biāo)示為可解，則搜索成功結(jié)束；若初始節(jié)點(diǎn)被標(biāo)示為不可解，則搜索失敗.節(jié)點(diǎn)處理不同：一旦發(fā)現(xiàn)不可解節(jié)點(diǎn)，應(yīng)把該節(jié)點(diǎn)從圖中刪去.4與或圖啟發(fā)式搜索算法AO*假設(shè)：G；G；h(n)是從節(jié)點(diǎn)n到一組終葉節(jié)點(diǎn)的一個(gè)最優(yōu)解圖的一個(gè)代價(jià)估計(jì)，評(píng)價(jià)函數(shù)q(n)=h(n)AO*過(guò)程:1.建立初始搜索圖，G:=s，計(jì)算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；2.Untils已標(biāo)記為SOLVED,do:3.Begin4.G:=FIND(G)；根據(jù)連接符標(biāo)記（指針）找出一個(gè)待擴(kuò)展的侯選局部解圖G（連接符在11步標(biāo)記）5.n:=G中的任一非終節(jié)點(diǎn);選一個(gè)當(dāng)前節(jié)點(diǎn)6.EXPAND(n),生成子節(jié)點(diǎn)集{ni}，如果ni

G，G:=ADD({ni},G),計(jì)算q(ni)=h(ni)，IFGOAL(ni)THENM(ni,SOLVED);7S:={n};建立含n的節(jié)點(diǎn)集合S.（已擴(kuò)展待修正）8UntilS為空,do:9Begin(m為S中任一節(jié)點(diǎn))10REMOVE(m,S),當(dāng)mc{S};（m→mc,從底層開(kāi)始修正）11修改m的耗散值q(m):對(duì)m指向節(jié)點(diǎn)集(n1i，n2i,…nki)的每一個(gè)連接符i分別計(jì)算qi,qi(m)=Ci+q(n1i)+…+q(nki),并取q(m):=minqi(m);

加(或修正)指針到minqi(m)的連接符上.IFM(nji,SOLVED)THENM(m,SOLVED);（j=1，2，…，k）若該連接符的所有子節(jié)點(diǎn)都是能解的,則m也能解.12IFM(m,SOLVED)(q(m)q0(m))THENADD(ma,S);m能解或修正的耗散值與原先估算q0不同,則把m的所有先輩節(jié)點(diǎn)ma添加到S中.（能解或修正向上傳遞）13end(與8匹配)14

end(與2匹配)兩個(gè)過(guò)程的重復(fù):自上而下的圖生長(zhǎng)過(guò)程（4-6步）:先通過(guò)有標(biāo)記的連接符，找到目前為止最好的一個(gè)局部解圖，然后對(duì)其中一個(gè)非終節(jié)點(diǎn)進(jìn)行擴(kuò)展，并對(duì)其后繼節(jié)點(diǎn)賦估計(jì)耗散值和加能解標(biāo)記.自下而上的估價(jià)函數(shù)值的修正、連接符的標(biāo)記和SOLVED的標(biāo)注過(guò)程(7-12):耗散值的修正從剛被擴(kuò)展的節(jié)點(diǎn)n開(kāi)始，其修正耗散值q(n)取所有估計(jì)值中最小的一個(gè)，然后根據(jù)耗散值遞歸計(jì)算公式逐級(jí)向上修正其先輩節(jié)點(diǎn)的耗散值.只有下層節(jié)點(diǎn)耗散值修正后，才可能影響到上一層節(jié)點(diǎn)的耗散值，如此一直修正到初始節(jié)點(diǎn).AO*搜索算法過(guò)程分析例:各節(jié)點(diǎn)啟發(fā)值如圖，k-連接符的耗散值=k,求最佳解圖.

應(yīng)用AO*算法，經(jīng)四個(gè)循環(huán)，可找到解圖.

在第一次循環(huán)擴(kuò)展節(jié)點(diǎn)n0；然后,依次擴(kuò)展節(jié)點(diǎn)n1、n5、n4。在節(jié)點(diǎn)n4被擴(kuò)展之后，節(jié)點(diǎn)n0便被標(biāo)注SOLVED，此時(shí)，通過(guò)向下跟蹤有標(biāo)記的連接符，便獲得了解圖.

主要步驟第4步(G’)第5步(n)第6步第7步(S)第11步第12步AO*搜索算法的過(guò)程第1循環(huán)(n0)(n0)(n1,n5,n4)(n0)比較,選n0→n1;n1不可解;無(wú)第2循環(huán)n0→n1(n1)(n2,n3)(n1)1)比較,選n1→n3;n3不可解;2)比較,改n0→n5,n4;n5,n4不可解;n0不可解,值變;1)加n0→S;2)無(wú)前輩;第3循環(huán)n0→n5,n4(n5)(n6,n7,n8)(n5)1)比較,選n5→n7,n8;n7,n8可解,n5可解;2)n0不可解,值變;1)加n0→S;2)無(wú);第4循環(huán)n0→n5,n4;(n4)(n5,n8)(n4)1)比較,選n4→n8;n8可解,n4可解;2)n4,n5可解;n0可解,值不變;1)加n0→S;2)無(wú);n0n1n4n52113446542002×5n6n3n2n7n8★★★★★不帶括號(hào)的數(shù)是啟發(fā)函數(shù)h(n)值,帶括號(hào)數(shù)是估價(jià)函數(shù)q（n）的修正值；短箭頭用來(lái)標(biāo)記連接符，標(biāo)明侯選局部解圖；已經(jīng)標(biāo)注SOLVED的節(jié)點(diǎn)用黑心圓來(lái)表示。

討論當(dāng)節(jié)點(diǎn)n無(wú)后繼節(jié)點(diǎn)?在第11步中對(duì)m(n)賦一個(gè)高的q值(會(huì)傳遞到s),從而排除了含有n的子圖被當(dāng)作候選局部解圖的可能性.在G’中存在多個(gè)非終節(jié)點(diǎn)時(shí),選擇什么樣的節(jié)點(diǎn)先擴(kuò)展?一般選擇最能導(dǎo)致該局部解圖耗散值發(fā)生較大變化的節(jié)點(diǎn)先進(jìn)行擴(kuò)展,可促使及時(shí)修改局部解圖的標(biāo)記.同A算法類(lèi)似,若s→N存在解圖,當(dāng)h(n)≤h*(n)且h(n)滿足單調(diào)限制條件時(shí)(對(duì)n到其子節(jié)點(diǎn)的每一連接符均需要滿足),則AO*一定能找到最佳解圖.與A*算法的區(qū)別評(píng)價(jià)函數(shù)只考慮h(n):

理由:算法有自下而上的修正費(fèi)用的的操作,實(shí)際上局部解圖費(fèi)用值的估計(jì)是在起始節(jié)點(diǎn)S比較,計(jì)算g既無(wú)必要也不可能.不能優(yōu)先擴(kuò)展具有最小費(fèi)用的節(jié)點(diǎn):理由:K-連接符連接的有關(guān)子節(jié)點(diǎn)對(duì)父節(jié)點(diǎn)的可解性及費(fèi)用值的估計(jì)都會(huì)產(chǎn)生影響.僅適用于無(wú)環(huán)圖,否則耗散值遞歸計(jì)算不收斂:方法:當(dāng)新生成的節(jié)點(diǎn)已在圖中時(shí),判斷是否為正被擴(kuò)展節(jié)點(diǎn)的先輩節(jié)點(diǎn).控制策略不同:沒(méi)有OPEN表和CLOSED表,只用生成的解圖結(jié)構(gòu)G,h(n)是最佳解圖的費(fèi)用估計(jì).

5博弈樹(shù)的搜索問(wèn)題:二人完備博弈：1．由二人對(duì)壘，輪流走步，自己的走步自己選擇2．信息完備:任何一方都完全知道對(duì)方過(guò)去的走步情況和今后可能的走步，不包括碰運(yùn)氣的情況表示方法:利用與或圖表示來(lái)描述博弈問(wèn)題.理由:由于在博弈中,決定自己走步時(shí)只需考慮對(duì)自己有利的一步——或，而考察對(duì)方時(shí)，則應(yīng)考慮對(duì)方所有可能的走步——與.求解方法:特殊的與或圖搜索算法——博弈樹(shù)搜索.理由:由于兩人嚴(yán)格地輪流走步，使博弈狀態(tài)圖呈現(xiàn)出嚴(yán)格的與或圖的交替層次.1)Grundy博弈

例：假設(shè)桌上放有一堆（7個(gè)）錢(qián)幣，由兩人輪流進(jìn)行分堆，要求每人每次只把其中某堆錢(qián)幣分成數(shù)目不相等的兩小堆，最后不能分下去的人被判負(fù).綜合數(shù)據(jù)庫(kù)：（x1，x2，…，xn，M）表示某個(gè)選手走步的狀態(tài).其中,x1，x2，…，xn表示n堆錢(qián)幣不同的個(gè)數(shù)，M代表選手(MIN或MAX).規(guī)則：控制策略:博弈雙方總是偏向最有利于自己的狀態(tài)前進(jìn)，己方會(huì)盡力將贏的幾率最大化,而使對(duì)手方偏離取勝目標(biāo).(5,1,1,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(3,2,2,MIN)(4,2,1,MIN)(7,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,1,1,1,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)ABC搜索策略分析（以MAX方的角度）對(duì)MAX節(jié)點(diǎn)(MIN控制)，MAX必須都能夠獲勝，即MAX必須考慮應(yīng)付MIN的所有招法，故它為與節(jié)點(diǎn).對(duì)MIN節(jié)點(diǎn)(MAX控制)，MAX只需證明有一步能走贏就可以，即MAX只要考慮有一步棋使MIN無(wú)法招架就成，故它為或節(jié)點(diǎn).因此,對(duì)弈過(guò)程的搜索圖就呈現(xiàn)出與或圖表示的形式，從圖可見(jiàn)，MAX方存在完全取勝的策略.于是,尋找MAX方取勝的策略便和求與或圖的解圖(能解→能勝)一致起來(lái)，即MAX要獲勝，在各層必須對(duì)所有與節(jié)點(diǎn)取勝，但只需對(duì)一個(gè)或節(jié)點(diǎn)取勝.2)博弈樹(shù)的極大極小搜索法思想：預(yù)先考慮雙方對(duì)弈若干步之后的局勢(shì)，從當(dāng)前侯選的走步中選一個(gè)相對(duì)好的走步來(lái)走，即在有限搜索深度范圍內(nèi)進(jìn)行求解.方法：定義一個(gè)評(píng)價(jià)函數(shù)f，以便對(duì)棋局的勢(shì)態(tài)（節(jié)點(diǎn)）作出優(yōu)劣估值.一般規(guī)定:有利于MAX(我)的勢(shì)態(tài)，f(n)取正值;有利于MIN(敵)的勢(shì)態(tài)，f(n)取負(fù)值;勢(shì)均力敵，f(n):=0.若f(n):=，表示MAX方獲勝;若f(n):=-，表示MIN方獲勝.選步的過(guò)程:假定開(kāi)始由MAX選擇走一步棋，如何選擇一步好棋？首先，對(duì)給定的格局MAX給出可能的走法，接著,MIN對(duì)MAX的每一步走法，又給出可能的走法，這樣進(jìn)行若干次（規(guī)定深度），得到一組端節(jié)點(diǎn).此時(shí),計(jì)算每個(gè)端節(jié)點(diǎn)相應(yīng)的靜態(tài)函數(shù)值;然后由底向上逐級(jí)計(jì)算倒推估值，在MIN處(與節(jié)點(diǎn))取其下層估值中最小者，在MAX處(或節(jié)點(diǎn))取其下層估值最大者。一直到MAX的開(kāi)始棋局，取其下層估值中最大的格局作為要走的第一步.當(dāng)用端節(jié)點(diǎn)的靜態(tài)估計(jì)函數(shù)值求倒推值時(shí)，針對(duì)兩位選手的控制力應(yīng)采用不同的策略，從下往上逐層交替使用極大和極小的選值方法，故稱(chēng)為極大極小過(guò)程.ＡＢＣＳＤＥＦＧＨＩＪ9-600-2-4-3-6-2-4-2MAX取極大值MIN取極小值端節(jié)點(diǎn)例.向前看兩步時(shí)f(n)的求值過(guò)程極大極小過(guò)程MIN-MAX：1.T:=(s,MAX)，OPEN:=(s)，CLOSED:=();開(kāi)始時(shí)樹(shù)由初始節(jié)點(diǎn)構(gòu)成，OPEN表只含有s.2.LOOP1:IFOPEN=()THENGOLOOP2;3.n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);將n放到CLOSED表的前面，使第5步操作時(shí)深度大的節(jié)點(diǎn)優(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計(jì)算f(ni)GOLOOP1;ni達(dá)到深度k,計(jì)算端節(jié)點(diǎn)f值.5.LOOP2：IFCLOSED=NIL,THENGOLOOP3ELSEnd=FIRST(CLOSED);6.IF(nd

MAX)(f(nciMIN)有值)THENf(nd):=max{f(nci)},REMOVE(nd，CLOSED);若MAX所有子節(jié)點(diǎn)均有值,則該MAX取其極大值.ELSEIF(nd

MIN)(f(nciMAX)有值)THENf(nd):=min{f(nci)},REMOVE(nd，CLOSED);若MIN所有子節(jié)點(diǎn)均有值，則該MIN取其極小值.7.GOLOOP2;8.LOOP3:IFf(s)≠NILTHENEXIT(ENDM(Move,T));s有值,或則結(jié)束或標(biāo)記走步.例：在九宮格棋盤(pán)上，甲乙（MAX和MIN）二人輪流在空格中放入自己的棋子（一次一枚），誰(shuí)先使自己的三子成一線就獲勝，設(shè)甲先走用（）表示，乙用（）表示，p表示某種格局，f(p)表示對(duì)格局的評(píng)價(jià)值。贏線定義:將棋盤(pán)的整行、整列或整條對(duì)角線稱(chēng)為贏線。如,一條贏線上只有（或）方的棋子或?yàn)榭眨鴽](méi)有對(duì)方的棋子，那么這條贏線就稱(chēng)為（或）方的贏線。f(p)定義：1）MAX勝，f(p)=+

2）MIN勝，f(p)=-

3）若p不是可定勝負(fù)的格局，則f(p)=fMAX(p)-fMIN(p)考慮走兩步的搜索過(guò)程,并兼顧棋盤(pán)對(duì)稱(chēng)性條件第一次調(diào)用算法產(chǎn)生的搜索樹(shù)如下圖所示，圖中端節(jié)點(diǎn)下面是計(jì)算的f(p)值，非端節(jié)點(diǎn)的倒推值標(biāo)記在圓圈內(nèi).結(jié)論:第1步的最好走法是把棋子下到中央位置.(為了使初始節(jié)點(diǎn)具有最大的倒推值)fMAX(p)=4fMIN(p)=6f(p)=4-6=-2一字棋第1階段的搜索樹(shù)√√√√√√√√√√√√√√√√

一字棋第2階段的搜索樹(shù)

√√一字棋第3階段的搜索樹(shù)

3)-搜索過(guò)程極大極小搜索缺陷:把生成樹(shù)和棋局估值兩個(gè)過(guò)程完全分離，即先生成全部的搜索樹(shù)，然后再進(jìn)行端節(jié)點(diǎn)估值和倒推值計(jì)算，這導(dǎo)致效率降低.例:一個(gè)MIN節(jié)點(diǎn)要全部生成A、B、C、D節(jié)點(diǎn)，然后逐個(gè)計(jì)算其靜態(tài)估值，最后在求倒推值階段，才賦給這個(gè)MIN節(jié)點(diǎn)的倒推值-.如何改進(jìn)?改進(jìn)思路:若兩個(gè)過(guò)程同時(shí)進(jìn)行，再依一定的條件判斷，有可能盡早剪掉一些無(wú)用的分支，那么就可能減少搜索量，這是-搜索的思想.例：生成節(jié)點(diǎn)A后，馬上進(jìn)行靜態(tài)估值，得知f（A）=-后，便可斷定再生成其余節(jié)點(diǎn)并進(jìn)行估值計(jì)算是多余的，故可馬上對(duì)MIN節(jié)點(diǎn)賦倒推值-，不會(huì)影響MAX的最好優(yōu)先走步的選擇.實(shí)現(xiàn)方法:采用有界深度優(yōu)先策略進(jìn)行搜索，這樣當(dāng)生成達(dá)到規(guī)定深度的節(jié)點(diǎn)時(shí)，就立即計(jì)算其靜態(tài)估值函數(shù)，而一旦某個(gè)非端節(jié)點(diǎn)有條件確定其倒推值時(shí)就立即計(jì)算賦值.一字棋第1階段-剪枝方法1-6→f(1)=-1→初始S,f(S)>=-1,此時(shí)該MAX層下界值=-1;7-8→f(7)<=-1,此時(shí)該MIN層上界值

=-1≥,節(jié)點(diǎn)7的其他子節(jié)點(diǎn)不必再生成，因S的極大值不可能比這個(gè)值還小，再生成是多余的，故可剪枝.在搜索過(guò)程中,通過(guò)記錄并比較倒推值的上、下界并進(jìn)行比較，就可以實(shí)現(xiàn)修剪操作，這種技術(shù)統(tǒng)稱(chēng)為-剪枝技術(shù).在實(shí)際修剪中，、的值可以隨時(shí)修正，但滿足如下條件：極大值層的倒推值下界值永不下降，實(shí)際的倒推值取其后繼節(jié)點(diǎn)最終確定的倒推值中最大的一個(gè)倒推值.極小值層的倒推值上界值永不上升，其倒推值取其后繼節(jié)點(diǎn)最終確定的倒推值中最小的一個(gè)倒推值.在一個(gè)分支上進(jìn)行-剪枝的判斷規(guī)則：剪枝：若任一極小值層節(jié)點(diǎn)的值小于或等于它任一先輩極大值層節(jié)點(diǎn)的值，即（先輩層）≥（后繼層），則可終止該MIN層中這個(gè)MIN節(jié)點(diǎn)以下的搜索，并設(shè)置這個(gè)MIN節(jié)點(diǎn)的最終的倒推值為.(位置：MIN層的剪枝)剪枝：若任一極大值層節(jié)點(diǎn)的值大于或等于它任一先輩極小值層節(jié)點(diǎn)的值，即（后繼層）≥（先輩層），則可終止該MAX層中這個(gè)MAX節(jié)點(diǎn)以下的搜索，并設(shè)置這個(gè)MAX節(jié)點(diǎn)的最終倒推值為.(位置：MAX層的剪枝)-過(guò)程：保存和值，且滿足條件時(shí)便進(jìn)行剪枝，當(dāng)初始節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)的最終倒推值都給出時(shí)，過(guò)程即結(jié)束，而最好的優(yōu)先走步就是走向具有最高倒推值的那個(gè)后繼節(jié)點(diǎn).比較是在極大值層節(jié)點(diǎn)和極小值層節(jié)點(diǎn)間進(jìn)行的(非直系).比較時(shí)是與先輩層節(jié)點(diǎn)(已經(jīng)有了值的那些節(jié)點(diǎn)),不僅限于父輩.只有一個(gè)節(jié)點(diǎn)的值固定以后,其值才能夠向其父節(jié)點(diǎn)傳遞.-剪枝搜索得到的最佳走步與極大極小方法得到的結(jié)果一致,但效率會(huì)提高.生成搜索圖和剪枝過(guò)程同時(shí)進(jìn)行.注意幾個(gè)問(wèn)題:⑴0≤0(2)(3)5(4)=0(