《搜索與或圖搜索》ppt課件

1、 內(nèi)容內(nèi)容n 4.0 4.0 與或樹表示與或樹表示n 4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n 4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索n 4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n 4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n 4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索4.0 4.0 與或樹表示與或樹表示n不同于形狀空間方法的另外一種方式化方法。n根本思想：n當(dāng)一個(gè)問(wèn)題比較復(fù)雜時(shí)，直接進(jìn)展求解往往比較困難。n可經(jīng)過(guò)歸約分解或變換，將它轉(zhuǎn)化為一系列較簡(jiǎn)單的問(wèn)題。n經(jīng)過(guò)對(duì)這些較簡(jiǎn)單問(wèn)題的求解來(lái)實(shí)現(xiàn)對(duì)原問(wèn)題的求解。4.

2、0 4.0 與或樹表示與或樹表示n【例4.0】n設(shè)有四邊形ABCD和ABCD，證明它們?nèi)取?.0 4.0 與或樹表示與或樹表示n分析：原問(wèn)題分解為兩個(gè)子問(wèn)題：4.0 4.0 與或樹表示與或樹表示4.0 4.0 與或樹表示與或樹表示n4.0.1 分解n問(wèn)題P可以歸約為一組子問(wèn)題P1,P2,Pn。n只需當(dāng)一切子問(wèn)題Pi(i1，2，n)都有解時(shí),原問(wèn)題P才有解。n即分解所得到的子問(wèn)題的“與和原問(wèn)題P等價(jià)。n與樹nK-銜接符P1P2P3P.K個(gè)4.0 4.0 與或樹表示與或樹表示n4.0.2 等價(jià)變換n問(wèn)題P可以歸約為一組子問(wèn)題P1,P2,Pn。n這些子問(wèn)題Pi中只需有一個(gè)有解那么原問(wèn)題P就有解，只

3、需當(dāng)一切子問(wèn)題Pi都無(wú)解時(shí)原問(wèn)題P才無(wú)解。n即變換所得到的子問(wèn)題的“或與原問(wèn)題P等價(jià)。n或樹n把一個(gè)原問(wèn)題變換為假設(shè)干個(gè)子問(wèn)題可用一個(gè)“或樹來(lái)表示。P1P2P3P4.0 4.0 與或樹表示與或樹表示n4.0.3 與或樹n假設(shè)一個(gè)問(wèn)題既需求經(jīng)過(guò)分解，又需求經(jīng)過(guò)變換才干得到其本原問(wèn)題，那么其歸約過(guò)程可用一個(gè)“與/或樹來(lái)表示。PP1P2P3P31P32P33P11P12原始問(wèn)題本原問(wèn)題終止節(jié)點(diǎn)端節(jié)點(diǎn)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，即葉子節(jié)點(diǎn)；終止節(jié)點(diǎn)可解節(jié)點(diǎn)，即本原問(wèn)題。t4.0 4.0 與或樹表示與或樹表示Ptttn4.0.4 解樹n由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)(它對(duì)應(yīng)著原始問(wèn)題)為可解節(jié)

4、點(diǎn)的子樹。n在解樹中一定包含初始節(jié)點(diǎn)。4.0 4.0 與或樹表示與或樹表示n【例4.1】三階梵塔問(wèn)題。n解：n用三元組表示問(wèn)題在任一時(shí)辰的形狀：(i,j,k)ni：代表金片C所在的鋼針號(hào)；nj: 代表金片B所在的鋼針號(hào)；nk; 代表金片A所在的鋼針號(hào)；1 2 31 2 31 2 31 2 3ABC 1 2 3(1, 1, 1)1 2 3(1, 2, 2)1 2 3(3, 2, 2)1 2 3(3, 3, 3)ABC(1,1,1)-(3,3,3) (1,1,1)-(3,3,3) (1,1,1)-(1,2,2)(1,1,1)-(1,2,2)(1,2,2)-(3,2,2)(1,2,2)-(3,2,2

5、)(3,2,2)-(3,3,3)(3,2,2)-(3,3,3)(1,1,1)-(1,1,3)(1,1,1)-(1,1,3) (1,1,3)-(1,2,3)(1,1,3)-(1,2,3)(1,2,3) (1,2,2)(1,2,3) (1,2,2)(3,2,2)-(3,2,1)(3,2,2)-(3,2,1) (3,2,1) (3,3,1)(3,2,1) (3,3,1)(3,3,1) (3,3,3)(3,3,1) (3,3,3)三階梵塔問(wèn)題的與或樹三階梵塔問(wèn)題的與或樹n在該與/或樹中，有7個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著7個(gè)本原問(wèn)題。假設(shè)把這些本原問(wèn)題從左至右陳列起來(lái)，即得到了原始問(wèn)題的解：4.0 4.0

