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

6.3與/或樹的搜索策略一般搜索過程寬度優(yōu)先搜索深度優(yōu)先搜索有序搜索博弈樹搜索-剪枝技術(shù)6.3與/或樹的搜索策略一般搜索過程可解節(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)時，只要子節(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)才是可解節(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)的過程稱為不可解標(biāo)示過程。不可解節(jié)點(diǎn)的定義為：關(guān)于可解節(jié)點(diǎn)的三個條件全部不滿足的節(jié)點(diǎn)，稱為不可解節(jié)點(diǎn)；可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)在與/或樹上執(zhí)行搜索過程，目的在于表明起一般搜索過程流程(1)把原始問題作為初始節(jié)點(diǎn)S，并把它作為當(dāng)前節(jié)點(diǎn)。(2)應(yīng)用分解或等價(jià)變換算符對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展。(3)為每個子節(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)為止。由這個搜索過程所形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱為搜索樹。搜索中，通過可解標(biāo)示過程確定初始節(jié)點(diǎn)是可解的，則由此初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)就構(gòu)成了解樹。一般搜索過程流程(1)把原始問題作為初始節(jié)點(diǎn)S，并把它作為當(dāng)提高與/或樹搜索效率的兩個性質(zhì)與/或搜索有兩個特有性質(zhì)，可用來提高搜索效率：如果已確定某個節(jié)點(diǎn)為可解節(jié)點(diǎn)，其不可解的后裔節(jié)點(diǎn)不再有用，可從搜索樹中刪去；若已確定某個節(jié)點(diǎn)是不可解節(jié)點(diǎn)，其全部后裔節(jié)點(diǎn)都不再有用，可從搜索樹中刪去。但當(dāng)前這個不可解節(jié)點(diǎn)還不能刪去，在判斷其先輩節(jié)點(diǎn)的可解性時還要用到。提高與/或樹搜索效率的兩個性質(zhì)與/或搜索有兩個特有性質(zhì)，可用寬度優(yōu)先搜索算法流程基本思想：先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展，先進(jìn)先出。把初始節(jié)點(diǎn)S放入OPEN表。把OPEN表中的第一個節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSLD表。如果n可擴(kuò)展，則做下列工作：①擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每個子節(jié)點(diǎn)配置父指針，以備標(biāo)示過程使用。

②考察子節(jié)點(diǎn)中是否有終葉節(jié)點(diǎn)。若有，則標(biāo)示這些終葉節(jié)點(diǎn)為可解節(jié)點(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)先搜索算法流程基本思想：先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展，先進(jìn)先出。寬度優(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)先搜索算法流程4.如果n不可擴(kuò)展，則做下列工作：寬度優(yōu)先搜索算法流程寬度優(yōu)先搜索算法流程寬度優(yōu)先搜索算法流程寬度優(yōu)先搜索算法流程例：與/或樹的寬度優(yōu)先搜索例：設(shè)有如圖所示的與/或樹，其中t1，t2，t3，t4均為終葉節(jié)點(diǎn)，A和B是不可解的端節(jié)點(diǎn)。試采用與/或樹的寬度優(yōu)先搜索法對該圖進(jìn)行搜索。例：與/或樹的寬度優(yōu)先搜索例：設(shè)有如圖所示的與/或樹，其中t例：與/或樹的寬度優(yōu)先搜索Step1：擴(kuò)展1號節(jié)點(diǎn)，得到2、3號節(jié)點(diǎn)。

