前面討論的各種搜索方法都沒有用到問題本身的特性信息，只是按照事先設(shè)定的線路進行搜索，具有較大的盲目性。事實上，如果能夠利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程，則對搜索將是十分有益的。這種利用問題自身的特性信息來引導(dǎo)搜索過程的搜索方法稱為啟發(fā)式搜索。由于啟發(fā)式搜索方法具有較強的針對性，因此，可以縮小搜索范圍，提高搜索效率。4.5狀態(tài)空間的啟發(fā)式搜索

啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息，而啟發(fā)性信息又是通過估價函數(shù)作用到搜索過程中的。

1．啟發(fā)性信息一.啟發(fā)性信息和估價函數(shù)

啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進的控制信息。啟發(fā)性信息一般有以下三種：

①有效地幫助確定擴展節(jié)點的信息；

②有效地幫助決定哪些后繼節(jié)點應(yīng)被生成；

③能決定在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上被刪除。

一般來說，搜索過程所使用的啟發(fā)性信息的啟發(fā)能力越強，擴展的無用節(jié)點就越少。

2．估價函數(shù)用來估計節(jié)點重要性的函數(shù)稱為估價函數(shù)。估價函數(shù)f（n）被定義為從初始節(jié)點S0出發(fā)，經(jīng)過節(jié)點n到達(dá)目標(biāo)節(jié)點Sg的所有路徑中最小路徑代價的估計值。它的一般形式為

f（n）=g（n）＋h（n）

其中，g（n）是從初始節(jié)點S0到節(jié)點n的實際代價；h（n）是從節(jié)點n到目標(biāo)節(jié)點S0的最優(yōu)路徑的估計代價。對g（n）的值，可以按指向父節(jié)點的指針，從節(jié)點n反向跟蹤到初始節(jié)點S0,得到一條從初始節(jié)點S0到節(jié)點n的最小代價路徑，然后把這條路徑上所有有向邊的代價相加，就得到g（n）的值。對h（n）的值，則需要根據(jù)問題自身的特性來確定，它體現(xiàn)的是問題自身的啟發(fā)性信息，因此也稱h（n）為啟發(fā)函數(shù)。ng(n)h(n)例：八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如前所述，且估價函數(shù)為:f（n）=d（n）＋W（n）

其中，d（n）表示節(jié)點n在搜索樹中的深度；w（n）表示節(jié)點n中“不在位”的數(shù)碼個數(shù)。請計算初始狀態(tài)S0的估價函數(shù)值f（S0）。

解：在本例的估價函數(shù)中，取g（n）=d（n），h（n）=W（n）。它說明是用從S0到n的路徑上的單位代價表示實際代價，用n中“不在位”的數(shù)碼個數(shù)作為啟發(fā)信息。一般來說，某節(jié)點中的“不在位”的數(shù)碼個數(shù)越多，說明它離目標(biāo)節(jié)點越遠(yuǎn)。

對初始節(jié)點S0，由于d（S0）=0，W（S0）=3，因此有

f（S0）=0＋3=3

這個例子僅是為了說明估價函數(shù)的含義及估價函數(shù)值的計算。在問題搜索過程中，除了需要計算初始節(jié)點的估價函數(shù)之外，更多的是要計算新生成節(jié)點的估價函數(shù)值。

28314765二.A算法

在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f（n）=g（n）＋h（n）對Open表中的節(jié)點進行排序，則該搜索算法為A算法。由于估價函數(shù)中帶有問題自身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。

對啟發(fā)式搜索算法，又可根據(jù)搜索過程中選擇擴展節(jié)點的范圍，將其分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。每當(dāng)需要擴展節(jié)點時，總是從Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進行擴展。其搜索過程可描述如下：

（1）把S0放入Open表中，f(s0)=g（So）＋h（So）；

（2）如果Open表為空，則問題無解，失敗退出；

（3）把Open表的第一個節(jié)點取出放入Closed表，記該節(jié)點為n；

（4）考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則找到了問題的解，成功退出；

（5）若節(jié)點n不可擴展，則轉(zhuǎn)第（2）步；

（6）擴展節(jié)點n，生成其子節(jié)點ni（i=1,2,……），計算每一個子節(jié)點的估價值f(ni)（i=1,2,……），并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后將這些子節(jié)點放入Open表中；

（7）根據(jù)各節(jié)點的估價函數(shù)值，對Open表中的全部節(jié)點按從小到大的順序重新進行排序；

（8）轉(zhuǎn)第（2）步。

1．全局擇優(yōu)搜索由于上述算法的第（7）步要對Open表中的全部節(jié)點按其估價函數(shù)值從小到大重新進行排序，這樣在算法第（3）步取出的節(jié)點就一定是Open表的所有節(jié)點中估價函數(shù)值最小的一個節(jié)點。因此，它是一種全局擇優(yōu)的搜索方式。

對上述算法進一步分析還可以發(fā)現(xiàn)：如果取估價函數(shù)f(n)=g（n），則它將退化為代價樹的廣度優(yōu)先搜索；如果取估價函數(shù)f(n)=d（n），則它將退化為廣度優(yōu)先搜索?？梢?，廣度優(yōu)先搜索和代價樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個特例。例：八數(shù)碼難題。2834765S028314765238476528347652836475

