1、6.3 與/或樹的搜索策略,一般搜索過程 寬度優(yōu)先搜索 深度優(yōu)先搜索 有序搜索 博弈樹搜索 -剪枝技術(shù),可解節(jié)點(diǎn)與不可解節(jié)點(diǎn),在與/或樹上執(zhí)行搜索過程，目的在于表明起始節(jié)點(diǎn)有解或無解。,可解節(jié)點(diǎn)的遞歸定義為： 終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)，直接和本原問題相關(guān)連； 非終葉節(jié)點(diǎn)含有“或”子節(jié)點(diǎn)時(shí)，只要子節(jié)點(diǎn)中有一個(gè)是可解節(jié)點(diǎn)，該非終葉節(jié)點(diǎn)便為可解節(jié)點(diǎn)； 非終葉節(jié)點(diǎn)含有“與”子節(jié)點(diǎn)時(shí)，只有子節(jié)點(diǎn)全為可解節(jié)點(diǎn)時(shí)，該非終葉節(jié)點(diǎn)才是可解節(jié)點(diǎn)。,注意：終葉節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終葉節(jié)點(diǎn)。,由可解子節(jié)點(diǎn)來確定先輩節(jié)點(diǎn)是否為可解節(jié)點(diǎn)的過程稱為可解標(biāo)示過程。 由不可解子節(jié)點(diǎn)來確定先輩節(jié)點(diǎn)是否為可解節(jié)點(diǎn)的過程稱為

2、不可解標(biāo)示過程。,不可解節(jié)點(diǎn)的定義為： 關(guān)于可解節(jié)點(diǎn)的三個(gè)條件全部不滿足的節(jié)點(diǎn)，稱為不可解節(jié)點(diǎn)；,一般搜索過程流程,(1)把原始問題作為初始節(jié)點(diǎn)S，并把它作為當(dāng)前節(jié)點(diǎn)。 (2)應(yīng)用分解或等價(jià)變換算符對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展。 (3)為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。 (4)選擇合適子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第(2)、(3)步，在此期間多次調(diào)用可解標(biāo)示過程和不可解標(biāo)示過程，直到初始節(jié)點(diǎn)被標(biāo)示為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。 由這個(gè)搜索過程所形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱為搜索樹。 搜索中，通過可解標(biāo)示過程確定初始節(jié)點(diǎn)是可解的，則由此初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)就構(gòu)成了解樹。,提高與/或樹搜索效率的兩個(gè)性質(zhì),與/或

3、搜索有兩個(gè)特有性質(zhì)，可用來提高搜索效率： 如果已確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn)，其不可解的后裔節(jié)點(diǎn)不再有用，可從搜索樹中刪去； 若已確定某個(gè)節(jié)點(diǎn)是不可解節(jié)點(diǎn)，其全部后裔節(jié)點(diǎn)都不再有用，可從搜索樹中刪去。但當(dāng)前這個(gè)不可解節(jié)點(diǎn)還不能刪去，在判斷其先輩節(jié)點(diǎn)的可解性時(shí)還要用到。,寬度優(yōu)先搜索算法流程,基本思想：先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展，先進(jìn)先出。 把初始節(jié)點(diǎn)S放入OPEN表。 把OPEN表中的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSLD表。 如果n可擴(kuò)展，則做下列工作： 擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每個(gè)子節(jié)點(diǎn)配置父指針，以備標(biāo)示過程使用。 考察子節(jié)點(diǎn)中是否有終葉節(jié)點(diǎn)。若有，則標(biāo)示這些終葉節(jié)點(diǎn)為可解節(jié)

4、點(diǎn)，并應(yīng)用可解標(biāo)示過程對其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。若S也被標(biāo)示為可解節(jié)點(diǎn)，就得到了解樹，搜索成功，退出搜索過程；若無法確定S可解，則從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)。 轉(zhuǎn)步驟2。,寬度優(yōu)先搜索算法流程,4. 如果n不可擴(kuò)展，則做下列工作： 標(biāo)示n為不可解節(jié)點(diǎn)。 應(yīng)用不可解標(biāo)示過程對n的先輩節(jié)點(diǎn)中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)示。如果S被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗，原始問題無解，退出搜索過程；如果無法確定S不可解，則從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)。 轉(zhuǎn)步驟2。,寬度優(yōu)先搜索算法流程,寬度優(yōu)先搜索算法流程,例：與/或樹的寬度優(yōu)先搜索,例：設(shè)有如圖所示的與/或樹，其中t1，t2，t3，t4均