2、3都不是終葉節(jié)點(diǎn)，接著擴(kuò)展2。OPENCLOSED12,3132,1例：與/或樹的寬度優(yōu)先搜索Step1：擴(kuò)展1號節(jié)點(diǎn)，得到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ù)搜索。OPENCLOSED…………3,42,1t1,2,1…………例：與/或樹的寬度優(yōu)先搜索Step3：擴(kuò)展2，得到4、t1。例：與/或樹的寬度優(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均為可解節(jié)點(diǎn)。還不能確定1為可解節(jié)點(diǎn)。此時5號節(jié)點(diǎn)是OPEN表中的第一個待考察的節(jié)點(diǎn)，所以下一步擴(kuò)展5號節(jié)點(diǎn)。OPENCLOSED…………43,t1,2,15t2,4,3,t1,2,1…………例：與/或樹的寬度優(yōu)先搜索Step3：擴(kuò)展3得到5、B，都不例：與/或樹的寬度優(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：搜索成功，得到解樹。OPENCLOSED…………5,t2,4,3,t1,2,1…………例：與/或樹的寬度優(yōu)先搜索Step5：擴(kuò)展5得到t3、t4。深度優(yōu)先搜索的幾點(diǎn)說明與/或樹的深度優(yōu)先搜索和寬度優(yōu)先搜索過程基本相同。只要把第(3)步的第①點(diǎn)改為“擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每個子節(jié)點(diǎn)配置父指針，以備標(biāo)示過程使用”，就可使后產(chǎn)生的節(jié)點(diǎn)先被擴(kuò)展。也可像狀態(tài)空間的有界深度優(yōu)先搜索那樣，為與/或樹的深度優(yōu)先搜索規(guī)定一個深度界限，使搜索在規(guī)定范圍內(nèi)進(jìn)行。深度優(yōu)先搜索的幾點(diǎn)說明與/或樹的深度優(yōu)先搜索和寬度優(yōu)先搜索過有界深度優(yōu)先搜索算法流程把初始節(jié)點(diǎn)S放人OPEN表。把OPEN表中第一個節(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)先搜索算法流程把初始節(jié)點(diǎn)S放人OPEN表。有界深度優(yōu)先搜索算法流程如果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為不可解節(jié)點(diǎn)，則從OPEN表中刪去有不可解先輩的節(jié)點(diǎn)。③轉(zhuǎn)第(2)步。有界深度優(yōu)先搜索算法流程如果n不可擴(kuò)展，則做下列工作：例：與/或樹的深度優(yōu)先搜索對與/或樹進(jìn)行有界深度優(yōu)先搜索，并規(guī)定深度界限為4，則擴(kuò)展節(jié)點(diǎn)的順序是：1，3，B，5，2，4解樹與寬度優(yōu)先搜索相同。例：與/或樹的深度優(yōu)先搜索對與/或樹進(jìn)行有界深度優(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)選擇某個節(jié)點(diǎn)進(jìn)行擴(kuò)展時，只考慮節(jié)點(diǎn)在與/或樹中的位置，沒有考慮要付出的代價(jià)，因而求得的解樹不一定是代價(jià)最小的解樹，即不一定是最優(yōu)解樹。與/或樹的深度、寬度優(yōu)先搜索特點(diǎn)都是盲目搜索。有序搜索的基本思想

與/或樹的有序搜索是求代價(jià)最小的解樹的搜索方法。為求得代價(jià)最小的解樹，每次確定待擴(kuò)展節(jié)點(diǎn)時，需要往前多看幾步，計(jì)算擴(kuò)展這個節(jié)點(diǎn)可能要付出的代價(jià)，并選擇代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。像這樣根據(jù)代價(jià)決定搜索路線的方法稱為與/或樹的有序搜索，它是一種啟發(fā)式搜索策略。有序搜索的基本思想與/或樹的有序搜索是求代價(jià)最小的解樹的代價(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ò)展，且不是終葉節(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à)法解樹的代價(jià)計(jì)算方法通過計(jì)算解樹中節(jié)點(diǎn)的代價(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à)最大代價(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例：與/或樹的有序搜索例：設(shè)有如圖所示與/或樹，包括兩棵解樹代價(jià)計(jì)算中存在的問題計(jì)算h(x)的條件：已知x所有子節(jié)點(diǎn)的代價(jià)。問題：搜索是自上而下進(jìn)行的，只有不可擴(kuò)展節(jié)點(diǎn)的代價(jià)是已知的（或0），因此除非x的所有子節(jié)點(diǎn)都不可擴(kuò)展，否則x的代價(jià)無法計(jì)算得到。解決方案：根據(jù)問題本身提供的啟發(fā)性信息定義一個啟發(fā)函數(shù)，由啟發(fā)函數(shù)估算子節(jié)點(diǎn)的代價(jià)，然后反推計(jì)算父節(jié)點(diǎn)和先輩節(jié)點(diǎn)的代價(jià)。每當(dāng)有新一代的節(jié)點(diǎn)生成時，都要自下而上地重新計(jì)算先輩節(jié)點(diǎn)的代價(jià)。希望樹代價(jià)計(jì)算中存在的問題計(jì)算h(x)的條件：已知x所有子節(jié)點(diǎn)的代希望樹的定義

選擇待擴(kuò)展節(jié)點(diǎn)時，挑選有希望成為最優(yōu)解樹一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展，保證任一時刻求出的部分解樹的代價(jià)都是最小的。由這些節(jié)點(diǎn)及先輩節(jié)點(diǎn)（包括初始節(jié)點(diǎn)S）構(gòu)成的與/或樹有可能成為最優(yōu)解樹一部分，被稱為希望樹。注意：搜索過程中，隨著新節(jié)點(diǎn)的不斷生成，節(jié)點(diǎn)的代價(jià)值不斷變化。因此，希望樹也是在不斷變化的。有序搜索是一個不斷選擇、不斷修正希望樹的過程。希望樹的定義選擇待擴(kuò)展節(jié)點(diǎn)時，挑選有希希望樹的構(gòu)成初始節(jié)點(diǎn)S在希望樹中；如果節(jié)點(diǎn)x在希望樹中，則一定有：如果x是“或”節(jié)點(diǎn)，y1，y2，…，yn是它的子節(jié)點(diǎn)，則具有值的那個子節(jié)點(diǎn)yi也應(yīng)在希望樹中。如果x是“與”節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在希望樹中。希望樹的構(gòu)成初始節(jié)點(diǎn)S在希望樹中；有序搜索算法流程(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表中刪去具有可解先輩的節(jié)點(diǎn)。有序搜索算法流程(1)把初始節(jié)點(diǎn)S放入OPEN表中。(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表，并為每個子節(jié)點(diǎn)配置父指針。 ③計(jì)算子節(jié)點(diǎn)的h值及其先輩節(jié)點(diǎn)的h值。(7)轉(zhuǎn)第(2)步。(5)如果N不是終葉節(jié)點(diǎn)，且不可擴(kuò)展，則做下列工作：3.2.4與/或樹的有序搜索3.2.4與/或樹的有序搜索例：與/或樹的有序搜索例：設(shè)與/或樹初始節(jié)點(diǎn)為S0，每次擴(kuò)展兩層，一層是“與”節(jié)點(diǎn)，一層是“或”節(jié)點(diǎn)。希望樹生成時，采用和代價(jià)法，c(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)=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é)點(diǎn)E擴(kuò)展兩層后得到的與/或樹例：與/或樹的有序搜索例：設(shè)與/或樹初始節(jié)點(diǎn)為S0，每次擴(kuò)例：與/或樹的有序搜索Step2：

h(G)=7

h(H)=6 h(E)=7

h(D)=11hD(S0)=12S0的左子樹是希望樹左子樹代價(jià)：hA(S0)=9例：與/或樹的有序搜索Step2：S0的左子樹是希望樹左子樹例：與/或樹的有序搜索Step3：h(L)=2，h(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也無法判斷例：與/或樹的有序搜索Step3：終葉節(jié)點(diǎn)L和B都是可解節(jié)點(diǎn)例：與/或樹的有序搜索Step4：擴(kuò)展Ch(N)=2，h(P)=7，h(C)=3，h(A)=8，hA(S0)=9終葉節(jié)點(diǎn)N、C、B可解A可解S0可解最優(yōu)解樹例：與/或樹的有序搜索Step4：擴(kuò)展C終葉節(jié)點(diǎn)N、C、B可什么是博弈？

博弈一直是啟發(fā)式搜索的一個重要應(yīng)用領(lǐng)域，早在20世紀(jì)60年代就已經(jīng)出現(xiàn)若干博弈系統(tǒng)，美國IBM公司的“深藍(lán)”系統(tǒng)已達(dá)到了國際特級大師級的水平?！岸肆愫汀⑷畔?、非偶然”是最簡單的博弈：對壘的A、B雙方輪流采取行動，結(jié)果只有三種情況：A勝B敗，A敗B勝，雙方和局；對壘過程中，任何一方都了解當(dāng)前及過去歷史；任何一方在采取行動前都要根據(jù)當(dāng)前實(shí)際情況，進(jìn)行得失分析，選取對自己最有利而對對方最不利的對策。什么是博弈？博弈一直是啟發(fā)式搜索的一個博弈樹的形成博弈過程中，設(shè)我方為A方，則可供A方選擇的若干行動方案之間是“或”關(guān)系；在A方行動方案基礎(chǔ)上，B方也有若干個可供選擇的行動方案，則這些方案對A方來說就是“與”關(guān)系。如此，逐層擴(kuò)展，并用圖表示博弈過程，得到的就是一棵與/或樹，描述博弈過程的與/或樹被稱為博弈樹。博弈樹的形成博弈過程中，設(shè)我方為A方，則可供A方選擇的若干行博弈樹搜索的特點(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)。所有能使自己一方獲勝的終局都是本原問題，相應(yīng)節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。問題：如何從眾多可供選擇的行動方案中選出一個對自己有利的行動方案。最常用的分析方法是極大極小分析法博弈樹搜索的特點(diǎn)博弈的初始格局是初始節(jié)點(diǎn)。最常用的分析方法是極大極小分析法的基本思想根據(jù)問題特性定義一個估價(jià)函數(shù)?？紤]每一方案實(shí)施后，對方可能采取的所有行動，利用估價(jià)函數(shù)估算當(dāng)前博弈樹端節(jié)點(diǎn)得分（靜態(tài)估值）。利用端節(jié)點(diǎn)的估值推算其父節(jié)點(diǎn)得分（倒推值）。對“或”節(jié)點(diǎn)，為了選一個對自己最有利的方案，選其子節(jié)點(diǎn)中的最大得分作為父節(jié)點(diǎn)得分；對“與”節(jié)點(diǎn)，立足于最壞情況，選其子節(jié)點(diǎn)中的最小得分作為父節(jié)點(diǎn)得分。具有較大倒推值的行動方案就是當(dāng)前最好的行動方案。極大極小分析法的基本思想根據(jù)問題特性定義一個估價(jià)函數(shù)?？紤]每倒推值的計(jì)算注意：由于完整的博弈樹過于龐大，在博弈問題中，可行的方法是只生成一定深度的博弈樹。倒推值的計(jì)算注意：由于完整的博弈樹過于龐大，在博弈問題中，可例：博弈樹搜索——一字棋游戲

例：設(shè)有如圖所示九個空格，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ù)目。bae(P)=3-1=2例：博弈樹搜索——一字棋游戲例：設(shè)有如圖所示九個空格，A、例：博弈樹搜索——一字棋游戲e(P)=e(+P)-e(-P)=2-1=1A的最佳走步A走S3后，B的最優(yōu)選擇是S4，因?yàn)樗撵o態(tài)估值較小，對A不利。例：博弈樹搜索——一字棋游戲e(P)=e(+P)-e(-P)極大極小法的缺點(diǎn)首先，生成一定深度的博弈樹。然后，對端節(jié)點(diǎn)進(jìn)行估值，再計(jì)算上層節(jié)點(diǎn)的倒推值，效率較低。分析可知：博弈樹具有“與”、“或”節(jié)點(diǎn)逐層交替出現(xiàn)的特點(diǎn)，如能邊生成節(jié)點(diǎn)邊計(jì)算估值及倒推值，就有可能刪去一些不必要的節(jié)點(diǎn)，從而減少搜索及計(jì)算的工作量。-剪枝技術(shù)極大極小法的缺點(diǎn)首先，生成一定深度的博弈樹。然后，對端節(jié)點(diǎn)進(jìn)什么是-剪枝技術(shù)？

邊生成邊計(jì)算，從而剪去某些分枝的技術(shù)。對“與”節(jié)點(diǎn)，取當(dāng)前子節(jié)點(diǎn)中最小倒推值作為它的倒推值上界，該值被稱為值。對“或”節(jié)點(diǎn)，取當(dāng)前子節(jié)點(diǎn)中最大倒推值作為它的倒推值下界，該值被稱為值。什么是-剪枝技術(shù)？ 邊生成邊計(jì)算，從而剪去某些分枝的技術(shù)例：-剪枝技術(shù)例：設(shè)按每次生成兩層的原則得到如圖所示博弈樹。各端節(jié)點(diǎn)估值如圖所示，其中S6的估值還沒有計(jì)算出。由S3、S4的估值得到Sl的倒推值為3。設(shè)S6的估值2，則S2的倒推值為2，此時，S0的倒推值為3。設(shè)S6的估值<2，則S2的倒推值<2，此時，S0的倒推值也為3。結(jié)論：雖然S6的估值還沒有計(jì)算出，但不影響對上層節(jié)點(diǎn)倒推值的推算，這表示這個分枝可以從博弈樹中刪去。例：-剪枝技術(shù)例：設(shè)按每次生成兩層的原則得到如圖所示博弈-剪枝技術(shù)的一般規(guī)律剪枝 對“或”節(jié)點(diǎn)x，如果x的值不能降低其父節(jié)點(diǎn)的值，則對x以下的分枝可停止搜索，并使x的倒推值為。這種剪枝稱為剪枝。剪枝 對“與”節(jié)點(diǎn)x，如果x的值不能升高其父節(jié)點(diǎn)的值，則對x以下的分枝可停止搜索，并使x的倒推值為。這種剪枝稱為剪枝。-剪枝技術(shù)的一般規(guī)律剪枝S0BADBCBDHGFBDHGNMLBDH*PBD*QB*IB*SR2841*-2*591*-5*2≤1≤-25≤1≤-5≥2≥5≥1≤2≤1≥2***

So

ABCDEFGHIJK

LMNPQRSTUOPEN表S0BADBCBDHGFBDHGNMLBDH*PBD*QB*

6.3與/或樹的搜索策略一般搜索過程寬度優(yōu)先搜索深度優(yōu)先搜索有序搜索博弈樹搜索-剪枝技術(shù)6.3與/或樹的搜索策略一般搜索過程可解節(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)時，只要子節(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)才是可解節(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)的過程稱為不可解標(biāo)示過程。不可解節(jié)點(diǎn)的定義為：關(guān)于可解節(jié)點(diǎn)的三個條件全部不滿足的節(jié)點(diǎn)，稱為不可解節(jié)點(diǎn)；可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)在與/或樹上執(zhí)行搜索過程，目的在于表明起一般搜索過程流程(1)把原始問題作為初始節(jié)點(diǎn)S，并把它作為當(dāng)前節(jié)點(diǎn)。(2)應(yīng)用分解或等價(jià)變換算符對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展。(3)為每個子節(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)為止。由這個搜索過程所形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱為搜索樹。搜索中，通過可解標(biāo)示過程確定初始節(jié)點(diǎn)是可解的，則由此初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)就構(gòu)成了解樹。一般搜索過程流程(1)把原始問題作為初始節(jié)點(diǎn)S，并把它作為當(dāng)提高與/或樹搜索效率的兩個性質(zhì)與/或搜索有兩個特有性質(zhì)，可用來提高搜索效率：如果已確定某個節(jié)點(diǎn)為可解節(jié)點(diǎn)，其不可解的后裔節(jié)點(diǎn)不再有用，可從搜索樹中刪去；若已確定某個節(jié)點(diǎn)是不可解節(jié)點(diǎn)，其全部后裔節(jié)點(diǎn)都不再有用，可從搜索樹中刪去。但當(dāng)前這個不可解節(jié)點(diǎn)還不能刪去，在判斷其先輩節(jié)點(diǎn)的可解性時還要用到。提高與/或樹搜索效率的兩個性質(zhì)與/或搜索有兩個特有性質(zhì)，可用寬度優(yōu)先搜索算法流程基本思想：先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展，先進(jìn)先出。把初始節(jié)點(diǎn)S放入OPEN表。把OPEN表中的第一個節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSLD表。如果n可擴(kuò)展，則做下列工作：①擴(kuò)展n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每個子節(jié)點(diǎn)配置父指針，以備標(biāo)示過程使用。