8321476528371465

23847652384765

S9

4123847651238476512378465S5

5S66

S8

6

S7

4SgS10

4S11

6S1

4S2

4

S3

5S4

5在局部擇優(yōu)搜索中，每當(dāng)需要擴展節(jié)點時，總是從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進行擴展。其搜索過程可描述如下：（1）把初始節(jié)點S0放入Open表中，f(S0)=g(S0)+h(S0);（2）如果Open表為空，則問題無解，失敗退出；

（3）把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

（4）考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則找到了問題的解，成功退出；

（5）若節(jié)點n不可擴展，則轉(zhuǎn)第（2）步；

（6）擴展節(jié)點n，生成其子節(jié)點ni(i=1，2，…)，計算每一個子節(jié)點的估價值f（ni）（i=1，2，…），并按估價值從小到大的順序依次放入Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第（2）步。

2．局部擇優(yōu)搜索(瞎子爬山法)

由于這一算法的第（6）步僅是把剛生成的子節(jié)點按其估價函數(shù)值從小到大放入Open表的首都，這樣在算法第（3）步取出的節(jié)點僅是剛生成的子節(jié)點中估價函數(shù)值最小的一個節(jié)點。因此，它是一種局部擇優(yōu)的搜索方式。對這一算法進一步分析也可以發(fā)現(xiàn)：如果取估價函數(shù)f（n）=g（n），則它將退化為代價樹的深度優(yōu)先搜索；如果取估價函數(shù)f（n）=d（n），則它將退化為深度優(yōu)先搜索。可見，深度優(yōu)先搜索和代價樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個特例。三.A*算法前面討論論的啟發(fā)發(fā)式搜索索算法，，都沒有有對估價價函數(shù)f(n)作任何何限制。。實際上上，估價價函數(shù)對對搜索過過程是十十分重要要的，如如果選擇擇不當(dāng)，，則有可可能找不不到問題題的解，，或者找找到的不不是問題題的最優(yōu)優(yōu)解。為為此，需需要對估估價函數(shù)數(shù)進行某某些限制制。A*算法法就是對估價函函數(shù)加上上一些限制后得到的的一種啟啟發(fā)式搜搜索算法法。假設(shè)f*(n)為從初初始節(jié)點點S0出出發(fā)，約約束經(jīng)過過節(jié)點n到達(dá)目目標(biāo)節(jié)點點的最小小代價值值。估價價函數(shù)f(n)是f*(n)的估計計值。顯顯然，f*（n）應(yīng)由由以下兩兩部分所所組成：：一部分分是從初初始節(jié)點點到節(jié)點點n的最小代價，記記為g*（n））；另一一部分是是從節(jié)點點n到目目標(biāo)節(jié)點點的最小代價，記記為h*（n）），當(dāng)問問題有多多個目標(biāo)標(biāo)節(jié)點時時，應(yīng)取取其中代代價最小小的一個個。因此此有f*（n）＝g*（n）＋h*（n）把估價函函數(shù)f(n)與與f*(n)相相比，g（n））是對g*（n）的一一個估計計，h（（n）是是對h*（n））的一個個估計。。在這兩兩個估計計中，盡盡管g（（n）的的值容易易計算，，但它不不一定就就是從初初始節(jié)點點S0到到節(jié)點n的真正正最小代代價，很很有可能能從初始始節(jié)點S0到節(jié)節(jié)點n的的真正最最小代價價還沒有有找到，，故有g(shù)（n））≥g*（n））。有有了g*（n）和h*（n）的定定義，如如果對A算法（（全局擇擇優(yōu)的啟啟發(fā)式搜搜索算法法）中的的g（n）和h（n））分別提提出如下下限制：：第第一，，g（n）是對對g*（（n）的的估計，，且g（（n）＞＞0；第第二，h（n））是h*（n））的下界界，即對對任意節(jié)節(jié)點n均均有h（n））≤h*（n））。