5、為終葉節(jié)點(diǎn)，A和B是不可解的端節(jié)點(diǎn)。 試采用與/或樹的寬度優(yōu)先搜索法對該圖進(jìn)行搜索。,例：與/或樹的寬度優(yōu)先搜索,Step1：擴(kuò)展1號(hào)節(jié)點(diǎn)，得到2、3號(hào)節(jié)點(diǎn)。 2、3都不是終葉節(jié)點(diǎn)，接著擴(kuò)展2。,例：與/或樹的寬度優(yōu)先搜索,Step3：擴(kuò)展2，得到4、t1。 t1是終葉節(jié)點(diǎn)，標(biāo)示為可解節(jié)點(diǎn)，應(yīng)用可解標(biāo)示過程，對其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。 t1的父節(jié)點(diǎn)是“與”節(jié)點(diǎn)，僅由t1可解不能確定2是否可解，應(yīng)繼續(xù)搜索。,例：與/或樹的寬度優(yōu)先搜索,Step3：擴(kuò)展3得到5、B，都不是終葉節(jié)點(diǎn)，接著擴(kuò)展4。 Step4：擴(kuò)展4得到A、t2。 t2是終葉節(jié)點(diǎn)，標(biāo)示4為可解節(jié)點(diǎn)。應(yīng)用可解標(biāo)示過程標(biāo)出4、2

6、均為可解節(jié)點(diǎn)。 還不能確定1為可解節(jié)點(diǎn)。此時(shí)5號(hào)節(jié)點(diǎn)是OPEN表中的第一個(gè)待考察的節(jié)點(diǎn)，所以下一步擴(kuò)展5號(hào)節(jié)點(diǎn)。,例：與/或樹的寬度優(yōu)先搜索,Step5：擴(kuò)展5得到t3、t4。 都是終葉節(jié)點(diǎn)，標(biāo)示5為可解節(jié)點(diǎn)。 應(yīng)用可解標(biāo)示過程得到5、3、1均為可解節(jié)點(diǎn)。 Step6：搜索成功，得到解樹。,深度優(yōu)先搜索的幾點(diǎn)說明,與/或樹的深度優(yōu)先搜索和寬度優(yōu)先搜索過程基本相同。只要把第(3)步的第點(diǎn)改為“擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每個(gè)子節(jié)點(diǎn)配置父指針，以備標(biāo)示過程使用”，就可使后產(chǎn)生的節(jié)點(diǎn)先被擴(kuò)展。 也可像狀態(tài)空間的有界深度優(yōu)先搜索那樣，為與/或樹的深度優(yōu)先搜索規(guī)定一個(gè)深度界限，使搜索

7、在規(guī)定范圍內(nèi)進(jìn)行。,有界深度優(yōu)先搜索算法流程,把初始節(jié)點(diǎn)S放人OPEN表。 把OPEN表中第一個(gè)節(jié)點(diǎn)n取出，放入CLOSLD表。 如果n的深度深度界限，轉(zhuǎn)第(5)步的第點(diǎn)。 如果n 可擴(kuò)展，做下列工作： 擴(kuò)展n，將子節(jié)點(diǎn)放入OPEN表首部，配置父指針，在 標(biāo)示過程使用。 若子節(jié)點(diǎn)中有終葉節(jié)點(diǎn)，標(biāo)示其為可解節(jié)點(diǎn)，對其先輩 節(jié)點(diǎn)應(yīng)用可解標(biāo)示過程進(jìn)行標(biāo)示。若S被標(biāo)示為可解， 得到解樹，成功退出搜索；若無法確定S為可解節(jié)點(diǎn)， 從OPEN表中刪去有可解先輩的節(jié)點(diǎn)。 轉(zhuǎn)第(2)步。,有界深度優(yōu)先搜索算法流程,如果n不可擴(kuò)展，則做下列工作： 標(biāo)示n為不可解節(jié)點(diǎn)。 應(yīng)用不可解標(biāo)示過程對n的先輩節(jié)點(diǎn)中不可解節(jié)點(diǎn)

