與或樹的搜索策略搜索的完備性與效率

6.3與/或樹的搜索策略一般搜索過程寬度優(yōu)先搜索深度優(yōu)先搜索有序搜索博弈樹搜索-剪枝技術可解節(jié)點與不可解節(jié)點在與/或樹上執(zhí)行搜索過程，目的在于表明起始節(jié)點有解或無解?？山夤?jié)點的遞歸定義為：終葉節(jié)點是可解節(jié)點，直接和本原問題相關連；非終葉節(jié)點含有“或”子節(jié)點時，只要子節(jié)點中有一個是可解節(jié)點，該非終葉節(jié)點便為可解節(jié)點；非終葉節(jié)點含有“與”子節(jié)點時，只有子節(jié)點全為可解節(jié)點時，該非終葉節(jié)點才是可解節(jié)點。注意：終葉節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終葉節(jié)點。由可解子節(jié)點來確定先輩節(jié)點是否為可解節(jié)點的過程稱為可解標示過程。由不可解子節(jié)點來確定先輩節(jié)點是否為可解節(jié)點的過程稱為不可解標示過程。不可解節(jié)點的定義為：關于可解節(jié)點的三個條件全部不滿足的節(jié)點，稱為不可解節(jié)點；一般搜索過程流程(1)把原始問題作為初始節(jié)點S，并把它作為當前節(jié)點。(2)應用分解或等價變換算符對當前節(jié)點進行擴展。(3)為每個子節(jié)點設置指向父節(jié)點的指針。(4)選擇合適子節(jié)點作為當前節(jié)點，反復執(zhí)行第(2)、(3)步，在此期間多次調(diào)用可解標示過程和不可解標示過程，直到初始節(jié)點被標示為可解節(jié)點或不可解節(jié)點為止。由這個搜索過程所形成的節(jié)點和指針結構稱為搜索樹。搜索中，通過可解標示過程確定初始節(jié)點是可解的，則由此初始節(jié)點及其下屬的可解節(jié)點就構成了解樹。提高與/或樹搜索效率的兩個性質(zhì)與/或搜索有兩個特有性質(zhì)，可用來提高搜索效率：如果已確定某個節(jié)點為可解節(jié)點，其不可解的后裔節(jié)點不再有用，可從搜索樹中刪去；若已確定某個節(jié)點是不可解節(jié)點，其全部后裔節(jié)點都不再有用，可從搜索樹中刪去。但當前這個不可解節(jié)點還不能刪去，在判斷其先輩節(jié)點的可解性時還要用到。寬度優(yōu)先搜索算法流程基本思想：先產(chǎn)生的節(jié)點先擴展，先進先出。把初始節(jié)點S放入OPEN表。把OPEN表中的第一個節(jié)點(記為節(jié)點n)取出放入CLOSLD表。如果n可擴展，則做下列工作：①擴展n，將其子節(jié)點放入OPEN表的尾部，并為每個子節(jié)點配置父指針，以備標示過程使用。

②考察子節(jié)點中是否有終葉節(jié)點。若有，則標示這些終葉節(jié)點為可解節(jié)點，并應用可解標示過程對其先輩節(jié)點中的可解節(jié)點進行標示。若S也被標示為可解節(jié)點，就得到了解樹，搜索成功，退出搜索過程；若無法確定S可解，則從OPEN表中刪去具有可解先輩的節(jié)點。③轉步驟2。寬度優(yōu)先搜索算法流程4.如果n不可擴展，則做下列工作：①標示n為不可解節(jié)點。

②應用不可解標示過程對n的先輩節(jié)點中不可解的節(jié)點進行標示。如果S被標示為不可解節(jié)點，則搜索失敗，原始問題無解，退出搜索過程；如果無法確定S不可解，則從OPEN表中刪去具有不可解先輩的節(jié)點。③轉步驟2。寬度優(yōu)先搜索算法流程寬度優(yōu)先搜索算法流程例：與/或樹的寬度優(yōu)先搜索例：設有如圖所示的與/或樹，其中t1，t2，t3，t4均為終葉節(jié)點，A和B是不可解的端節(jié)點。試采用與/或樹的寬度優(yōu)先搜索法對該圖進行搜索。例：與/或樹的寬度優(yōu)先搜索Step1：擴展1號節(jié)點，得到2、3號節(jié)點。

