《搜索與或圖搜索》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當一個問題比較復(fù)雜時，直接進展求解往往比較困難。n可經(jīng)過歸約分解或變換，將它轉(zhuǎn)化為一系列較簡單的問題。n經(jīng)過對這些較簡單問題的求解來實現(xiàn)對原問題的求解。4.

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

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

4、點的子樹。n在解樹中一定包含初始節(jié)點。4.0 4.0 與或樹表示與或樹表示n【例4.1】三階梵塔問題。n解：n用三元組表示問題在任一時辰的形狀：(i,j,k)ni：代表金片C所在的鋼針號；nj: 代表金片B所在的鋼針號；nk; 代表金片A所在的鋼針號；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)三階梵塔問題的與或樹三階梵塔問題的與或樹n在該與/或樹中，有7個終止節(jié)點，它們分別對應(yīng)著7個本原問題。假設(shè)把這些本原問題從左至右陳列起來，即得到了原始問題的解：4.0 4.0

6、 與或樹表示與或樹表示目的目的目的目的初始節(jié)點初始節(jié)點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與/或樹的搜索過程實踐上是一個不斷尋覓解樹的過程。其普通搜索過程如下：n1把原始問題作為初始節(jié)點S0，并把它作為當前節(jié)n 點； n2

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

8、、祖父節(jié)點為可解節(jié)點的過程。n不可解標志過程n由不可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點為不可解節(jié)點的過程。4.1 4.1 與與/ /或樹的普通搜索或樹的普通搜索n搜索解樹的過程中，節(jié)點刪除戰(zhàn)略：n 假設(shè)搜索過程確定某個節(jié)點為可解節(jié)點，那么其不n 可解的后裔節(jié)點就可從搜索樹中刪去；n 假設(shè)搜索過程能確定某個節(jié)點為不可解節(jié)點，那么n 其后裔節(jié)點也可從搜索樹中刪去。內(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é)點S0 放人Open表中； n2把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點n 為n； n3假設(shè)節(jié)點n可擴展，那么做以下任務(wù)： n擴展節(jié)點n，將其子節(jié)點放入Open表的尾部，并為每一個子 n 節(jié)點設(shè)置指向父節(jié)點的指針； n調(diào)查這些子節(jié)點中能否有終止節(jié)點。假設(shè)有，那么標志這些終n 止節(jié)點為可解節(jié)點，并用可解標志過程對其父節(jié)點及先輩 n 節(jié)點中的可解節(jié)點進展標志。n假設(shè)初始

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

11、是終止節(jié)點，A 、 B 、 C為不可解的端節(jié)點為不可解的端節(jié)點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擴展節(jié)點擴展節(jié)點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é)點S0放入 Open表中； n2把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n n； n3假設(shè)節(jié)點n的深度等于dm，那么轉(zhuǎn)第5步的第n 點； n4假設(shè)節(jié)點n可擴展，那么做以下任務(wù)：n擴展節(jié)點 n，將其子節(jié)點放入 Open表的首部，并為每一n 個子節(jié)點設(shè)置指向父節(jié)點的指針； n調(diào)查這些子

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

14、么從Open表中刪去具有不可解先輩的節(jié)點； n轉(zhuǎn)第2步。4.3 4.3 與與/ /或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索n【例4.3】n對上例所給出的與或樹，假設(shè)按有解深度優(yōu)先搜索，且給定dm=4。n那么其擴展節(jié)點的順序為：1，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ā)式搜索過程是一種利用搜索過程所得到的啟發(fā)性信息尋覓最優(yōu)解樹的過程。對搜索的每一步，算法都試圖找到一個最有希望成為最優(yōu)解樹的子樹希望樹。n4.4.1 解樹的代價與希望樹n最優(yōu)解樹 n指代價最小的那棵解樹。4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n如何計算解樹的代價？目的目的目的目的初始節(jié)點初始節(jié)點abc4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n解樹的代價可按如下規(guī)那么計算：n1假設(shè)n為終止節(jié)點：n n2假設(shè)n為或節(jié)點，且子節(jié)點為n1，n2，nk， n n3假設(shè)n為與節(jié)點

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

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

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

19、解標志過程，對n的先輩節(jié)點中的一切不可解節(jié)點進展標志； n 假設(shè)初始節(jié)點S?？梢员粯酥緸椴豢山夤?jié)點，那么問題無解，失敗退出； n 否那么，從Open表中刪去具有不可解先輩的一切節(jié)點；n 轉(zhuǎn)第2步。4.4 4.4 與或樹的啟發(fā)式搜索與或樹的啟發(fā)式搜索n【例4.5】假設(shè)搜索過程每次擴展節(jié)點時都同擴展兩層，且按一層或節(jié)點、一層與節(jié)點的間隔方式進展擴展。887S0ADBCEF3332希望樹希望樹T : 擴展節(jié)點擴展節(jié)點 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機遇性博弈n存在不可預(yù)測性的博弈。n雙人完備

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

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

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

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

25、那么 eP= + n假設(shè) P是 MIN的必勝局， 那么 eP= - n假設(shè)P對MAX、MIN都是勝負未定局，那么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條能夠的勝利道路條能夠的勝利道路運用到九宮游戲開局挪動的運用到九宮游戲開局挪動的2層預(yù)判極小極大過程層預(yù)判極小極大過程兩種能夠的兩種能夠的MAX第二步挪動第二步挪動對對X在接近結(jié)局的挪動運用極小極大過程在接近結(jié)局的挪動運用極小極大過程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極小極大過程性能分析：n極小極大過程需求對搜索空間進展兩遍分析，第一遍是向下降到預(yù)判層并在那里運用啟發(fā)評價，第