8、進(jìn)行標(biāo)示。如果S被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗退出；如果不能確定S為不可解節(jié)點(diǎn)，則從OPEN表中刪去有不可解先輩的節(jié)點(diǎn)。 轉(zhuǎn)第(2)步。,例：與/或樹的深度優(yōu)先搜索,對與/或樹進(jìn)行有界深度優(yōu)先搜索，并規(guī)定深度界限為4，則擴(kuò)展節(jié)點(diǎn)的順序是：1，3，B，5，2，4 解樹與寬度優(yōu)先搜索相同。,與/或樹的深度、寬度優(yōu)先搜索特點(diǎn),都是盲目搜索。 搜索從初始節(jié)點(diǎn)開始，先自上而下進(jìn)行搜索，尋找終葉節(jié)點(diǎn)及端點(diǎn)節(jié)，然后再自下而上進(jìn)行標(biāo)示。一旦初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)，搜索就不再繼續(xù)進(jìn)行。 搜索都按確定路線進(jìn)行，當(dāng)選擇某個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)，只考慮節(jié)點(diǎn)在與/或樹中的位置，沒有考慮要付出的代價(jià)，因而求得的解樹不

9、一定是代價(jià)最小的解樹，即不一定是最優(yōu)解樹。,有序搜索的基本思想,與/或樹的有序搜索是求代價(jià)最小的解樹的搜索方法。 為求得代價(jià)最小的解樹，每次確定待擴(kuò)展節(jié)點(diǎn)時(shí)，需要往前多看幾步，計(jì)算擴(kuò)展這個(gè)節(jié)點(diǎn)可能要付出的代價(jià)，并選擇代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 像這樣根據(jù)代價(jià)決定搜索路線的方法稱為與/或樹的有序搜索，它是一種啟發(fā)式搜索策略。,解樹的代價(jià)計(jì)算方法,通過計(jì)算解樹中節(jié)點(diǎn)的代價(jià)得到。若問題可解，由子節(jié)點(diǎn)代價(jià)推算父節(jié)點(diǎn)代價(jià)，逐層上推，最終求出S的代價(jià)，即解樹的代價(jià)。,設(shè)c(x, y)表示節(jié)點(diǎn)x到其子節(jié)點(diǎn)y的代價(jià)，則x的代價(jià)計(jì)算方法如下： 如果x是終葉節(jié)點(diǎn)，則定義x的代價(jià)： h(x)=0 如果x不可擴(kuò)展，且不

10、是終葉節(jié)點(diǎn)，則定義：h(x)= 如果x是“或”節(jié)點(diǎn)，y1， y2， ， yn是它的子節(jié)點(diǎn)，則x的代價(jià)為： 如果x是“與”節(jié)點(diǎn)則x的代價(jià)有兩種計(jì)算方法： 和代價(jià)法 最大代價(jià)法,例：與/或樹的有序搜索,例：設(shè)有如圖所示與/或樹，包括兩棵解樹，一棵由S, A, t1, t2組成，另一棵由S, B, D, G, t4, t5組成。在與/或樹中，邊上的數(shù)字是該邊的代價(jià)，t1, t2 , t3, t4, t5為終葉節(jié)點(diǎn)，代價(jià)為0，E, F是端節(jié)點(diǎn)，代價(jià)為。 試計(jì)算解樹代價(jià)。,代價(jià)計(jì)算中存在的問題,計(jì)算h(x)的條件：已知x所有子節(jié)點(diǎn)的代價(jià)。 問題：搜索是自上而下進(jìn)行的，只有不可擴(kuò)展節(jié)點(diǎn)的代價(jià)是已知的（或0