6、 與或樹表示與或樹表示目的目的目的目的初始節(jié)點(diǎn)初始節(jié)點(diǎn)sabc內(nèi)容內(nèi)容n 4.0 4.0 與或樹表示與或樹表示n 4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n 4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索n 4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n 4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n 4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n與/或樹的搜索過(guò)程實(shí)踐上是一個(gè)不斷尋覓解樹的過(guò)程。其普通搜索過(guò)程如下：n1把原始問(wèn)題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)n 點(diǎn)； n2

7、運(yùn)用分解或等價(jià)變換操作對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)展擴(kuò)展； n3為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； n4選擇適宜的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第n 2步和第3步，在此期間需求多次調(diào)用可解n 標(biāo)志過(guò)程或不可解標(biāo)志過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)n 記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n在與/或樹中，除端節(jié)點(diǎn)和終止節(jié)點(diǎn)外，一個(gè)節(jié)點(diǎn)的可解性完全是由其子節(jié)點(diǎn)來(lái)決議的。n對(duì)與節(jié)點(diǎn)，只需其一切子節(jié)點(diǎn)都為可解時(shí)它才為可解，只需有一個(gè)子節(jié)點(diǎn)不可解它就是不可解的；n對(duì)或節(jié)點(diǎn)，只需有一個(gè)子節(jié)點(diǎn)可解它就是可解的，僅當(dāng)一切子節(jié)點(diǎn)都是不可解時(shí)它才為不可解。n可解標(biāo)志過(guò)程n由可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)

8、、祖父節(jié)點(diǎn)為可解節(jié)點(diǎn)的過(guò)程。n不可解標(biāo)志過(guò)程n由不可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為不可解節(jié)點(diǎn)的過(guò)程。4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n搜索解樹的過(guò)程中，節(jié)點(diǎn)刪除戰(zhàn)略：n 假設(shè)搜索過(guò)程確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn)，那么其不n 可解的后裔節(jié)點(diǎn)就可從搜索樹中刪去；n 假設(shè)搜索過(guò)程能確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn)，那么n 其后裔節(jié)點(diǎn)也可從搜索樹中刪去。內(nèi)容內(nèi)容n 4.0 4.0 與或樹表示與或樹表示n 4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n 4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索n 4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n

9、 4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n 4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索n與/或樹的廣度優(yōu)先搜索算法：n1把初始節(jié)點(diǎn)S0 放人Open表中； n2把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)n 為n； n3假設(shè)節(jié)點(diǎn)n可擴(kuò)展，那么做以下任務(wù)： n擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子 n 節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； n調(diào)查這些子節(jié)點(diǎn)中能否有終止節(jié)點(diǎn)。假設(shè)有，那么標(biāo)志這些終n 止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)志過(guò)程對(duì)其父節(jié)點(diǎn)及先輩 n 節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)展標(biāo)志。n假設(shè)初始