2、3都不是終葉節(jié)點，接著擴展2。OPENCLOSED12,3132,1例：與/或樹的寬寬度優(yōu)先先搜索Step3：擴展2，得到4、t1。t1是終葉節(jié)節(jié)點，標標示為可可解節(jié)點點，應用用可解標標示過程程，對其其先輩節(jié)節(jié)點中的的可解節(jié)節(jié)點進行行標示。。t1的父節(jié)點點是“與與”節(jié)點點，僅由由t1可解不能能確定2是否可解解，應繼繼續(xù)搜索索。OPENCLOSED…………3,42,1t1,2,1…………例：與/或樹的寬寬度優(yōu)先先搜索Step3：擴展3得到5、B，都不是是終葉節(jié)節(jié)點，接接著擴展展4。Step4：擴展4得到A、t2。t2是終葉節(jié)節(jié)點，標標示4為可解節(jié)節(jié)點。應應用可解解標示過過程標出出4、2均為可解解節(jié)點。。還不能確確定1為可解節(jié)節(jié)點。此此時5號節(jié)點是是OPEN表中的第第一個待待考察的的節(jié)點，，所以下下一步擴擴展5號節(jié)點。。OPENCLOSED…………43,t1,2,15t2,4,3,t1,2,1…………例：與/或樹的寬寬度優(yōu)先先搜索Step5：擴展5得到t3、t4。都是終葉葉節(jié)點，，標示5為可解節(jié)節(jié)點。應用可解解標示過過程得到到5、3、1均為可解解節(jié)點。。Step6：搜索成功功，得到到解樹。。OPENCLOSED…………5,t2,4,3,t1,2,1…………深度優(yōu)先先搜索的的幾點說說明與/或樹的深度度優(yōu)先搜搜索和寬寬度優(yōu)先先搜索過過程基本本相同。。只要把把第(3)步的第①點改為““擴展節(jié)節(jié)點n，將其子子節(jié)點放放入OPEN表的首部部，并為為每個子子節(jié)點配配置父指指針，以以備標示示過程使使用”，就可使使后產(chǎn)生生的節(jié)點點先被擴擴展。也可像狀狀態(tài)空間間的有界界深度優(yōu)優(yōu)先搜索索那樣，，為與/或樹的深深度優(yōu)先先搜索規(guī)規(guī)定一個個深度界限限，使搜索索在規(guī)定定范圍內(nèi)內(nèi)進行。。有界深度度優(yōu)先搜搜索算法法流程把初始節(jié)節(jié)點S放人OPEN表。把OPEN表中第一一個節(jié)點點n取出，放放入CLOSLD表。如果n的深度深度界限限，轉第第(5)步的第①①點。如果n可擴展，，做下列列工作：：①擴展n，將子節(jié)節(jié)點放入入OPEN表首部，配置父父指針，，在標示過程程使用。。②若子節(jié)點點中有終終葉節(jié)點點，標示示其為可可解節(jié)點點，對其其先輩節(jié)點應用用可解標標示過程程進行標標示。若若S被標示為為可解，，得到解樹樹，成功功退出搜搜索；若若無法確確定S為可解節(jié)節(jié)點，從OPEN表中刪去去有可解解先輩的的節(jié)點。。③轉第(2)步。有界深度度優(yōu)先搜搜索算法法流程如果n不可擴展展，則做做下列工工作：①標示n為不可解解節(jié)點。。②應用不可可解標示示過程對對n的先輩節(jié)節(jié)點中不不可解節(jié)節(jié)點進行行標示。。如果S被標示為為不可解解節(jié)點，，則搜索索失敗退退出；如如果不能能確定S為不可解解節(jié)點，，則從OPEN表中刪去去有不可可解先輩輩的節(jié)點點。③轉第(2)步。例：與/或樹的深深度優(yōu)先先搜索對與/或樹進行行有界深深度優(yōu)先先搜索，，并規(guī)定定深度界界限為4，則擴展展節(jié)點的的順序是是：1，3，B，5，2，4解樹與寬度優(yōu)優(yōu)先搜索相同同。與/或樹的深度、、寬度優(yōu)先搜搜索特點都是盲目搜索。搜索從初始節(jié)節(jié)點開始，先先自上而下進進行搜索，尋尋找終葉節(jié)點點及端點節(jié)，，然后再自下下而上進行標標示。一旦初初始節(jié)點被標標示為可解或或不可解節(jié)點點，搜索就不不再繼續(xù)進行行。搜索都按確定定路線進行，，當選擇某個個節(jié)點進行擴擴展時，只考考慮節(jié)點在與與/或樹中的位置置，沒有考慮慮要付出的代代價，因而求求得的解樹不不一定是代價價最小的解樹樹，即不一定定是最優(yōu)解樹樹。有序搜索的基基本思想與/或樹的有序搜搜索是求代價最小的的解樹的搜索方法。。為求得代價最最小的解樹，，每次確定待待擴展節(jié)點時時，需要往前前多看幾步，，計算擴展這個個節(jié)點可能要要付出的代價價，并選擇代代價最小的節(jié)節(jié)點進行擴展展。像這樣根據(jù)代代價決定搜索索路線的方法法稱為與/或樹的有序搜搜索，它是一一種啟發(fā)式搜索策略。解樹的代價計計算方法通過計算解樹樹中節(jié)點的代代價得到。若若問題可解，，由子節(jié)點代代價推算父節(jié)節(jié)點代價，逐逐層上推，最最終求出S的代價，即解解樹的代價。。設c(x,y)表示節(jié)點x到其子節(jié)點y的代價，則x的代價計算方方法如下：如果x是終葉節(jié)點，，則定義x的代價：h(x)=0如果x不可擴展，且且不是終葉節(jié)節(jié)點，則定義義：h(x)=如果x是“或”節(jié)點點，y1，y2，…，yn是它的子節(jié)點點，則x的代價為：如果x是“與”節(jié)點點．則x的代價有兩種種計算方法：：※和代價法※最大代價法例：與/或樹的有序搜搜索例：設有如圖圖所示與/或樹，包括兩兩棵解樹，一一棵由S,A,t1,t2組成，另一棵棵由S,B,D,G,t4,t5組成。在與/或樹中，邊上上的數(shù)字是該該邊的代價，，t1,t2,t3,t4,t5為終葉節(jié)點，，代價為0，E,F是端節(jié)點，代代價為。試計算解樹代代價。和代價最大代價左邊解樹h(A)=11h(S)=13h(A)=6h(S)=8右邊解樹h(G)=3h(D)=4h(B)=6h(S)=8h(G)=2h(D)=3h(B)=5h(S)=7代價計算中存存在的問題計算h(x)的條件：已知x所有子節(jié)點的的代價。問題：搜索是自上而而下進行的，，只有不可擴擴展節(jié)點的代代價是已知的的（或0），因此除非非x的所有子節(jié)點點都不可擴展展，否則x的代價無法計計算得到。解決方案：根據(jù)問題本身身提供的啟發(fā)發(fā)性信息定義義一個啟發(fā)函數(shù)，由啟發(fā)函數(shù)數(shù)估算子節(jié)點點的代價，然然后反推計算算父節(jié)點和先先輩節(jié)點的代代價。每當有有新一代的節(jié)節(jié)點生成時，，都要自下而而上地重新計計算先輩節(jié)點點的代價。希望樹希望樹的定義義選擇待擴展節(jié)節(jié)點時，挑選選有希望成為為最優(yōu)解樹一一部分的節(jié)點點進行擴展，，保證任一時時刻求出的部部分解樹的代代價都是最小小的。由這些節(jié)點及及先輩節(jié)點（（包括初始節(jié)節(jié)點S）構成的與/或樹有可能成成為最優(yōu)解樹樹一部分，被被稱為希望樹樹。注意：搜索過程中，，隨著新節(jié)點點的不斷生成成，節(jié)點的代代價值不斷變變化。因此，，希望樹也是在不斷變化的。有序搜索是一一個不斷選擇擇、不斷修正正希望樹的過過程。希望樹的構成成初始節(jié)點S在希望樹中；；如果節(jié)點x在希望樹中，，則一定有：：如果x是“或”節(jié)點點，y1，y2，…，yn是它的子節(jié)點點，則具有值的那個子節(jié)節(jié)點yi也應在在希望望樹中中。如果x是“與與”節(jié)節(jié)點，，則它它的全全部子子節(jié)點點都應應在希希望樹樹中。。有序搜搜索算算法流流程(1)把初始始節(jié)點點S放入OPEN表中。。(2)根據(jù)當當前搜搜索樹樹中節(jié)節(jié)點的的代價價求出出以S為根的的希望望樹T。(3)依次把把OPEN表中T的端節(jié)節(jié)點N選出放放入CLOSED表中。。(4)如果N是終葉葉節(jié)點點，則則做下下列工工作：：①標示示N為可解解節(jié)點點。②對T應用可可解標標示過過程，，標記記N的先輩輩節(jié)點點。③若S被標記記為可可解，，則T就是最最優(yōu)解解樹，，成功功退出出。④否則則，從從OPLN表中刪刪去具具有可可解先先輩的的節(jié)點點。(5)如果N不是終終葉節(jié)節(jié)點，，且不不可擴擴展，，則做做下列列工作作：①標示示N為不可可解節(jié)節(jié)點。。②對T應用不不可解解標示示過程程，標標記N的先輩輩節(jié)點點。③若初初始節(jié)節(jié)點S被標示示為不不可解解節(jié)點點，則則失敗敗退出出。④否則則，從從OPEN表中刪刪去有有不可可解先先輩的的節(jié)點點。(6)如果N不是終終葉節(jié)節(jié)點，，但可可擴展展，則則做下下列工工作：：①擴展展N，產(chǎn)生生N的所有有子節(jié)節(jié)點。。②把子節(jié)節(jié)點放放入OPEN表，并并為每每個子子節(jié)點點配置置父指指針。。③計算子子節(jié)點點的h值及其其先輩輩節(jié)點點的h值。(7)轉第(2)步。與/或樹的的有序序搜索索例：與與/或樹的的有序序搜索索例：設設與與/或樹初初始節(jié)節(jié)點為為S0，每次次擴展展兩層層，一一層是是“與與”節(jié)節(jié)點，，一層層是““或””節(jié)點點。希希望樹樹生成成時，，采用用和代代價法法，c(x,yi)=1。S0擴展后后得到到如圖圖所示示與/或樹，，B，C，E，F(xiàn)用啟發(fā)發(fā)函數(shù)數(shù)估算算出的的h值分別別是：：h(B)=3，h(C)=3，h(E)=3，h(F)=2Step1：h(A)=c(A,B)+h(B)+c(A,C)+h(C)=(1+3)+(1+3)=8hA(S0)=8+1=9h(D)=7，hD(S0)=8S0的右子子樹是是希望望樹對希望望樹的的端節(jié)節(jié)點E擴展兩兩層后后得到到的與與/或樹例：與與/或樹的的有序序搜索索Step2：h(G)=7h(H)=6h(E)=7h(D)=11hD(S0)=12S0的左子子樹是是希望望樹左子子樹樹代代價價：：hA(S0)=9例：：與與/或樹樹的的有有序序搜搜索索Step3：h(L)=2，h(M)=6，h(B)=3，h(A)=8，hA(S0)=9終葉葉節(jié)節(jié)點點L和B都是是可可解解節(jié)節(jié)點點C無法法判判斷斷是是否否可可解解節(jié)節(jié)點點A和S0也無無法法判判斷斷例：：與與/或樹樹的的有有序序搜搜索索Step4：擴展展Ch(N)=2，h(P)=7，h(C)=3，h(A)=8，hA(S0)=9終葉節(jié)點N、C、B可解解A可解解S0可解解最優(yōu)優(yōu)解解樹樹什么么是是博博弈弈？？博弈弈一一直直是是啟啟發(fā)發(fā)式式搜搜索索的的一一個個重重要要應應用用領領域域，，早早在在20世紀紀60年代代就就已已經(jīng)經(jīng)出出現(xiàn)現(xiàn)若若干干博博弈弈系系統(tǒng)統(tǒng)，，美美國國IBM公司司的的““深深藍藍””系系統(tǒng)統(tǒng)已已達達到到了了國國際際特特級級大大師師級級的的水水平平。?！岸巳肆懔愫秃?、、全全信信息息、、非非偶偶然然””是最最簡簡單單的的博博弈弈：：對壘壘的的A、B雙方方輪輪流流采采取取行行動動，，結結果果只只有有三三種種情情況況：：A勝B敗，，A敗B勝，，雙雙方方和和局局；；對壘壘過過程程中中，，任任何何一一方方都都了了解解當當前前及及過過去去歷歷史史；；任何何一一方方在在采采取取行行動動前前都都要要根根據(jù)據(jù)當當前前實實際際情情況況，，進進行行得得失失分分析析，，選選取取對對自自己己最最有有利利而而對對對對方方最最不不利利的的對對策策。。博弈弈樹樹的的形形成成博弈弈過過程程中中，，設設我我方方為為A方，，則則可可供供A方選選擇擇的的若若干干行行動動方方案案之之間間是是““或或””關關系系；；在A方行行動動方方案案基基礎礎上上，，B方也也有有若若干干個個可可供供選選擇擇的的行行動動方方案案，，則則這這些些方方案案對對A方來來說說就就是是““與與””關關系系。。如此此，，逐逐層層擴擴展展，，并并用用圖圖表表示示博博弈弈過過程程，，得得到到的的就就是是一一棵棵與與/或樹樹，，描描述述博博弈弈過過程程的的與與/或樹樹被被稱稱為為博博弈弈樹樹。。博弈弈樹樹搜搜索索的的特特點點博弈弈的的初初始始格格局局是是初初始始節(jié)節(jié)點點。。博弈弈樹樹中中，，“或或””節(jié)節(jié)點點和和““與與””節(jié)節(jié)點點是是逐逐層層交交替替出出現(xiàn)現(xiàn)的的。自自己己一一方方擴擴展展的的節(jié)節(jié)點點之之間間是是““或或””關關系系，，對對方方擴擴展展的的節(jié)節(jié)點點之之間間是是““與與””關關系系。。雙雙方方輪輪流流擴擴展展節(jié)節(jié)點點。。所有能使使自己一一方獲勝勝的終局局都是本本原問題題，相應應節(jié)點是是可解節(jié)節(jié)點；所所有使對對方獲勝勝的終局局都是不不可解節(jié)節(jié)點。問題：如何從眾眾多可供供選擇的的行動方方案中選選出一個個對自己己有利的的行動方方案。最常用的的分析方方法是極大極小小分析法法極大極小小分析法法的基本本思想根據(jù)問題題特性定定義一個個估價函函數(shù)。考考慮每一一方案實實施后，，對方可可能采取取的所有有行動，，利用估估價函數(shù)數(shù)估算當當前博弈弈樹端節(jié)節(jié)點得分分（靜態(tài)估值值）。利用端節(jié)節(jié)點的估估值推算算其父節(jié)節(jié)點得分分（倒推值）。對“或””節(jié)點，，為了選選一個對對自己最最有利的的方案，，選其子子節(jié)點中中的最大大得分作作為父節(jié)節(jié)點得分分；對“與””節(jié)點，，立足于于最壞情情況，選選其子節(jié)節(jié)點中的的最小得得分作為為父節(jié)點點得分。。具有較大大倒推值值的行動動方案就就是當前前最好的的行動方方案。倒推值的的計算注意：由于完整整的博弈弈樹過于于龐大，，在博弈弈問題中中，可行行的方法法是只生生成一定定深度的的博弈樹樹。例：博弈弈樹搜索索——一字棋游游戲例：設有有如圖所所示九個個空格，，A、B二人對奕奕，輪到到誰走誰誰就往空空格上放放一只自自己的棋棋子，最最先使自自己棋子子構成三三子一線線的就獲獲得勝利利。設A的棋子用用“a”表示，B的棋子用用“b”表示，A先走棋。。為了不生生成太大大的博弈弈樹，假假設每次次僅擴展展兩層。。一字棋對A方，設棋棋局為P，估價函函數(shù)e(P)定義為：：若P是A必勝的棋棋局，則則e(P)=+若P是B必勝的棋棋局，則則e(P)=-若P是勝負未未定的棋棋局，則則e(P)=e(+P)-e(-P)e(+P)：P上可能使使a三子成一一線的數(shù)數(shù)目。e(-P)：P上可能使使b三子成一一線的數(shù)數(shù)目。bae(P)=3-1=2例：博弈弈樹搜索索——一字棋游游戲e(P)=e(+P)-e(-P)=2-1=1A的最佳走走步A走S3后，B的最優(yōu)選選擇是S4，因為它它的靜態(tài)態(tài)估值較較小，對對A不利。極大極小小法的缺缺點首先，生生成一定定深度的的博弈樹樹。然后后，對端端節(jié)點進進行估值值，再計計算上層層節(jié)點的的倒推值值，效率率較低。。分析可知知：博弈弈樹具有有“與””、“或或”節(jié)點點逐層交交替出現(xiàn)現(xiàn)的特點點，如能能邊生成成節(jié)點邊邊計算估估值及倒倒推值，，就有可可能刪去去一些不不必要的的節(jié)點，，從而減減少搜索索及計算算的工作作量。-剪枝技術術什么是-剪枝技術？？邊