②考察子節(jié)點(diǎn)中是否有終葉節(jié)點(diǎn)。若有，則標(biāo)示這些終葉節(jié)點(diǎn)為可解節(jié)點(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)先搜索算法流程基本思想：先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展，先進(jìn)先出。寬度優(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)先搜索算法流程4.如果n不可擴(kuò)展，則做下列工作：寬度優(yōu)先搜索算法流程寬度優(yōu)先搜索算法流程寬度優(yōu)先搜索算法流程寬度優(yōu)先搜索算法流程例：與/或樹的寬度優(yōu)先搜索例：設(shè)有如圖所示的與/或樹，其中t1，t2，t3，t4均為終葉節(jié)點(diǎn)，A和B是不可解的端節(jié)點(diǎn)。試采用與/或樹的寬度優(yōu)先搜索法對該圖進(jìn)行搜索。例：與/或樹的寬度優(yōu)先搜索例：設(shè)有如圖所示的與/或樹，其中t例：與/或樹的寬度優(yōu)先搜索Step1：擴(kuò)展1號節(jié)點(diǎn)，得到2、3號節(jié)點(diǎn)。

2、3都不是終葉節(jié)點(diǎn)，接著擴(kuò)展2。OPENCLOSED12,3132,1例：與/或樹的寬度優(yōu)先搜索Step1：擴(kuò)展1號節(jié)點(diǎn)，得到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ù)搜索。OPENCLOSED…………3,42,1t1,2,1…………例：與/或樹的寬度優(yōu)先搜索Step3：擴(kuò)展2，得到4、t1。例：與/或樹的寬度優(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均為可解節(jié)點(diǎn)。還不能確定1為可解節(jié)點(diǎn)。此時5號節(jié)點(diǎn)是OPEN表中的第一個待考察的節(jié)點(diǎn)，所以下一步擴(kuò)展5號節(jié)點(diǎn)。OPENCLOSED…………43,t1,2,15t2,4,3,t1,2,1…………例：與/或樹的寬度優(yōu)先搜索Step3：擴(kuò)展3得到5、B，都不例：與/或樹的寬度優(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：搜索成功，得到解樹。OPENCLOSED…………5,t2,4,3,t1,2,1…………例：與/或樹的寬度優(yōu)先搜索Step5：擴(kuò)展5得到t3、t4。深度優(yōu)先搜索的幾點(diǎn)說明與/或樹的深度優(yōu)先搜索和寬度優(yōu)先搜索過程基本相同。只要把第(3)步的第①點(diǎn)改為“擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每個子節(jié)點(diǎn)配置父指針，以備標(biāo)示過程使用”，就可使后產(chǎn)生的節(jié)點(diǎn)先被擴(kuò)展。也可像狀態(tài)空間的有界深度優(yōu)先搜索那樣，為與/或樹的深度優(yōu)先搜索規(guī)定一個深度界限，使搜索在規(guī)定范圍內(nèi)進(jìn)行。深度優(yōu)先搜索的幾點(diǎn)說明與/或樹的深度優(yōu)先搜索和寬度優(yōu)先搜索過有界深度優(yōu)先搜索算法流程把初始節(jié)點(diǎn)S放人OPEN表。把OPEN表中第一個節(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)先搜索算法流程把初始節(jié)點(diǎn)S放人OPEN表。有界深度優(yōu)先搜索算法流程如果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為不可解節(jié)點(diǎn)，則從OPEN表中刪去有不可解先輩的節(jié)點(diǎn)。③轉(zhuǎn)第(2)步。有界深度優(yōu)先搜索算法流程如果n不可擴(kuò)展，則做下列工作：例：與/或樹的深度優(yōu)先搜索對與/或樹進(jìn)行有界深度優(yōu)先搜索，并規(guī)定深度界限為4，則擴(kuò)展節(jié)點(diǎn)的順序是：1，3，B，5，2，4解樹與寬度優(yōu)先搜索相同。例：與/或樹的深度優(yōu)先搜索對與/或樹進(jìn)行有界深度優(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)選擇某個節(jié)點(diǎn)進(jìn)行擴(kuò)展時，只考慮節(jié)點(diǎn)在與/或樹中的位置，沒有考慮要付出的代價(jià)，因而求得的解樹不一定是代價(jià)最小的解樹，即不一定是最優(yōu)解樹。與/或樹的深度、寬度優(yōu)先搜索特點(diǎn)都是盲目搜索。有序搜索的基本思想

與/或樹的有序搜索是求代價(jià)最小的解樹的搜索方法。為求得代價(jià)最小的解樹，每次確定待擴(kuò)展節(jié)點(diǎn)時，需要往前多看幾步，計(jì)算擴(kuò)展這個節(jié)點(diǎn)可能要付出的代價(jià)，并選擇代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。像這樣根據(jù)代價(jià)決定搜索路線的方法稱為與/或樹的有序搜索，它是一種啟發(fā)式搜索策略。有序搜索的基本思想與/或樹的有序搜索是求代價(jià)最小的解樹的代價(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ò)展，且不是終葉節(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à)法解樹的代價(jià)計(jì)算方法通過計(jì)算解樹中節(jié)點(diǎn)的代價(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à)最大代價(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例：與/或樹的有序搜索例：設(shè)有如圖所示與/或樹，包括兩棵解樹代價(jià)計(jì)算中存在的問題計(jì)算h(x)的條件：已知x所有子節(jié)點(diǎn)的代價(jià)。問題：搜索是自上而下進(jìn)行的，只有不可擴(kuò)展節(jié)點(diǎn)的代價(jià)是已知的（或0），因此除非x的所有子節(jié)點(diǎn)都不可擴(kuò)展，否則x的代價(jià)無法計(jì)算得到。解決方案：根據(jù)問題本身提供的啟發(fā)性信息定義一個啟發(fā)函數(shù)，由啟發(fā)函數(shù)估算子節(jié)點(diǎn)的代價(jià)，然后反推計(jì)算父節(jié)點(diǎn)和先輩節(jié)點(diǎn)的代價(jià)。每當(dāng)有新一代的節(jié)點(diǎn)生成時，都要自下而上地重新計(jì)算先輩節(jié)點(diǎn)的代價(jià)。希望樹代價(jià)計(jì)算中存在的問題計(jì)算h(x)的條件：已知x所有子節(jié)點(diǎn)的代希望樹的定義

選擇待擴(kuò)展節(jié)點(diǎn)時，挑選有希望成為最優(yōu)解樹一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展，保證任一時刻求出的部分解樹的代價(jià)都是最小的。由這些節(jié)點(diǎn)及先輩節(jié)點(diǎn)（包括初始節(jié)點(diǎn)S）構(gòu)成的與/或樹有可能成為最優(yōu)解樹一部分，被稱為希望樹。注意：搜索過程中，隨著新節(jié)點(diǎn)的不斷生成，節(jié)點(diǎn)的代價(jià)值不斷變化。因此，希望樹也是在不斷變化的。有序搜索是一個不斷選擇、不斷修正希望樹的過程。希望樹的定義選擇待擴(kuò)展節(jié)點(diǎn)時，挑選有希希望樹的構(gòu)成初始節(jié)點(diǎn)S在希望樹中；如果節(jié)點(diǎn)x在希望樹中，則一定有：如果x是“或”節(jié)點(diǎn)，y1，y2，…，yn是它的子節(jié)點(diǎn)，則具有值的那個子節(jié)點(diǎn)yi也應(yīng)在希望樹中。如果x是“與”節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在希望樹中。希望樹的構(gòu)成初始節(jié)點(diǎn)S在希望樹中；有序搜索算法流程(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表中刪去具有可解先輩的節(jié)點(diǎn)。有序搜索算法流程(1)把初始節(jié)點(diǎn)S放入OPEN表中。(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表，并為每個子節(jié)點(diǎn)配置父指針。 ③計(jì)算子節(jié)點(diǎn)的h值及其先輩節(jié)點(diǎn)的h值。(7)轉(zhuǎn)第(2)步。(5)如果N不是終葉節(jié)點(diǎn)，且不可擴(kuò)展，則做下列工作：3.2.4與/或樹的有序搜索3.2.4與/或樹的有序搜索例：與/或樹的有序搜索例：設(shè)與/或樹初始節(jié)點(diǎn)為S0，每次擴(kuò)展兩層，一層是“與”節(jié)點(diǎn)，一層是“或”節(jié)點(diǎn)。希望樹生成時，采用和代價(jià)法，c(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)=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é)點(diǎn)E擴(kuò)展兩層后得到的與/或樹例：與/或樹的有序搜索例：設(shè)與/或樹初始節(jié)點(diǎn)為S0，每次擴(kuò)例：與/或樹的有序搜索Step2：

h(G)=7

h(H)=6 h(E)=7

h(D)=11hD(S0)=12S0的左子樹是希望樹左子樹代價(jià)：hA(S0)=9例：與/或樹的有序搜索Step2：S0的左子樹是希望樹左子樹例：與/或樹的有序搜索Step3：h(L)=2，h(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也無法判斷例：與/或樹的有序搜索Step3：終葉節(jié)點(diǎn)L和B都是可解節(jié)點(diǎn)例：與/或樹的有序搜索Step4：擴(kuò)展Ch(N)=2，h(P)=7，h(C)=3，h(A)=8，hA(S0)=9終葉節(jié)點(diǎn)N、C、B可解A可解S0可解最優(yōu)解樹例：與/或樹的有序搜索Step4：擴(kuò)展C終葉節(jié)點(diǎn)N、C、B可什么是博弈？

博弈一直是啟發(fā)式搜索的一個重要應(yīng)用領(lǐng)域，早在20世紀(jì)60年代就已經(jīng)出現(xiàn)若干博弈系統(tǒng)，美國IBM公司的“深藍(lán)”系統(tǒng)已達(dá)到了國際特級大師級的水平。“二人零和、全信息、非偶然”是最簡單的博弈：對壘的A、B雙方輪流采取行動，結(jié)果只有三種情況：A勝B敗，A敗B勝，雙方和局；對壘過程中，任何一方都了解當(dāng)前及過去歷史；任何一方在采取行動前都要根據(jù)當(dāng)前實(shí)際情況，進(jìn)行得失分析，選取對自己最有利而對對方最不利的對策。什么是博弈？博弈一直是啟發(fā)式搜索的一個博弈樹的形成博弈過程中，設(shè)我方為A方，則可供A方選擇的若干行動方案之間是“或”關(guān)系；在A方行動方案基礎(chǔ)上，B方也有若干個可供選擇的行動方案，則這些方案對A方來說就是“與”關(guān)系。如此，逐層擴(kuò)展，并用圖表示博弈過程，得到的就是一棵與/或樹，描述博弈過程的與/或樹被稱為博弈樹。博弈樹的形成博弈過程中，設(shè)我方為A方，則可供A方選擇的若干行博弈樹搜索的特點(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)。所有能使自己一方獲勝的終局都是本原問題，相應(yīng)節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。問題：如何從眾多可供選擇的行動方案中選出一個對自己有利的行動方案。最常用的分析方法是極大極小分析法博弈樹搜索的特點(diǎn)博弈的初始格局是初始節(jié)點(diǎn)。最常用的分析方法是極大極小分析法的基本思想根據(jù)問題特性定義一個估價(jià)函數(shù)?？紤]每一方案實(shí)施后，對方可能采取的所有行動，利用估價(jià)函數(shù)估算當(dāng)前博弈樹端節(jié)點(diǎn)得分（靜態(tài)估值）。利用端節(jié)點(diǎn)的估值推算其父節(jié)點(diǎn)得分（倒推值）。對“或”節(jié)點(diǎn)，為了選一個對自己最有利的方案，選其子節(jié)點(diǎn)中的最大得分作為父節(jié)點(diǎn)得分；對“與”節(jié)點(diǎn)，立足于最壞情況，選其子節(jié)點(diǎn)中的最小得分作為父節(jié)點(diǎn)得分。具有較大倒推值的行動方案就是當(dāng)前最好的行動方案。極大極小分析法的基本思想根據(jù)問題特性定義一個估價(jià)函數(shù)?？紤]每倒推值的計(jì)算注意：由于完整的博弈樹過于龐大