則稱稱得到的的算法為為A*算算法。。A*算法法的有關(guān)關(guān)特性。。1．A*算法的的可納性性一般來說說，對任任意一個個狀態(tài)空空間圖，，當(dāng)從初初始節(jié)點點到目標(biāo)標(biāo)節(jié)點有有路徑存存在時，，如果搜搜索算法法能在有有限步內(nèi)內(nèi)找到一一條從初初始節(jié)點點到目標(biāo)標(biāo)節(jié)點的的最佳路路徑，并并在此路路徑上結(jié)結(jié)束，則則稱該搜搜索算法法是可采采納的。。A*算算法是可可采納的的。(證明略略）。2.A*算法的的最優(yōu)性性A*算算法的搜搜索效率率很大程程度上取取決于估估價函數(shù)數(shù)h（n）。一一般來說說，在滿滿足h（（n）≤≤h*（（n）的的前提下下，h（（n）的的值越大大越好。。h（n）的值值越大，，說明它它攜帶的的啟發(fā)性性信息越越多，A*算算法搜索索時擴展展的節(jié)點點就越少少，搜索索效率就就越高。。A*算算法的這這一特性性也稱為為信息性性。(證證明略)A*算法應(yīng)用用舉例例例：八數(shù)碼難難題。問問題的初初始狀態(tài)態(tài)和目標(biāo)標(biāo)狀態(tài)和和前例相相同。要要求用A*算算法解決決該問題題。解：在上例中中，我們們?nèi)（（n）=W（n）。盡盡管我們們對h*（n））不能確確切知道道，但當(dāng)當(dāng)采用單單位代價價時，通通過對““不在位位”數(shù)碼碼個數(shù)的的估計，，可以得得出至少少要移動動W（n）步才才能到達(dá)達(dá)目標(biāo)，，顯然有有W（n）≤h*（n）。因因此，前前例中所所定義的的h（n）滿足足A*算算法的限限制條件件。這這里里再取另另外一種種啟發(fā)函函數(shù)h（（n）=P（n），P（n））定義為為每一個個數(shù)碼與與其目標(biāo)標(biāo)位置之之間距離離（不考考慮夾在在其間的的數(shù)碼））的總和和，同樣樣可以斷斷定至少少要移動動P（n）步才才能到達(dá)達(dá)目標(biāo)，，因此有有P（n）≤h*（n），即即滿足A*算法法的限制制條件。。23847655238476128314765h*=4,f=4S0231

8476528316475283

1476528314765g*=1

2318476523184765g*=21

23847651

2378465Sgg*=4h*=5,f=6h*=5,f=6h*=3,f=4h*=5,f=6h*=2,f=4h*=4,f=61