11、），因此除非x的所有子節(jié)點(diǎn)都不可擴(kuò)展，否則x的代價(jià)無法計(jì)算得到。 解決方案：根據(jù)問題本身提供的啟發(fā)性信息定義一個(gè)啟發(fā)函數(shù)，由啟發(fā)函數(shù)估算子節(jié)點(diǎn)的代價(jià)，然后反推計(jì)算父節(jié)點(diǎn)和先輩節(jié)點(diǎn)的代價(jià)。每當(dāng)有新一代的節(jié)點(diǎn)生成時(shí)，都要自下而上地重新計(jì)算先輩節(jié)點(diǎn)的代價(jià)。,希望樹,希望樹的定義,選擇待擴(kuò)展節(jié)點(diǎn)時(shí)，挑選有希望成為最優(yōu)解樹一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展，保證任一時(shí)刻求出的部分解樹的代價(jià)都是最小的。 由這些節(jié)點(diǎn)及先輩節(jié)點(diǎn)（包括初始節(jié)點(diǎn)S）構(gòu)成的與/或樹有可能成為最優(yōu)解樹一部分，被稱為希望樹。 注意： 搜索過程中，隨著新節(jié)點(diǎn)的不斷生成，節(jié)點(diǎn)的代價(jià)值不斷變化。因此，希望樹也是在不斷變化的。 有序搜索是一個(gè)不斷選擇、不斷

12、修正希望樹的過程。,希望樹的構(gòu)成,初始節(jié)點(diǎn)S在希望樹中； 如果節(jié)點(diǎn)x在希望樹中，則一定有： 如果x是“或”節(jié)點(diǎn)，y1， y2， ， yn是它的子節(jié)點(diǎn)，則具有 值的那個(gè)子節(jié)點(diǎn)yi也應(yīng)在希望樹中。 如果x是“與”節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在希望樹中。,有序搜索算法流程,(1)把初始節(jié)點(diǎn)S放入OPEN表中。 (2)根據(jù)當(dāng)前搜索樹中節(jié)點(diǎn)的代價(jià)求出以S為根的希望樹T 。 (3)依次把OPEN表中T的端節(jié)點(diǎn)N選出放入CLOSED表中。 (4)如果N是終葉節(jié)點(diǎn)，則做下列工作： 標(biāo)示N為可解節(jié)點(diǎn)。 對T應(yīng)用可解標(biāo)示過程，標(biāo)記N的先輩節(jié)點(diǎn)。 若S被標(biāo)記為可解，則T就是最優(yōu)解樹，成功退出。 否則，從OPLN表中刪

13、去具有可解先輩的節(jié)點(diǎn)。,(5)如果N不是終葉節(jié)點(diǎn)，且不可擴(kuò)展，則做下列工作： 標(biāo)示N為不可解節(jié)點(diǎn)。 對T應(yīng)用不可解標(biāo)示過程，標(biāo)記N的先輩節(jié)點(diǎn)。 若初始節(jié)點(diǎn)S被標(biāo)示為不可解節(jié)點(diǎn)，則失敗退出。 否則，從OPEN表中刪去有不可解先輩的節(jié)點(diǎn)。 (6)如果N不是終葉節(jié)點(diǎn)，但可擴(kuò)展，則做下列工作： 擴(kuò)展N，產(chǎn)生N的所有子節(jié)點(diǎn)。 把子節(jié)點(diǎn)放入OPEN表，并為每個(gè)子節(jié)點(diǎn)配置父指針。 計(jì)算子節(jié)點(diǎn)的h值及其先輩節(jié)點(diǎn)的h值。 (7)轉(zhuǎn)第(2)步。,3.2.4 與/或樹的有序搜索,例：與/或樹的有序搜索,例： 設(shè)與/或樹初始節(jié)點(diǎn)為S0，每次擴(kuò)展兩層，一層是“與”節(jié)點(diǎn)，一層是“或”節(jié)點(diǎn)。希望樹生成時(shí)，采用和代價(jià)法，c(

14、x, yi)=1。S0擴(kuò)展后得到如圖所示與/或樹，B，C，E，F(xiàn)用啟發(fā)函數(shù)估算出的h值分別是：h(B)=3，h(C)=3，h(E)=3，h(F)=2,Step1： h(A)=c(A, B)+h(B)+c(A, C)+h(C) =(1+3)+(1+3)=8 hA(S0)=8+1=9 h(D)=7，hD(S0)=8,S0的右子樹是希望樹,對希望樹的端節(jié)點(diǎn)E擴(kuò)展兩層后得到的與/或樹,例：與/或樹的有序搜索,Step2： h(G)=7h(H)=6 h(E)=7h(D)=11 hD(S0)=12,S0的左子樹是希望樹,左子樹代價(jià)：hA(S0)=9,例：與/或樹的有序搜索,Step3： h(L)=2，h(

15、M)=6，h(B)=3，h(A)=8，hA(S0)=9,終葉節(jié)點(diǎn),L和B都是可解節(jié)點(diǎn) C無法判斷是否可解節(jié)點(diǎn) A和S0也無法判斷,例：與/或樹的有序搜索,Step4：擴(kuò)展C h(N)=2，h(P)=7，h(C)=3，h(A)=8，hA(S0)=9,N、C、B可解 A可解 S0可解,最優(yōu)解樹,什么是博弈？,博弈一直是啟發(fā)式搜索的一個(gè)重要應(yīng)用領(lǐng)域，早在20世紀(jì)60年代就已經(jīng)出現(xiàn)若干博弈系統(tǒng)，美國IBM公司的“深藍(lán)”系統(tǒng)已達(dá)到了國際特級(jí)大師級(jí)的水平。 “二人零和、全信息、非偶然”是最簡單的博弈： 對壘的A、B雙方輪流采取行動(dòng)，結(jié)果只有三種情況：A勝B敗， A敗B勝，雙方和局； 對壘過程中，任何一方都