10、解節(jié)點(diǎn)S0可以被標(biāo)志為可解節(jié)點(diǎn)，就得到了解樹，搜索勝利，退出搜索過(guò)程；n假設(shè)不能確定S0為可解節(jié)點(diǎn)，那么從Open表中刪去具有可解先輩的節(jié)點(diǎn)； n轉(zhuǎn)第2步。4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索n搜索算法續(xù)：n4假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么做以下任務(wù)： n 標(biāo)志節(jié)點(diǎn)n為不可解節(jié)點(diǎn)； n 運(yùn)用不可解標(biāo)志過(guò)程對(duì)節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)展標(biāo)志。n假設(shè)初始解節(jié)點(diǎn)S0也被標(biāo)志為不可解節(jié)點(diǎn)，那么搜索失敗，闡明原始問(wèn)題無(wú)解，退出搜索過(guò)程；n假設(shè)不能確定S0為不可解節(jié)點(diǎn)，那么從Open表中刪去具有不可解先輩的節(jié)點(diǎn)； n轉(zhuǎn)第2步。【例【例4.2】 t1、t2、t3的節(jié)點(diǎn)是終止節(jié)點(diǎn)，的節(jié)點(diǎn)

11、是終止節(jié)點(diǎn)，A 、 B 、 C為不可解的端節(jié)點(diǎn)為不可解的端節(jié)點(diǎn)123A4t1t3CBt25(1) 1 2 3 1(2) 2 3 A 4 1 2(3) 3 A 4 5 1 2 3 t1(4) A 4 5 (5) 4 5 B 1 2 3 t1 4 t2(6) 5 B 1 2 3 t1 4 t2 5 t3(7) 搜索勝利搜索勝利, 解樹解樹: 1, 2, 3, 4, 5, t1, t2, t3擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)Open 列表列表Closed列表列表內(nèi)容內(nèi)容n 4.0 4.0 與或樹表示與或樹表示n 4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n 4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或

12、樹的廣度優(yōu)先搜索n 4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n 4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n 4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n與/或樹的深度優(yōu)先搜索算法：n1把初始節(jié)點(diǎn)S0放入 Open表中； n2把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n n； n3假設(shè)節(jié)點(diǎn)n的深度等于dm，那么轉(zhuǎn)第5步的第n 點(diǎn)； n4假設(shè)節(jié)點(diǎn)n可擴(kuò)展，那么做以下任務(wù)：n擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的首部，并為每一n 個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； n調(diào)查這些子

13、節(jié)點(diǎn)中能否有終止節(jié)點(diǎn)。假設(shè)有，那么標(biāo)志這些n 終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)志過(guò)程對(duì)其父節(jié)點(diǎn)及n 先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)展標(biāo)志。假設(shè)初始節(jié)點(diǎn)S0可以n 被標(biāo)志為可解節(jié)點(diǎn)，就得到了解樹，搜索勝利，退出搜n 索過(guò)程；假設(shè)不能確定S0為可解節(jié)點(diǎn)，那么從Open表中刪n 去具有可解先輩的節(jié)點(diǎn)； n轉(zhuǎn)第2步。4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n5假設(shè)節(jié)點(diǎn)n不可擴(kuò)展，那么做以下任務(wù)：n標(biāo)志節(jié)點(diǎn)n為不可解節(jié)點(diǎn)； n運(yùn)用不可解標(biāo)志過(guò)程對(duì)節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)展標(biāo)志。假設(shè)初始節(jié)點(diǎn)S0也被標(biāo)志為不可解節(jié)點(diǎn)，那么搜索失敗，闡明原始問(wèn)題無(wú)解，退出搜索過(guò)程；假設(shè)不能確定為不可解節(jié)點(diǎn)，那

14、么從Open表中刪去具有不可解先輩的節(jié)點(diǎn)； n轉(zhuǎn)第2步。4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n【例4.3】n對(duì)上例所給出的與或樹，假設(shè)按有解深度優(yōu)先搜索，且給定dm=4。n那么其擴(kuò)展節(jié)點(diǎn)的順序?yàn)椋?，3，5，2，4n其解樹與上例一樣。123A4t1t3CBt25內(nèi)容內(nèi)容n 4.0 4.0 與或樹表示與或樹表示n 4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n 4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索n 4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n 4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n 4.5 4.5