2384765g*=3h*=1,f=4h*=0,f=4h*=1,f=6八數(shù)碼難題h（n）=P（n）的搜索樹例：設(shè)有如如下結(jié)構(gòu)構(gòu)的移動動將牌游游戲B代表黑黑色牌，，W代表表白色牌牌；E代代表該位位置為空空。玩法法：當(dāng)一個牌牌移入相相鄰的空空位時，，費用等等于挑過過的牌數(shù)數(shù)加1。。一個牌至至多可跳跳過兩個個牌進入入空位置置，其費費用等于于跳過的的牌數(shù)加加1。要求把所所有的B都移到到所有的的W的右右邊，設(shè)設(shè)計h(x)。。解：顯然W左左邊的B越少越越接近目目標(biāo)，因因此可用用W左邊邊B的個個數(shù)作為為h(x)h(x)=3*(每個個W左邊邊B個數(shù)數(shù)的總和和）h(x)=3*(2+2+3)=21BBBWWWEBBBWWWE例：傳教士和和野人問問題。請請用A*算法解解決該問問題。解：用m表示示左岸的的傳道士士人數(shù)，，c表示示左岸的的野人數(shù)數(shù)，b表表示左岸岸的船數(shù)數(shù)，用三三元組（（m，c，b））表示問問題的狀狀態(tài)。對對A*算法，，首先需需要確定定估價函函數(shù)。設(shè)設(shè)g（n））=d（（n），，h（n）=m＋c－－2b，，則則有有f（（n）=g（n）＋h（n））=d（（n）＋＋m＋c－2b

其中中，d（（n）為為節(jié)點的的深度。。通過分分析可知知h（n）＜h*(n)，滿滿足A*算法的的限制條條件。M-C問問題的的搜索過過程如下下頁圖所所示。在在該圖中中，每個個節(jié)點旁旁邊還標(biāo)標(biāo)出了該該節(jié)點的的h值和和f值。。(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問題的搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)4.4與/或樹的盲目目搜索概念:直接可解的簡簡單問題稱為為本原問題，，本原問題題對應(yīng)的節(jié)點點稱為終止節(jié)節(jié)點，在與或或圖（樹）中中無子節(jié)點的的節(jié)點稱為端端節(jié)點，一一個節(jié)點的子子節(jié)點如果是是“與”關(guān)系系，則該節(jié)點點便稱為與節(jié)節(jié)點，一個節(jié)節(jié)點的子節(jié)點點如果是“或或”關(guān)系，則則該節(jié)點便稱稱為或節(jié)點。。注意，終止止節(jié)點一定是是端節(jié)點，但但端節(jié)點不一一定是終止節(jié)節(jié)點?？山庑耘袆e(1)一個節(jié)節(jié)點是可解，，則節(jié)點須滿滿足下列條件件之一:①終止節(jié)點是是可解節(jié)點；；②一個與節(jié)點點可解，當(dāng)且且僅當(dāng)其子節(jié)節(jié)點全都可解解；③一個或節(jié)點點可解，只要要其子節(jié)點至至少有一個可可解。(2)一個節(jié)節(jié)點是不可解解，則節(jié)點須須滿足下列條條件之一:①非終止節(jié)點點的端節(jié)點是是不可解節(jié)點點；②一個與節(jié)點點不可解，只只要其子節(jié)點點至少有一個個不可解；③一個或節(jié)點點不可解，當(dāng)當(dāng)且僅當(dāng)其子子節(jié)點全都不不可解。一.與/或或樹的一般搜搜索與/或樹的搜搜索過程實際際上是一個不不斷尋找解樹的過程。其一一般搜索過程程如下：（1）把原始問題作作為初始節(jié)點點S0，并把把它作為當(dāng)前前節(jié)點；（2）應(yīng)用分解或等價變換操作對當(dāng)前節(jié)節(jié)點進行擴展展；（3）為每個子節(jié)點點設(shè)置指向父父節(jié)點的指針針；（4）選擇合適的子子節(jié)點作為當(dāng)當(dāng)前節(jié)點，反反復(fù)執(zhí)行第（（2）步和第第（3）步，，在此期間需需要多次調(diào)用用可解標(biāo)記過程程或不可解標(biāo)記過過程，直到初始節(jié)節(jié)點被標(biāo)記為為可解節(jié)點或不不可解節(jié)點為止。上上述搜搜索過程將形形成一棵與/或樹，這種種由搜索過程程形成的與/或樹稱為搜索樹。當(dāng)搜索成功功時，經(jīng)可解解標(biāo)記過程標(biāo)標(biāo)識的由初始始節(jié)點及其下下屬的可解節(jié)節(jié)點構(gòu)成的子子樹稱為解樹。用與/或樹法法表示的問題題求解過程與與狀態(tài)空間法法類似，也是是通過搜索來來實現(xiàn)對問題題求解的。與與/或樹的搜搜索策略也分分為盲目搜索和啟發(fā)式搜索兩大類。搜索過程中的的可解標(biāo)記過程程與不可解標(biāo)標(biāo)記過程都是自下而上上進行的，即即由子節(jié)點的的可解性確定定父節(jié)點、祖祖父節(jié)點的可可解性；由子子節(jié)點的不可可解性確定父父節(jié)點、祖父父節(jié)點的不可可解性。在與與/或樹中，，除端節(jié)點和和終止節(jié)點外外，一個節(jié)點點的可解性完完全是由其子子節(jié)點來決定定的。對與節(jié)節(jié)點，只有其其所有子節(jié)點點都為可解時時它才為可解解，只要有一一個子節(jié)點不不可解它就是是不可解的；；對或節(jié)點，，只要有一個個子節(jié)點可解解它就是可解解的，僅當(dāng)所所有子節(jié)點都都是不可解時時它才為不可可解。這種由由可解子節(jié)點點來確定其父父節(jié)點、祖父父節(jié)點為可解解節(jié)點的過程程稱為可解標(biāo)記過程程；由不可解子子節(jié)點來確定定其父節(jié)點、、祖父節(jié)點為為不可解節(jié)點點的過程稱為為不可解標(biāo)記過過程。由由于與/或樹樹搜索的目標(biāo)標(biāo)是尋找解樹，因此，如果果搜索過程確確定某個節(jié)點點為可解節(jié)點點，則其不不可解的后裔裔節(jié)點就可從從搜索樹中刪刪去；同樣，，如果搜索過過程能確定某某個節(jié)點為不不可解節(jié)點，，則其后裔節(jié)節(jié)點也可從搜搜索樹中刪去去。與狀態(tài)空間的的廣度優(yōu)先搜搜索類似，只只是在搜索過過程中需要多多次調(diào)用可解解標(biāo)記過程或或不可解標(biāo)記記過程，其搜搜索算法如下下：（1）把初始節(jié)點S0放人Open表中中；（2）把Open表表的第一個節(jié)節(jié)點取出放入入Closed表，并記記該節(jié)點為n；（3）如果節(jié)點n可可擴展，則做做下列工作：：①擴展節(jié)點n，，將其子節(jié)點點放入Open表的尾部部，并為每一一個子節(jié)點設(shè)設(shè)置指向父節(jié)節(jié)點的指針；；②考察這些子節(jié)節(jié)點中是否有有終止節(jié)點。。若有，則標(biāo)標(biāo)記這些終止止節(jié)點為可解解節(jié)點，并用用可解標(biāo)記過過程對其父節(jié)節(jié)點及先輩節(jié)節(jié)點中的可解解節(jié)點進行標(biāo)標(biāo)記。如果初初始解節(jié)點S0能夠被標(biāo)標(biāo)記為可解節(jié)節(jié)點，就得到到了解樹，搜搜索成功，退退出搜索過程程；如果不能能確定S0為為可解節(jié)點，，則從Open表中刪去去具有可解先先輩的節(jié)點；；③轉(zhuǎn)第（2）步步。二.與/或或樹的廣度優(yōu)優(yōu)先搜索（4）如果節(jié)點n不不可擴展，則則做下列工作作：①標(biāo)記節(jié)點n為為不可解節(jié)點點；②應(yīng)用不可解標(biāo)標(biāo)記過程對節(jié)節(jié)點n的先輩輩中不可解的的節(jié)點進行標(biāo)標(biāo)記。如果初初始解節(jié)點S0也被標(biāo)記記為不可解節(jié)節(jié)點，則搜索索失敗，表明明原始問題無無解，退出搜搜索過程；如如果不能確定定S0為不可可解節(jié)點，則則從Open表中刪去具具有不可解先先輩的節(jié)點；；③轉(zhuǎn)第（2）步步。例：設(shè)有如下圖所所示的與/或或樹，節(jié)點按按圖中所標(biāo)注注的順序號進進行擴展，其其中標(biāo)有t1、t2、t3的節(jié)點是是終止節(jié)點，，A、B、C為為不可解的端端節(jié)點。

與/或樹的廣度優(yōu)先搜索123A4t1t3CBt25搜索過程為：（1）先擴展1號節(jié)點，，生成2號節(jié)點和3號節(jié)點，，由于這兩兩個子節(jié)點都都不是終止節(jié)節(jié)點，因此接接著擴展2號號節(jié)點。（2）擴展2號節(jié)點點，生成A節(jié)節(jié)點和4號節(jié)節(jié)點。由于這這兩個子節(jié)點點均不是終止止節(jié)點，因此此接著擴展3號節(jié)點。（3）擴展3號節(jié)點點，生成t1節(jié)點和5號號節(jié)點。由于于t1為終止止節(jié)點，則標(biāo)標(biāo)記它為可解解節(jié)點，并應(yīng)應(yīng)用可解標(biāo)記記過程，對其其先輩中的可可解節(jié)點進行行標(biāo)記，由于于t1的父節(jié)節(jié)點是一個與與節(jié)點，因此此不能確定3號節(jié)點是是否可解。（4）擴展節(jié)點A，，由于A是端端節(jié)點，調(diào)用用不可解標(biāo)記記過程，由于于2號節(jié)點是是或節(jié)點，因因此不能確定定2號節(jié)點是是不可解節(jié)點點。（5）擴展4號節(jié)點點，生成t2節(jié)點和B節(jié)節(jié)點。由于t2為終止節(jié)節(jié)點，則標(biāo)記記它為可解節(jié)節(jié)點，并應(yīng)用用可解標(biāo)記過過程，標(biāo)記4號節(jié)點為可可解節(jié)點，標(biāo)標(biāo)記2號節(jié)點點為可解節(jié)點點，但不能標(biāo)標(biāo)記1號節(jié)點點為可解節(jié)點點。（6）擴展5號節(jié)節(jié)點，生成成t3節(jié)點點和C節(jié)點點。由于t3為終止止節(jié)點，標(biāo)標(biāo)記它為可可解節(jié)點，，并應(yīng)用可可解標(biāo)記過過程，標(biāo)記記5號節(jié)點點為可解節(jié)節(jié)點，標(biāo)記記3號節(jié)點點為可解節(jié)節(jié)點。標(biāo)記記1號節(jié)點點為可解節(jié)節(jié)點。（7）搜索成功，得到由1、2、3、4、5號節(jié)點及及t1、t2、t3節(jié)點構(gòu)成成的解樹。。該解樹如如上圖中的的粗線所示示?？梢詭в猩钌疃认拗芼m，其搜搜索算法如如下：（1）把初始節(jié)點點S0放入入Open表中中；（2）把Open表的第一一個節(jié)點取取出放入Closed表，并并記該節(jié)點點為n；（3）如果節(jié)點n的深度等等于dm，，則轉(zhuǎn)第（（5）步的的第①點；；（4）如果節(jié)點n可擴展，，則做下列列工作：①擴展節(jié)點n，將其其子節(jié)點放放入Open表的的首部，并并為每一個個子節(jié)點設(shè)設(shè)置指向父父節(jié)點的指指針；②考察這些子子節(jié)點中是是否有終止止節(jié)點。若若有，則標(biāo)標(biāo)記這些終終止節(jié)點為為可解節(jié)點點，并用可可解標(biāo)記過過程對其父父節(jié)點及先先輩節(jié)點中中的可解節(jié)節(jié)點進行標(biāo)標(biāo)記。如果果初始節(jié)點點S0能夠夠被標(biāo)記為為可解節(jié)點點，就得到到了解樹，，搜索成功功，退出搜搜索過程；；如果不能能確定S0為可解節(jié)節(jié)點，則從從Open表中刪去去具有可解解先輩的節(jié)節(jié)點；③轉(zhuǎn)第（2））步。三.與/或樹的深深度優(yōu)先搜搜索（5）如果節(jié)點n不可擴展展，則做下下列工作：：①標(biāo)記節(jié)點n為不可解解節(jié)點；②應(yīng)用不可解解標(biāo)記過程程對節(jié)點n的先輩中中不可解的的節(jié)點進行行標(biāo)記。如如果初始節(jié)節(jié)點S0也也被標(biāo)記為為不可解節(jié)節(jié)點，則搜搜索失敗，，表明原始始問題無解解，退出搜搜索過程；；如果不能能確定為不不可解節(jié)點點，則從Open表中刪刪去具有不不可解先輩輩的節(jié)點；；③轉(zhuǎn)第（2））步。

與/或樹的深度優(yōu)先搜索123A4t1t3CBt25例如，對上上例所給出出的與／或或樹，若按按有界深度度優(yōu)先搜索索，且給定定dm=4，則其擴擴展節(jié)點的的順序為：：1，，3，5，，2，4其其解樹與與上例相同同。與/或樹的的盲目搜索索是按確定定路線進行行的，當(dāng)要要選擇一個個節(jié)點進行行擴展時，，只是根據(jù)據(jù)節(jié)點在與與/或樹中中所處的位位置，而沒沒有考慮要要付出的代代價，因而而求得的解解樹不一定定是代價最最小的解樹樹，即不一一定是最優(yōu)優(yōu)解樹。因因此，需要要考慮與/或樹的啟啟發(fā)式搜索索。在討論論與／或樹樹的啟發(fā)式式搜索過程程之前，需需要先討論論幾個有關(guān)關(guān)的概念。。一.解樹樹的代價與與希望樹與／或樹的的啟發(fā)式搜搜索過程是是一種利用用搜索過程程所得到的的啟發(fā)性信信息尋找最最優(yōu)解樹的的過程。對對搜索的每每一步，算算法都試圖圖找到一個個最有希望望成為最優(yōu)優(yōu)解樹的子子樹。最優(yōu)優(yōu)解樹是指指代價最小小的那棵解解樹。4.5與與/或或樹樹的的啟啟發(fā)發(fā)式式搜搜索索1．．解解樹樹的的代代價價在與與/或或樹樹的的啟啟發(fā)發(fā)式式搜搜索索過過程程中中，，解解樹樹的的代代價價可可按按如如下下規(guī)規(guī)則則計計算算：：（1））若n為為終終止止節(jié)節(jié)點點，，則則其其代代價價h（（n））=0。。（2））若n為為或或節(jié)節(jié)點點，，且且子子節(jié)節(jié)點點為為n1，，n2，，……，，nk，，則則n的的代代價價為為h（（n））=min{c（（n，，ni））＋＋h（（ni））}(1≤≤i≤≤k)其中中，，c（（n，，ni））是是節(jié)節(jié)點點n到到其其子子節(jié)節(jié)點點ni的的邊邊代代價價。。（3））若n為為與與節(jié)節(jié)點點，，且且子子節(jié)節(jié)點點為為n1，，n2，，……，，nk，，則則n的的代代價價可可用用和和代代價價法法或或最最大大代代價價法法。。若若用用和和代代價價法法，，則則其其計計算算公公式式為為：：h（（n））=ΣΣ((c(n，，ni)＋＋h(ni))i=1,2,…………,k若若用用最最大大代代價價法法，，則則其其計計算算公公式式為為：：h（（n））=max｛｛c（（n，，ni））＋＋h（（ni））｝｝(1≤≤i≤≤k)（4））若n是是端端節(jié)節(jié)點點，，但但又又不不是是終終止止節(jié)節(jié)點點，，則則n不不可可擴擴展展，，其其代代價價定定義義為為h（（n））=∞∞（5））根節(jié)節(jié)點點的的代代價價即即為為解解樹樹的的代代價價。。例：：設(shè)右右圖圖是是一一棵棵與與/或或樹樹，，其其中中包包括括兩兩棵棵解解樹樹，，左左邊邊的的解解樹樹由由S0、、A、、t1、、C及及t3組組成成；；右右邊邊的的解解樹樹由由S0、、B、、t2、、D及及t4組組成成。。在在此此與與/或或樹樹中中，，t1、、t2、、t3、、t4為為終終止止節(jié)節(jié)點點；；E、、F是是端端節(jié)節(jié)點點；；邊邊上上的的數(shù)數(shù)字字是是該該邊邊的的代代價價。。請請計計算算解解樹樹的的代代價價。。S0ABt1Ct3Et2Dt4F與／或樹的代價22463521解：先計算左邊邊的解樹按按和代價價：h（S0）=2＋4＋6＋2=14按按最大代價價：h（S0）=8＋2=10再再計計算右邊的解解樹按按和代價：h（S0））=1＋5＋3＋＋2=11按按最大代價：：h（S0））=6＋2=8在在本例中中，無論按和和代價還是最最大代價，右右邊的解樹都都是最優(yōu)解樹樹。但在有些些情況下，當(dāng)當(dāng)采用的代價價法不同時，，找到的最優(yōu)優(yōu)解樹有可能能不同。2．希望樹為了找到最優(yōu)優(yōu)解樹，搜索索過程的任何何時刻都應(yīng)該該選擇那些最最有希望成為為最優(yōu)解樹一一部分的節(jié)點點進行擴展。。由于這些節(jié)節(jié)點及其父節(jié)節(jié)點所構(gòu)成的的與/或樹最最有可能成為為最優(yōu)解樹的的一部分，因因此稱它為希希望解樹，也也簡稱為希望樹。需要注意，，希望解樹是是會隨搜索過過程而不斷變變化的。定義：希望解樹T（（1）初始節(jié)節(jié)點S0在希希望樹T中；；（（2）如果果n是具有子子節(jié)點n1，，n2，…，，nk的或節(jié)點，則n的某個個子節(jié)點ni在希望樹T中的充分必必要條件是h（（n）=min{c（n，ni）＋h（（ni）}1≤i≤k（3）如果n是與節(jié)點，則n的全部部子節(jié)點都在在希望樹T中中。與／或樹的啟啟發(fā)式搜索需需要不斷地選選擇、修正希希望樹，其搜搜索過程如下下：（1）把初始節(jié)點S0放入Open表中，，計算h（S0）；（2）計算希望樹T；（3）依次在Open表中取出出T的端節(jié)點點放入Closed表，，記節(jié)點為n；（4）如果節(jié)點n為為終止節(jié)點，，則做下列工工作：①標(biāo)記節(jié)點n為為可解節(jié)點；；②在T上應(yīng)用可可解標(biāo)記過程程，對n的先先輩節(jié)點中的的所有可解節(jié)節(jié)點進行標(biāo)記記；③如果初始節(jié)點點S0能夠被被標(biāo)記為可解解節(jié)點，則T就是最優(yōu)解解樹，成功退退出；④否則，從Open表中刪刪去具有可解解先輩的所有有節(jié)點；⑤轉(zhuǎn)第（2）步步。二.與/或或樹的啟發(fā)式式搜索過程（5）如果節(jié)點n不不是終止節(jié)點點，但可擴展展，則做下列列工作：①擴展節(jié)點n，，生成n的所所有子節(jié)點；；②把這些子節(jié)點點都放入Open表中中，并為每一一個子節(jié)點設(shè)設(shè)置指向父節(jié)節(jié)點n的指指針；③計算這些子節(jié)節(jié)點及其先輩輩節(jié)點的h值值；④轉(zhuǎn)第（2）步步。（6）如果節(jié)點n不不是終止節(jié)點點，且不可擴擴展，則做下下列工作：①標(biāo)記節(jié)點n為為不可解節(jié)點點；②在T上應(yīng)用不不可解標(biāo)記過過程，對n的的先輩節(jié)點中中的所有不可可解節(jié)點進行行標(biāo)記；③如果初始節(jié)點點S0能夠被被標(biāo)記為不可可解節(jié)點，則則問題無解，，失敗退出；；④否則，從Open表表中刪去具有有不可解先輩輩的所有節(jié)點點；⑤轉(zhuǎn)第（（2））步。。例，搜搜索過過程每每次擴擴展節(jié)節(jié)點時時都都同時時擴展展兩層層，且且按一一層或或節(jié)點點、一一層與與節(jié)點點的間間隔方方式進進行擴擴展。。設(shè)初始始節(jié)點點為S0，，對S0擴擴展后后得到到的與與/或或樹如如下圖圖所示示。其其中，，端節(jié)節(jié)點B、C、E、F下面面的數(shù)數(shù)字是是用啟啟發(fā)函函數(shù)估估算出出的h值，，節(jié)點點A、、D旁旁邊的的數(shù)字字是按按和代代價法法計算算出來來的節(jié)節(jié)點代代價。。此時時，S0的的右子子樹是是當(dāng)前前的希希望樹樹，下下面對對其端端節(jié)點點進行行擴展展。S0ADBCEF873332擴展S0后后的與與／或或樹8擴展節(jié)節(jié)點E，，由右右子樹樹求出出的h（S0））=12，，而由由左子子樹求求出的的h（（S0）=9。。故當(dāng)當(dāng)前的的希望望樹應(yīng)應(yīng)改為為左子子樹。。對B擴擴展兩兩層。。由于于H和和I是是可解解節(jié)點點，調(diào)調(diào)用可可解標(biāo)標(biāo)記過過程，，得節(jié)節(jié)點G、B也為為可解解節(jié)點點，但但不能能標(biāo)記記S0為可可解節(jié)節(jié)點，，須繼繼續(xù)擴擴展。。當(dāng)前前的希希望樹樹仍然然是左左子樹樹。對對C擴擴展。。擴展展兩層層后得得到的的與／／或樹樹如圖圖3所所示。。S0ADBCEF8332

3222776119圖1擴擴展E后的的與／／或樹樹S0ADBCEF8332

3222776119GKHILJ002226圖2擴擴展展B后后的與與／或或樹S0DEFABC8332

3222776119IGKHLJ002226MNP005229圖3擴展C后的與／或樹9由于N和P是可可解節(jié)節(jié)點，，調(diào)用用可解解標(biāo)記記過程程，得得節(jié)點點M、、C、、A也也為可可解節(jié)節(jié)點，，進而而S0為可可解節(jié)節(jié)點。。求出出了代代價最最小的的解樹樹，即即最優(yōu)優(yōu)解樹樹，如如圖中中粗線線所示示。按按和代代價法法，該該最優(yōu)優(yōu)解樹樹的代代價為為9。。博弈是一類類富有有智能能行為為的競競爭活活動，，如下下棋、、打牌牌、戰(zhàn)戰(zhàn)爭等等。博博弈可可分為為雙人完完備信信息博博弈和機遇性性博弈弈。所謂謂雙人完完備信信息博博弈，就是是兩位位選手手對壘壘，輪輪流走走步，，每一一方不不僅知知道對對方已已經(jīng)走走過的的棋步步，而而且還還能估估計出出對方方未來來的走走步。。對弈弈的結(jié)結(jié)果是是一方方贏，，另一一方輸輸；或或者雙雙方和和局。。所謂謂機遇性性博弈弈，是指指存在在不可可預(yù)測測性的的博弈弈，例例如擲擲幣等等。對對機遇遇性博博弈，，由于于不具具備完完備信信息，，因此此不作作討論論。假設(shè)博博弈的的一方方為MAX，另一一方為為MIN。在博博弈過過程的的每一一步，，可供供MAX和和MIN選選擇的的行動動方案案都可可能有有多種種。從從MAX方方的觀觀點看看，可可供自自己選選擇的的那些些行動動方案案之間間是““或”的關(guān)關(guān)系，，選擇擇哪個個方案案完全全是由由自己己決定定的；；而對對那些些可供供MIN選選擇的的行動動方案案之間間則是是“與”的關(guān)關(guān)系，，主動動權(quán)掌掌握在在MIN的的手里里，任任何一一個方方案都都有可可能被被MIN選選中，，MAX必必須防防止那那種對對自己己最為為不利利的情情況的的發(fā)生生。4.6博博弈樹樹的啟啟發(fā)式式搜索索一.概概述述若把雙雙人完完備信信息博博弈過過程用用圖表表示出出來，，就可可得到到一棵棵與/或樹樹，這這種與與/或或樹被被稱為為博弈樹樹。在博博弈樹樹中，，那些些下一一步該該MAX走走步的的節(jié)點點稱為為MAX節(jié)點點，而下下一步步該MIN走步步的節(jié)節(jié)點稱稱為MIN節(jié)點點。博弈弈樹具具有如如下特特點：：（l））博弈弈的初初始狀狀態(tài)是是初始始節(jié)點點；（2））博弈弈樹中中的““或””節(jié)點點和““與””節(jié)點點是逐逐層交交替出出現(xiàn)的的；（3））整個個博弈弈過程程始終終站在在某一一方的的立場場上，對簡單單的博博弈問問題，，可以以生成成整個個博弈弈樹，，找到到必勝勝的策策略。。但對對于復(fù)復(fù)雜的的博弈弈，如如國際際象棋棋，大大約有有10120個節(jié)點，，要生成成整個搜搜索樹是是不可能能的。一一種可行行的方法法是用當(dāng)當(dāng)前正在在考察的的節(jié)點生生成一棵棵部分博弈弈樹，由于該該博弈樹樹的葉二.極極大極小小過程為了計算算非葉節(jié)節(jié)點的值值，必須須從葉節(jié)節(jié)點向上上倒推。。對于MAX節(jié)節(jié)點，由由于MAX方方總是選選擇估值值最大的的走步，，因此，，MAX節(jié)點的的倒推值值應(yīng)該取取其后繼繼節(jié)點估估值的最大值。對于MIN節(jié)節(jié)點，由由于MIN方總總是選擇擇使估值值最小的的走步，，因此MIN節(jié)節(jié)點的倒倒推值應(yīng)應(yīng)取其后后繼節(jié)點點估值的的最小值。這樣一一步一步步的計算算倒推值值，直至至求出初初始節(jié)點點的倒推推值為止止。這一一過程稱稱為極大極小小過程。例：一字棋游游戲。設(shè)設(shè)有一個個三行三三列的棋棋盤，如如下圖所所示，兩兩個棋手手輪流走走步，每每個棋手手走步時時往空格格上擺一一個自己己的棋子子，誰先先使自己己的棋子子成三子子一線為為贏。設(shè)設(shè)MAX方的棋棋子用×標(biāo)記，MIN方一字棋棋盤若P對MAX、、MIN都是勝勝負(fù)未定定局，則則e（P））=e（+P）－e（-P）其其中，e（+P）表示示棋局P上有有可能使使×成三子一一線的數(shù)數(shù)目；e（-P）表示示棋局P上有有可能使使○成三子一一線的數(shù)數(shù)目。例如，對對圖1所所示的棋棋局有估估價函數(shù)數(shù)值e（P）＝6-4＝＝2圖1棋局1在搜索過過程中，，具有對對稱性的的棋局認(rèn)認(rèn)為是同同一棋局局。例如如，圖2所示的的棋局可可以認(rèn)為為是同一一個棋局局，這圖2對稱棋局的例子圖3一一子棋棋的極大大極小搜搜索S0S1S2S3S4S5-11-26-5=15-5=06-5=15-5=04-5=-15-6=-15-5=06-6=05-6=-14-6=-25-4=16-4=2極大極小小值算法法FunctionMAX-MIN-DECISION(state)returnsanactioninputs:state(currentstateingame)v←MAX-VALUE(state)returntheactioninSUCCESSORS(state)withvaluevFunctionMAX-VALUE(state)returnsautilityvalueifTERMINAL-TEST(state)thenreturnUTILITY(state)v←-∞fora,sinSUCCESSORS(state)dov←←MAX(v,MIN-VALUE(s))returnv(a=action招招數(shù))FunctionMIN-VALUE(state)returnsautilityvalueifTERMINAL-TEST(state)thenreturnUTILITY(state)v←+∞fora,sinSUCCESSORS(state)dov←←MIN(v,MAX-VALUE(s))returnv三.αα-β剪剪枝<=23S0DEFABC5332對于一個或節(jié)點來說，它取當(dāng)前子節(jié)點中的最大倒推值作為它倒推值的下界，稱該值為α

值。α-β剪剪枝的方方法如下下：（1）MAX節(jié)節(jié)點的αα值為當(dāng)當(dāng)前子節(jié)節(jié)點的最最大倒推推值；（2）MIN節(jié)節(jié)點的的β值為為當(dāng)前子子節(jié)點的的最小倒倒推值；；（3）α-β剪剪枝