16、了解當(dāng)前及過去歷史； 任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前實(shí)際情況，進(jìn)行得失分析，選取對自己最有利而對對方最不利的對策。,博弈樹的形成,博弈過程中，設(shè)我方為A方，則可供A方選擇的若干行動(dòng)方案之間是“或”關(guān)系； 在A方行動(dòng)方案基礎(chǔ)上，B方也有若干個(gè)可供選擇的行動(dòng)方案，則這些方案對A方來說就是“與”關(guān)系。 如此，逐層擴(kuò)展，并用圖表示博弈過程，得到的就是一棵與/或樹，描述博弈過程的與/或樹被稱為博弈樹。,博弈樹搜索的特點(diǎn),博弈的初始格局是初始節(jié)點(diǎn)。 博弈樹中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。雙方輪流擴(kuò)展節(jié)點(diǎn)。 所有能使自己一方獲

17、勝的終局都是本原問題，相應(yīng)節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。 問題：如何從眾多可供選擇的行動(dòng)方案中選出一個(gè)對自己有利的行動(dòng)方案。,最常用的分析方法是極大極小分析法,極大極小分析法的基本思想,根據(jù)問題特性定義一個(gè)估價(jià)函數(shù)?？紤]每一方案實(shí)施后，對方可能采取的所有行動(dòng)，利用估價(jià)函數(shù)估算當(dāng)前博弈樹端節(jié)點(diǎn)得分（靜態(tài)估值）。 利用端節(jié)點(diǎn)的估值推算其父節(jié)點(diǎn)得分（倒推值）。 對“或”節(jié)點(diǎn)，為了選一個(gè)對自己最有利的方案，選其子節(jié)點(diǎn)中的最大得分作為父節(jié)點(diǎn)得分； 對“與”節(jié)點(diǎn)，立足于最壞情況，選其子節(jié)點(diǎn)中的最小得分作為父節(jié)點(diǎn)得分。 具有較大倒推值的行動(dòng)方案就是當(dāng)前最好的行動(dòng)方案。,倒推值的計(jì)算,注

18、意：由于完整的博弈樹過于龐大，在博弈問題中，可行的方法是只生成一定深度的博弈樹。,例：博弈樹搜索一字棋游戲,例：設(shè)有如圖所示九個(gè)空格，A、B二人對奕，輪到誰走誰就往空格上放一只自己的棋子，最先使自己棋子構(gòu)成三子一線的就獲得勝利。 設(shè)A的棋子用“a”表示，B的棋子用“b”表示，A先走棋。 為了不生成太大的博弈樹，假設(shè)每次僅擴(kuò)展兩層。,對A方，設(shè)棋局為P，估價(jià)函數(shù)e(P)定義為 ： 若P是A必勝的棋局，則e(P)=+ 若P是B必勝的棋局，則e(P)=- 若P是勝負(fù)未定的棋局，則e(P)=e(+P)-e(-P) e(+P)：P上可能使a三子成一線的數(shù)目。 e(-P)：P上可能使b三子成一線的數(shù)目。,e(P) =3-1=2,例：博弈樹搜索一字棋游戲,A的最佳