15、 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索 與或樹的啟發(fā)式搜索過(guò)程是一種利用搜索過(guò)程所得到的啟發(fā)性信息尋覓最優(yōu)解樹的過(guò)程。對(duì)搜索的每一步，算法都試圖找到一個(gè)最有希望成為最優(yōu)解樹的子樹希望樹。n4.4.1 解樹的代價(jià)與希望樹n最優(yōu)解樹 n指代價(jià)最小的那棵解樹。4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n如何計(jì)算解樹的代價(jià)？目的目的目的目的初始節(jié)點(diǎn)初始節(jié)點(diǎn)abc4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n解樹的代價(jià)可按如下規(guī)那么計(jì)算：n1假設(shè)n為終止節(jié)點(diǎn)：n n2假設(shè)n為或節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1，n2，nk， n n3假設(shè)n為與節(jié)點(diǎn)

16、，且子節(jié)點(diǎn)為n1，n2，nk， n和代價(jià)法：n最大代價(jià)法：n4假設(shè)n是端節(jié)點(diǎn)，但又不是終止節(jié)點(diǎn)：n5根節(jié)點(diǎn)的代價(jià)即為解樹的代價(jià)。n【例4.4】計(jì)算解樹的代價(jià)。n左邊的解樹n和代價(jià)：n最大代價(jià)：n右邊的解樹n和代價(jià)：n最大代價(jià)：S0ABt1Ct3Et2Dt4F22463521終止節(jié)點(diǎn)：終止節(jié)點(diǎn)：t1, t2, t3 和和 t4 端節(jié)點(diǎn)：端節(jié)點(diǎn)：E 和和 F 4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n希望樹n為了找到最優(yōu)解樹，搜索過(guò)程的任何時(shí)辰都應(yīng)該選擇那些最有希望成為最優(yōu)解樹一部分的節(jié)點(diǎn)進(jìn)展擴(kuò)展。由這些節(jié)點(diǎn)及其父節(jié)點(diǎn)所構(gòu)成的子樹，稱為希望樹。n【定義】希望解樹Tn1初始節(jié)點(diǎn)S0在希望

17、樹T中； n2假設(shè)n是具有子節(jié)點(diǎn)n1，n2，nk的或節(jié)點(diǎn)，那么n的n 某個(gè)子節(jié)點(diǎn)ni在希望樹T中的充分必要條件是: n hni= min cn，ni hni 1ik n3假設(shè)n是與節(jié)點(diǎn)，那么n的全部子節(jié)點(diǎn)都在希望樹T中。.nn1nk4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n4.4.2 與或樹的啟發(fā)式搜索過(guò)程n與或樹的啟發(fā)式搜索過(guò)程是不斷地選擇、修正希望樹的過(guò)程，其搜索過(guò)程如下：n1把初始節(jié)點(diǎn)S0放入Open表中，計(jì)算hS0； n2計(jì)算希望樹T； n3依次在Open表中取出T的端節(jié)點(diǎn)放入Closed表，并n 記該節(jié)點(diǎn)為n； n4假設(shè)節(jié)點(diǎn)n為終止節(jié)點(diǎn)，那么做以下任務(wù)：n標(biāo)志節(jié)點(diǎn)n為可解

18、節(jié)點(diǎn)； n在T上運(yùn)用可解標(biāo)志過(guò)程，對(duì)n的先輩節(jié)點(diǎn)中的一切可解節(jié)點(diǎn)進(jìn)展標(biāo)志； n假設(shè)初始節(jié)點(diǎn)S0可以被標(biāo)志為可解節(jié)點(diǎn)，那么T就是最優(yōu)解樹，勝利退出； n否那么，從Open表中刪去具有可解先輩的一切節(jié)點(diǎn)； n轉(zhuǎn)第2步。4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n5假設(shè)節(jié)點(diǎn)n不是終止節(jié)點(diǎn)，但可擴(kuò)展，那么做以下任務(wù)：n 擴(kuò)展節(jié)點(diǎn)n，生成n的一切子節(jié)點(diǎn)； n 把這些子節(jié)點(diǎn)都放入 Open表中，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn) n的指針； n 計(jì)算這些子節(jié)點(diǎn)及其先輩節(jié)點(diǎn)的h值； n 轉(zhuǎn)第2步。n6假設(shè)節(jié)點(diǎn)n不是終止節(jié)點(diǎn)，且不可擴(kuò)展，那么做以下任務(wù)： n 標(biāo)志節(jié)點(diǎn)n為不可解節(jié)點(diǎn)； n 在T上運(yùn)用不可

