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