與或樹的搜索策略_搜索的完備性與效率(文件)
【正文】 節(jié)點可能要付出的代價，計算擴展這個節(jié)點可能要付出的代價，并選擇代價最小的節(jié)點進行擴展并選擇代價最小的節(jié)點進行擴展 。若問題可解，由子節(jié)點代價推通過計算解樹中節(jié)點的代價得到。在與 /或樹中，邊上的數(shù)字是該邊的代價， t1, t2 , t3, t4, t5為終葉節(jié)點，代價為 0， E, F是端節(jié)點，代價為 ?。解決方案： 根據(jù)問題本身提供的啟發(fā)性信息定義一個 啟發(fā)函數(shù) ，由啟發(fā)函數(shù)估算子節(jié)點的代價，然后反推計算父節(jié)點和先輩節(jié)點的代價。 由這些節(jié)點及先輩節(jié)點（包括初始節(jié)點由這些節(jié)點及先輩節(jié)點（包括初始節(jié)點 S）構(gòu)）構(gòu)成的與成的與 /或樹有可能成為最優(yōu)解樹一部分，被稱為希望或樹有可能成為最優(yōu)解樹一部分，被稱為希望樹。因此， 希望樹希望樹 也是在也是在 不斷變化不斷變化 的。希望樹的構(gòu)成初始節(jié)點初始節(jié)點 S在希望樹中；在希望樹中；如果節(jié)點如果節(jié)點 x在希望樹中，則一定有：l 如果如果 x是是 ““ 或或 ”” 節(jié)點，節(jié)點， y1， y2， …， yn是它的子節(jié)點，則具有是它的子節(jié)點，則具有 值的那個子節(jié)點值的那個子節(jié)點 yi也應(yīng)在希望樹中。有序搜索算法流程(1)把初始節(jié)點把初始節(jié)點 S放入放入 OPEN表中。表中。的先輩節(jié)點。表中刪去具有可解先輩的節(jié)點。的先輩節(jié)點。表中刪去有不可解先輩的節(jié)點。表，并為每個子節(jié)點配置父指針。步。系統(tǒng)已達到了國際特級大師級的水平。關(guān)系。博弈的初始格局是初始節(jié)點。雙方輪流擴展節(jié)點。是可解節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點?？紤]每一方案實施后根據(jù)問題特性定義一個估價函數(shù)。）。具有較大倒推值的行動方案就是當(dāng)前最好的行動方案。 設(shè) A的棋子用 “ a”表示， B的棋子用 “ b”表示， A先走棋。l e(P)：： P上可能使上可能使 b三子成一線的數(shù)目。極大極小法的缺點極大極小法的缺點首先，生成一定深度的博弈樹。分析可知：博弈樹具有分析可知：博弈樹具有 ““ 與與 ”” 、 ““ 或或 ”” 節(jié)點逐層交替出節(jié)點逐層交替出現(xiàn)的特點，如能邊生成節(jié)點邊計算估值及倒推值，就有可能現(xiàn)的特點，如能邊生成節(jié)點邊計算估值及倒推值，就有可能刪去一些不必要的節(jié)點，從而減少搜索及計算的工作量。對對 ““ 與與 ”” 節(jié)點，取當(dāng)前子節(jié)點中最小倒推值作為它的倒節(jié)點，取當(dāng)前子節(jié)點中最小倒推值作為它的倒推值上界，該值被稱為推值上界，該值被稱為 ?值。例： ??剪枝技術(shù)例：設(shè)按每次生成兩層的原則得到如圖所示博弈樹。設(shè)設(shè) S6的估值的估值 2，則，則 S2的倒推值的倒推值 2，此，此時，時， S0的倒推值也為的倒推值也為 3。這種剪枝稱為這種剪枝稱為 ?剪枝。剪枝。?剪枝剪枝對對 ““ 與與 ”” 節(jié)點節(jié)點 x，如果，如果 x的的 ?值不能升高其父節(jié)點的值不能升高其父節(jié)點的 ?值，則對值，則對 x以下的分枝可停止搜索，并使以下的分枝可停止搜索，并使 x的倒推值為的倒推值為 ?。表示這個分枝可以從博弈樹中刪去。由由 S S4的估值得到的估值得到 Sl的倒推值為的倒推值為 3。對對 ““ 或或 ”” 節(jié)點，取當(dāng)前子節(jié)點中最大倒推值作為它的倒節(jié)點，取當(dāng)前子節(jié)點中最大倒推值作為它的倒推值下界，該值被稱為推值下界，該值被稱為 ?值。??剪枝技術(shù)什么是 ??剪枝技術(shù)？邊生成邊計算，從而剪去某些分枝的技術(shù)。然后，對端節(jié)點進行估值，再計算上層節(jié)點的倒推值，效率較低。bae(P) =31=2例：博弈樹搜索 ——一字棋游戲e(P)=e(+P)e(P)=21=1A的最佳走步的最佳走步A走走 S3后，后， B的最優(yōu)選擇的最優(yōu)選擇是是 S4，因為它的靜態(tài)估，因為它的靜態(tài)估值較小，對值較小，對 A不利。 一字棋對對 A方，設(shè)棋局為方，設(shè)棋局為 P，估價函數(shù)，估價函數(shù) e(P)定義為定義為 ：：若若 P是是 A必勝的棋局，則必勝的棋局，則 e(P)=+?若若 P是是 B必勝的棋局，則必勝的棋局，則 e(P)=?若若 P是勝負未定的棋局，則是勝負未定的棋局，則 e(P)=e(+P)e(P)l e(+P)：： P上可能使上可能使 a三子成一線的數(shù)目。法是只生成一定深度的博弈樹。分作為父節(jié)點得分。）。利的行動方案。雙方輪流擴展節(jié)點。自己一方擴展的節(jié)點之間是?；驑浔环Q為博弈樹。得失分析，選取對自己最有利而對對方最不利的對策。希望樹生成時，采用和代價法， c(x, yi)=1。值。的所有子節(jié)點。被標(biāo)示為不可解節(jié)點，則失敗退出。為不可解節(jié)點。就是最優(yōu)解樹，成功退出。為可解節(jié)點。(2)根據(jù)當(dāng)前搜索樹中節(jié)點的代價求出以根據(jù)當(dāng)前搜索樹中節(jié)點的代價求出以 S為根的希望樹為根的希望樹 T 。l 如果如果 x是是 ““ 與與 ”” 節(jié)點，則它的全部子節(jié)點都應(yīng)在希望樹中。l 有序搜索是一個不斷選擇、不斷修正希望樹的過程。注意：注意：l 搜索過程中，隨著新節(jié)點的不斷生成，節(jié)點的代價值不斷搜索過程中，隨著新節(jié)點的不斷生成，節(jié)點的代價值不斷變化。希望樹希望樹的定義 選擇待擴展節(jié)點時，挑選有希望成為最優(yōu)解樹一部分選擇待擴展節(jié)點時，挑選有希望成為最優(yōu)解樹一部分的節(jié)點進行擴展，保證任一時刻求出的部分解樹的代價的節(jié)點進行擴展，保證任一時刻求出的部分解樹的代價都是最小的。和代價和代價 最大代價最大代價左邊左邊解樹解樹h(A)=11h(S)=
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1