19、解標(biāo)志過(guò)程，對(duì)n的先輩節(jié)點(diǎn)中的一切不可解節(jié)點(diǎn)進(jìn)展標(biāo)志； n 假設(shè)初始節(jié)點(diǎn)S。可以被標(biāo)志為不可解節(jié)點(diǎn)，那么問(wèn)題無(wú)解，失敗退出； n 否那么，從Open表中刪去具有不可解先輩的一切節(jié)點(diǎn)；n 轉(zhuǎn)第2步。4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n【例4.5】假設(shè)搜索過(guò)程每次擴(kuò)展節(jié)點(diǎn)時(shí)都同擴(kuò)展兩層，且按一層或節(jié)點(diǎn)、一層與節(jié)點(diǎn)的間隔方式進(jìn)展擴(kuò)展。887S0ADBCEF3332希望樹希望樹T : 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn) S0 后后4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索S0ADBCEF8332 3222776119S0ADBCEF8332 3222776119GKHILJ0022264.4

20、 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索S0DEF8332 3222776119IGKHLJ002226MNP003229ABC內(nèi)容內(nèi)容n 4.0 4.0 與或樹表示與或樹表示n 4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n 4.2 4.2 與與/ /或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索n 4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n 4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n 4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n4.5.1 概述n機(jī)遇性博弈n存在不可預(yù)測(cè)性的博弈。n雙人完備

21、信息博弈n兩位選手對(duì)壘，輪番走步，每一方不僅知道對(duì)方曾經(jīng)走過(guò)的棋步，而且還能估計(jì)出對(duì)方未來(lái)的走步。對(duì)弈的結(jié)果是一方贏，另一方輸；或者雙方和局。n任何一方走步時(shí)，都是選擇對(duì)本人最為有利，而對(duì)另一方最為不利的行動(dòng)方案。n假設(shè)博弈的一方為MAX，另一方為MIN。n在博棄過(guò)程的每一步，可供MAX和MIN選擇的行動(dòng)方案都能夠有多種。4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索MINMAXMINMAXMINMAX分分錢錢幣幣問(wèn)問(wèn)題題對(duì)方先走我方必勝4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n博弈樹n把雙人完備信息博弈過(guò)程用圖表示出來(lái)，就可得到一棵與/或樹。n下一步該MAX走步的節(jié)點(diǎn)稱為M

22、AX節(jié)點(diǎn)。n下一步該MIN走步的節(jié)點(diǎn)稱為MIN節(jié)點(diǎn)。n博弈樹具有如下特點(diǎn)：n博弈的初始形狀是初始節(jié)點(diǎn)；n博弈樹中的“或節(jié)點(diǎn)和“與節(jié)點(diǎn)是逐層交替出現(xiàn)n 的；n整個(gè)博弈過(guò)程一直站在某一方的立場(chǎng)上，一切能使自n 己一方獲勝的結(jié)局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)是可解n 節(jié)點(diǎn)；一切使對(duì)方獲勝的結(jié)局都是不可解節(jié)點(diǎn)。4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n假定站在MAX方的立場(chǎng)：n可供本人選擇的行動(dòng)方案之間是“或的關(guān)系。n緣由是自動(dòng)權(quán)掌握在MAX手里，選擇哪個(gè)方案完全是由本人決議的。n可供MIN選擇的行動(dòng)方案之間那么是“與的關(guān)系。n緣由是自動(dòng)權(quán)掌握在MIN的手里，任何一個(gè)方案都有能夠被MIN選中。n

