與或圖搜索問(wèn)題ppt課件-資料下載頁(yè)
2025-05-05 18:36本頁(yè)面
【正文】 9 3 0 3 3 3 3 2 1 3 6 3 0 3 1 6 0 1 1 極大 極小 a b 52 極大極小分析法：一子棋 ? 一子棋游戲：估價(jià)函數(shù)定義如下 ? 設(shè)棋局為 P，估價(jià)函數(shù)為 e(P)： ? 1. 若 P是 A必勝的棋局，則 e(P)＝＋ ?； ? 2. 若 P是 B必勝的棋局，則 e(P)＝－ ?； ? 3. 若 P是勝負(fù)未定的棋局，則 e(P)=e(+P)e(P)。其中， e(+P)表示在棋局 P上添上所有的 a后直線(xiàn)的數(shù)目， e(P)表示在棋局P上添上所有的 b后直線(xiàn)的數(shù)目。 53 極大極小分析法：一子棋 A的第一著棋生成的博弈樹(shù)。每一著棋都要導(dǎo)致博弈樹(shù)深度加 2：一層是自己，一層是對(duì)方。 54 55 56 ??剪枝 ? 上述的極小極大分析法，實(shí)際是先生成一棵博弈樹(shù)，然后再計(jì)算其倒推值，致使極小極大分析法效率較低。于是在極小極大分析法的基礎(chǔ)上提出了 αβ剪枝技術(shù)。 ? αβ剪枝技術(shù)的基本思想或算法是，邊生成博弈樹(shù)邊計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹(shù)上的一些分枝，從而節(jié)約了機(jī)器開(kāi)銷(xiāo)，提高了搜索效率。 57 ??剪枝 S0 A B E D C H G F N M L P Q X X I S R X J T X K U X X X 2 8 4 1 2 5 9 1 5 2 ?1 ?2 ?2 5 ?2 ?5 ?1 ?5 ?1 ?1 ?2 “與”節(jié)點(diǎn) G的 ?值不能升高其父節(jié)點(diǎn) C的 ?值，則對(duì)節(jié)點(diǎn) G以下的分枝可停止搜索，并使 G的倒推值為?。這種剪枝稱(chēng)為 ?剪枝 ?“或”節(jié)點(diǎn) D的 ?值不能降低其父節(jié)點(diǎn) A的 ?值，則對(duì)節(jié)點(diǎn) D以下的分枝可停止搜索，并使 D的倒推值為 ?。這種剪枝稱(chēng)為 ?剪枝。 58 ? (1) 對(duì)于一個(gè)與節(jié)點(diǎn) MIN，若能估計(jì)出其倒推值的上確界 β，并且這個(gè) β值不大于 MIN的父節(jié)點(diǎn) (一定是或節(jié)點(diǎn) )的估計(jì)倒推值的下確界 α，即 α≥β，則就不必再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了 (因?yàn)檫@些節(jié)點(diǎn)的估值對(duì) MIN父節(jié)點(diǎn)的倒推值已無(wú)任何影響 了 )。這一過(guò)程稱(chēng)為 α剪枝。 (2) 對(duì)于一個(gè)或節(jié)點(diǎn) MAX，若能估計(jì)出其倒推值的下確界 α，并且這個(gè) α值不小于 MAX的父節(jié)點(diǎn) (一定是與節(jié)點(diǎn) )的估計(jì)倒推值的上確界 β，即 α≥β，則就不必再擴(kuò)展該 MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了 (因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MAX父節(jié)點(diǎn)的倒推值已無(wú)任何影響 了 )。這一過(guò)程稱(chēng)為 β剪枝。 59 ? 從算法中看到： (1) MAX節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 α值永不減少； (2) MIN節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 β值永不增加。 在搜索期間， α和 β值的計(jì)算如下： (1) 一個(gè) MAX節(jié)點(diǎn)的 α值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。 (2) 一個(gè) MIN節(jié)點(diǎn)的 β值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。 60 61 ? 畫(huà)出根節(jié)點(diǎn)、節(jié)點(diǎn) A及 5個(gè)子節(jié)點(diǎn)，計(jì)算并標(biāo)上這些節(jié)點(diǎn)的靜態(tài)估值， A的 5個(gè)子節(jié)點(diǎn)的靜態(tài)估值的最小值是 1，因此節(jié)點(diǎn) A的倒推值為 1，從而起始節(jié)點(diǎn)的倒推值的下界 α定為 1，當(dāng)然有可能比 1更小，因?yàn)樗衅渌淖庸?jié)點(diǎn)。 畫(huà)出節(jié)點(diǎn) B及它的第一個(gè)兒子節(jié)點(diǎn) C，算出節(jié)點(diǎn) C的靜態(tài)值為 1，于是節(jié)點(diǎn) B的倒推值不會(huì)比 1大，又注意到節(jié)點(diǎn) B的最終倒推值不會(huì)小于起始節(jié)點(diǎn)的 α值，由此可肯定最終倒推值 β=1。由于 α值不比 β值小，故可以終止節(jié)點(diǎn) B的搜索。 62 ? 例： αβ剪枝技術(shù)的例子，圖 。圖中所生成的搜索樹(shù)共有六層 (我們規(guī)定首先生成最左面的節(jié)點(diǎn)。 MAX節(jié)點(diǎn)用方塊表示， MIN節(jié)點(diǎn)用圓圈表示 )。圖中還給出了端節(jié)點(diǎn)的靜態(tài)估值?，F(xiàn)在假設(shè)我們采用 αβ剪枝技術(shù)來(lái)引導(dǎo)深度優(yōu)先搜索。由 αβ剪枝技術(shù)生成的子樹(shù)在圖中用粗樹(shù)枝表示。發(fā)生修剪的那些節(jié)點(diǎn)用“ ”表示。 63 64 ??剪枝 ? 由上面的例子可以歸納出： ? 1. 任何“或”節(jié)點(diǎn) x的 ?值如果不能降低其父節(jié)點(diǎn)的 ?值，則對(duì)節(jié)點(diǎn) x以下的分枝可停止搜索，并使 x的倒推值為 ?。這種剪枝稱(chēng)為 ?剪枝。 ? 2. 任何“與”節(jié)點(diǎn) x的 ?值如果不能升高其父節(jié)點(diǎn)的 ?值，則對(duì)節(jié)點(diǎn) x以下的分枝可停止搜索，并使 x的倒推值為 ?。這種剪枝稱(chēng)為 ?剪枝。 ? 在 ??剪枝技術(shù)中，一個(gè)節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)的倒推值（或估值）是很重要的。對(duì)于一個(gè)“或”節(jié)點(diǎn)，如果估值最高的子節(jié)點(diǎn)最先生成，或者對(duì)于一個(gè)“與”節(jié)點(diǎn)，估值最低的子節(jié)點(diǎn)最先生成，則被剪除的節(jié)點(diǎn)數(shù)最多，搜索的效率最高。這稱(chēng)為最優(yōu) ??剪枝法。 65 ? 要進(jìn)行 αβ修剪，必須至少使某一部分的搜索樹(shù)生長(zhǎng)到最大深度，因?yàn)?α和 β值必須以端節(jié)點(diǎn)的靜態(tài)估值為依據(jù)。因此采用 αβ剪枝技術(shù)通常都要使用某種深度優(yōu)先的搜索方法。而且在一次搜索期間修剪的枝數(shù)取決于早期的 α、 β值與最終倒推值之間的近似程度。 起始節(jié)點(diǎn)的最終倒推值等于某個(gè)端節(jié)點(diǎn)的靜態(tài)估值。如果在深度優(yōu)先搜索過(guò)程中第一次就遇到這個(gè)端節(jié)點(diǎn)，則修剪枝數(shù)最大。當(dāng)前修剪枝數(shù)最大時(shí)，需要生成和估計(jì)的端節(jié)點(diǎn)數(shù)就最少。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1