23、MAX必需防止那種對(duì)本人最為不利的情況的發(fā)生。4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n4.5.2 針對(duì)可窮舉搜索情況極大極小過(guò)程4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n4.5.3 固定深度的極大極小過(guò)程n對(duì)于某些情況，要生成整個(gè)搜索樹是不能夠的。一種可行的方法是用當(dāng)前正在調(diào)查的節(jié)點(diǎn)生成一棵部分博弈樹n-層預(yù)判n-ply look-ahead。n1利用估價(jià)函數(shù)f(n)對(duì)葉節(jié)點(diǎn)進(jìn)展靜態(tài)評(píng)價(jià)：n假設(shè)該節(jié)點(diǎn)對(duì)MAX有利，其估價(jià)函數(shù)取正值；n假設(shè)該節(jié)點(diǎn)對(duì)MIN有利，其估價(jià)函數(shù)取負(fù)值；n假設(shè)該節(jié)點(diǎn)對(duì)雙方有利，其估價(jià)函數(shù)取接近于0的值。n2計(jì)算非葉節(jié)點(diǎn)的值，必需從葉節(jié)點(diǎn)向上倒退n

24、MAX節(jié)點(diǎn)：其倒退值應(yīng)該取其后繼節(jié)點(diǎn)估值的最大值。nMIN節(jié)點(diǎn)：其倒推值應(yīng)該取其后繼節(jié)點(diǎn)估值的最小值。n3反復(fù)步驟2，直至求出初始節(jié)點(diǎn)的倒推值。4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索對(duì)假想形狀空間的對(duì)假想形狀空間的4層預(yù)判極小極大過(guò)程，葉子節(jié)點(diǎn)顯示了啟發(fā)值，內(nèi)部形狀顯示了向上傳播的值層預(yù)判極小極大過(guò)程，葉子節(jié)點(diǎn)顯示了啟發(fā)值，內(nèi)部形狀顯示了向上傳播的值4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n【例4.6】九宮游戲。n設(shè)MAX方的棋子用標(biāo)志，MIN方的棋子用標(biāo)志，并規(guī)定MAX方先走步。n解：n為了對(duì)葉節(jié)點(diǎn)進(jìn)展靜態(tài)估值，規(guī)定估價(jià)函數(shù)eP如下：n假設(shè) P是 MAX的必勝局，

25、那么 eP= + n假設(shè) P是 MIN的必勝局， 那么 eP= - n假設(shè)P對(duì)MAX、MIN都是勝負(fù)未定局，那么e(P)= e(+P)e(-P)ne+P：棋局 P上有能夠使成三子一線的數(shù)目。ne-P：棋局 P上有能夠使成三子一線的數(shù)目。n 一字棋棋盤一字棋棋盤4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索X有有6條能夠的勝利道路條能夠的勝利道路O有有5條能夠的勝利道路條能夠的勝利道路PPPX有有4條能夠的勝利道路條能夠的勝利道路O有有6條能夠的勝利道路條能夠的勝利道路X有有5條能夠的勝利道路條能夠的勝利道路O有有4條能夠的勝利道路條能夠的勝利道路運(yùn)用到九宮游戲開局挪動(dòng)的運(yùn)用到九宮游戲開局挪動(dòng)的2層預(yù)判極小極大過(guò)程層預(yù)判極小極大過(guò)程兩種能夠的兩種能夠的MAX第二步挪動(dòng)第二步挪動(dòng)對(duì)對(duì)X在接近結(jié)局的挪動(dòng)運(yùn)用極小極大過(guò)程在接近結(jié)局的挪動(dòng)運(yùn)用極小極大過(guò)程4.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n【例4.7】 0-33-3-3-21-36-30316011極大極小ab0 5 -33 3 -30 2 2 -3 0 -23 0 4 1-3-368 94.5 4.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索n4.5.4 -剪枝n極小極大過(guò)程性能分析：n極小極大過(guò)程需求對(duì)搜索空間進(jìn)展兩遍分析，第一遍是向下降到預(yù)判層并在那里運(yùn)用啟發(fā)評(píng)價(jià)，第