級人工智能原理課件

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

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

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

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

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

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

③能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上被刪除。

一般來說，搜索過程所使用的啟發(fā)性信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無用節(jié)點(diǎn)就越少。2啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息2

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

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

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

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

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

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

f（S0）=0＋3=3

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

283147654例：八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如前4二.A算法

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

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

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

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

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

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

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

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

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

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

1．全局擇優(yōu)搜索6每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí)，總是從Open表的所有節(jié)點(diǎn)中選擇6由于上述算法的第（7）步要對Open表中的全部節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大重新進(jìn)行排序，這樣在算法第（3）步取出的節(jié)點(diǎn)就一定是Open表的所有節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此，它是一種全局擇優(yōu)的搜索方式。

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

8321476528371465

23847652384765

S9

4123847651238476512378465S5

5S66

S8

6

S7

4SgS10

4S11

6S1

4S2

4

S3

5S4

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

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

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

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

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

2．局部擇優(yōu)搜索(瞎子爬山法)9在局部擇優(yōu)搜索中，每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí)，總是從9

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

f*（n）＝g*（n）＋h*（n）

把估價(jià)函數(shù)f(n)與f*(n)相比，g（n）是對g*（n）的一個(gè)估計(jì)，h（n）是對h*（n）的一個(gè)估計(jì)。在這兩個(gè)估計(jì)中，盡管g（n）的值容易計(jì)算，但它不一定就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià)，很有可能從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià)還沒有找到，故有g(shù)（n）≥g*（n）。

有了g*（n）和h*（n）的定義，如果對A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的g（n）和h（n）分別提出如下限制：

第一，g（n）是對g*（n）的估計(jì)，且g（n）＞0；

第二，h（n）是h*（n）的下界，即對任意節(jié)點(diǎn)n均有

h（n）≤h*（n）。

則稱得到的算法為A*算法。12假設(shè)f*(n)為從初始節(jié)點(diǎn)S0出發(fā)，約束經(jīng)過12A*算法的有關(guān)特性。

1．A*算法的可納性

一般來說，對任意一個(gè)狀態(tài)空間圖，當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在時(shí)，如果搜索算法能在有限步內(nèi)找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。A*算法是可采納的。(證明略）。

2.A*算法的最優(yōu)性

A*算法的搜索效率很大程度上取決于估價(jià)函數(shù)h（n）。一般來說，在滿足h（n）≤h*（n）的前提下，h（n）的值越大越好。h（n）的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少，搜索效率就越高。A*算法的這一特性也稱為信息性。(證明略)13A*算法的有關(guān)特性。

1313A*算法應(yīng)用舉例

例：八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀態(tài)和前例相同。要求用A*算法解決該問題。

解：在上例中，我們?nèi)（n）=W（n）。盡管我們對h*（n）不能確切知道，但當(dāng)采用單位代價(jià)時(shí)，通過對“不在位”數(shù)碼個(gè)數(shù)的估計(jì)，可以得出至少要移動W（n）步才能到達(dá)目標(biāo)，顯然有W（n）≤h*（n）。因此，前例中所定義的h（n）滿足A*算法的限制條件。

這里再取另外一種啟發(fā)函數(shù)h（n）=P（n），P（n）定義為每一個(gè)數(shù)碼與其目標(biāo)位置之間距離（不考慮夾在其間的數(shù)碼）的總和，同樣可以斷定至少要移動P（n）步才能到達(dá)目標(biāo)，因此有P（n）≤h*（n），即滿足A*算法的限制條件。

23847655238476114A*算法應(yīng)用舉例

例：八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀1428314765h*=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）的搜索樹15283h*=4,f=4S0232832815例：設(shè)有如下結(jié)構(gòu)的移動將牌游戲B代表黑色牌，W代表白色牌；E代表該位置為空。玩法：當(dāng)一個(gè)牌移入相鄰的空位時(shí)，費(fèi)用等于挑過的牌數(shù)加1。一個(gè)牌至多可跳過兩個(gè)牌進(jìn)入空位置，其費(fèi)用等于跳過的牌數(shù)加1。要求把所有的B都移到所有的W的右邊，設(shè)計(jì)h(x)。解：顯然W左邊的B越少越接近目標(biāo)，因此可用W左邊B的個(gè)數(shù)作為h(x)h(x)=3*(每個(gè)W左邊B個(gè)數(shù)的總和）h(x)=3*(2+2+3)=21BBBWWWEBBBWWWE16例：設(shè)有如下結(jié)構(gòu)的移動將牌游戲BBBWWWEBBBWWWE116例：傳教士和野人問題。請用A*算法解決該問題。

解：用m表示左岸的傳道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)，用三元組（m，c，b）表示問題的狀態(tài)。

對A*算法，首先需要確定估價(jià)函數(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é)點(diǎn)的深度。通過分析可知h（n）＜h*(n)，滿足A*算法的限制條件。

M-C問題的搜索過程如下頁圖所示。在該圖中，每個(gè)節(jié)點(diǎn)旁邊還標(biāo)出了該節(jié)點(diǎn)的h值和f值。17例：傳教士和野人問題。請用A*算法解決該問題。

解：用m表示17(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)18(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=181919194.4與/或樹的盲目搜索204.4與/或樹的盲目搜索2020概念:直接可解的簡單問題稱為本原問題，本原問題對應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)，在與或圖（樹）中無子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“與”關(guān)系，則該節(jié)點(diǎn)便稱為與節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“或”關(guān)系，則該節(jié)點(diǎn)便稱為或節(jié)點(diǎn)。注意，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。可解性判別(1)一個(gè)節(jié)點(diǎn)是可解，則節(jié)點(diǎn)須滿足下列條件之一:①終止節(jié)點(diǎn)是可解節(jié)點(diǎn)；②一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解；③一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)至少有一個(gè)可解。(2)一個(gè)節(jié)點(diǎn)是不可解，則節(jié)點(diǎn)須滿足下列條件之一:①非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)；②一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)至少有一個(gè)不可解；③一個(gè)或節(jié)點(diǎn)不可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都不可解。21概念:2121一.與/或樹的一般搜索與/或樹的搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。其一般搜索過程如下：

（1）把原始問題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)點(diǎn)；

（2）應(yīng)用分解或等價(jià)變換操作對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；

（3）為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；

（4）選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第（2）步和第（3）步，在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，直到初始節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。

上述搜索過程將形成一棵與/或樹，這種由搜索過程形成的與/或樹稱為搜索樹。當(dāng)搜索成功時(shí)，經(jīng)可解標(biāo)記過程標(biāo)識的由初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)構(gòu)成的子樹稱為解樹。用與/或樹法表示的問題求解過程與狀態(tài)空間法類似，也是通過搜索來實(shí)現(xiàn)對問題求解的。與/或樹的搜索策略也分為盲目搜索和啟發(fā)式搜索兩大類。22一.與/或樹的一般搜索與/或樹的搜索過程實(shí)22搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的，即由子節(jié)點(diǎn)的可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的可解性；由子節(jié)點(diǎn)的不可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的不可解性。在與/或樹中，除端節(jié)點(diǎn)和終止節(jié)點(diǎn)外，一個(gè)節(jié)點(diǎn)的可解性完全是由其子節(jié)點(diǎn)來決定的。對與節(jié)點(diǎn)，只有其所有子節(jié)點(diǎn)都為可解時(shí)它才為可解，只要有一個(gè)子節(jié)點(diǎn)不可解它就是不可解的；對或節(jié)點(diǎn)，只要有一個(gè)子節(jié)點(diǎn)可解它就是可解的，僅當(dāng)所有子節(jié)點(diǎn)都是不可解時(shí)它才為不可解。這種由可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為可解節(jié)點(diǎn)的過程稱為可解標(biāo)記過程；由不可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為不可解節(jié)點(diǎn)的過程稱為不可解標(biāo)記過程。

由于與/或樹搜索的目標(biāo)是尋找解樹，因此，如果搜索過程確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn)，則其不可解的后裔節(jié)點(diǎn)就可從搜索樹中刪去；同樣，如果搜索過程能確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn)，則其后裔節(jié)點(diǎn)也可從搜索樹中刪去。23搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的，23與狀態(tài)空間的廣度優(yōu)先搜索類似，只是在搜索過程中需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，其搜索算法如下：

（1）把初始節(jié)點(diǎn)S0放人Open表中；

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

（3）如果節(jié)點(diǎn)n可擴(kuò)展，則做下列工作：

①擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；

②考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有，則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)記過程對其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn)，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點(diǎn)，則從Open表中刪去具有可解先輩的節(jié)點(diǎn)；

③

轉(zhuǎn)第（2）步。二.與/或樹的廣度優(yōu)先搜索24與狀態(tài)空間的廣度優(yōu)先搜索類似，只是在搜索過程24（4）如果節(jié)點(diǎn)n不可擴(kuò)展，則做下列工作：

①

標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；

②

應(yīng)用不可解標(biāo)記過程對節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點(diǎn)，則從Open表中刪去具有不可解先輩的節(jié)點(diǎn)；

③轉(zhuǎn)第（2）步。25（4）如果節(jié)點(diǎn)n不可擴(kuò)展，則做下列工作：

25例：設(shè)有如下圖所示的與/或樹，節(jié)點(diǎn)按圖中所標(biāo)注的順序號進(jìn)行擴(kuò)展，其中標(biāo)有t1、t2、t3的節(jié)點(diǎn)是終止節(jié)點(diǎn)，A、B、C為不可解的端節(jié)點(diǎn)。

與/或樹的廣度優(yōu)先搜索123A4t1t3CBt25搜索過程為：

（1）先擴(kuò)展1號節(jié)點(diǎn)，生成2號節(jié)點(diǎn)和3號節(jié)點(diǎn)，由于這兩個(gè)子節(jié)點(diǎn)都不是終止節(jié)點(diǎn)，因此接著擴(kuò)展2號節(jié)點(diǎn)。（2）擴(kuò)展2號節(jié)點(diǎn)，生成A節(jié)點(diǎn)和4號節(jié)點(diǎn)。由于這兩個(gè)子節(jié)點(diǎn)均不是終止節(jié)點(diǎn)，因此接著擴(kuò)展3號節(jié)點(diǎn)。（3）擴(kuò)展3號節(jié)點(diǎn)，生成t1節(jié)點(diǎn)和5號節(jié)點(diǎn)。由于t1為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，對其先輩中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記，由于t1的父節(jié)點(diǎn)是一個(gè)與節(jié)點(diǎn)，因此不能確定3號節(jié)點(diǎn)是否可解。（4）擴(kuò)展節(jié)點(diǎn)A，由于A是端節(jié)點(diǎn)，調(diào)用不可解標(biāo)記過程，由于2號節(jié)點(diǎn)是或節(jié)點(diǎn)，因此不能確定2號節(jié)點(diǎn)是不可解節(jié)點(diǎn)。（5）擴(kuò)展4號節(jié)點(diǎn)，生成t2節(jié)點(diǎn)和B節(jié)點(diǎn)。由于t2為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，標(biāo)記4號節(jié)點(diǎn)為可解節(jié)點(diǎn)，標(biāo)記2號節(jié)點(diǎn)為可解節(jié)點(diǎn)，但不能標(biāo)記1號節(jié)點(diǎn)為可解節(jié)點(diǎn)。（6）擴(kuò)展5號節(jié)點(diǎn)，生成t3節(jié)點(diǎn)和C節(jié)點(diǎn)。由于t3為終止節(jié)點(diǎn)，標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，標(biāo)記5號節(jié)點(diǎn)為可解節(jié)點(diǎn)，標(biāo)記3號節(jié)點(diǎn)為可解節(jié)點(diǎn)。標(biāo)記1號節(jié)點(diǎn)為可解節(jié)點(diǎn)。（7）搜索成功，得到由1、2、3、4、5號節(jié)點(diǎn)及t1、t2、t3節(jié)點(diǎn)構(gòu)成的解樹。該解樹如上圖中的粗線所示。26例：設(shè)有如下圖所示的與/或樹，節(jié)點(diǎn)按圖中所標(biāo)注的順序號26可以帶有深度限制dm，其搜索算法如下：

（1）把初始節(jié)點(diǎn)S0放入Open表中；

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

（3）如果節(jié)點(diǎn)n的深度等于dm，則轉(zhuǎn)第（5）步的第①點(diǎn)；

（4）如果節(jié)點(diǎn)n可擴(kuò)展，則做下列工作：

①

擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；

②

考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有，則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)記過程對其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn)，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點(diǎn)，則從Open表中刪去具有可解先輩的節(jié)點(diǎn)；

③

轉(zhuǎn)第（2）步。三.與/或樹的深度優(yōu)先搜索27可以帶有深度限制dm，其搜索算法如下：

（1）把初始27（5）如果節(jié)點(diǎn)n不可擴(kuò)展，則做下列工作：

①

標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；

②應(yīng)用不可解標(biāo)記過程對節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定為不可解節(jié)點(diǎn)，則從Open表中刪去具有不可解先輩的節(jié)點(diǎn)；

③

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

與/或樹的深度優(yōu)先搜索123A4t1t3CBt25例如，對上例所給出的與／或樹，若按有界深度優(yōu)先搜索，且給定dm=4，則其擴(kuò)展節(jié)點(diǎn)的順序?yàn)椋?/p>

1，3，5，2，4

其解樹與上例相同。28（5）如果節(jié)點(diǎn)n不可擴(kuò)展，則做下列工作：

28與/或樹的盲目搜索是按確定路線進(jìn)行的，當(dāng)要選擇一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)，只是根據(jù)節(jié)點(diǎn)在與/或樹中所處的位置，而沒有考慮要付出的代價(jià)，因而求得的解樹不一定是代價(jià)最小的解樹，即不一定是最優(yōu)解樹。因此，需要考慮與/或樹的啟發(fā)式搜索。在討論與／或樹的啟發(fā)式搜索過程之前，需要先討論幾個(gè)有關(guān)的概念。

一.解樹的代價(jià)與希望樹

與／或樹的啟發(fā)式搜索過程是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。對搜索的每一步，算法都試圖找到一個(gè)最有希望成為最優(yōu)解樹的子樹。最優(yōu)解樹是指代價(jià)最小的那棵解樹。4.5與/或樹的啟發(fā)式搜索29與/或樹的盲目搜索是按確定路線進(jìn)行的，當(dāng)要291．解樹的代價(jià)

在與/或樹的啟發(fā)式搜索過程中，解樹的代價(jià)可按如下規(guī)則計(jì)算：

（1）若n為終止節(jié)點(diǎn)，則其代價(jià)h（n）=0。

（2）若n為或節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1，n2，…，nk，則n的代價(jià)為h（n）=min{c（n，ni）＋h（ni）}(1≤i≤k)其中，c（n，ni）是節(jié)點(diǎn)n到其子節(jié)點(diǎn)ni的邊代價(jià)。

（3）若n為與節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1，n2，…，nk，則n的代價(jià)可用和代價(jià)法或最大代價(jià)法。

若用和代價(jià)法，則其計(jì)算公式為：h（n）=Σ((c(n，ni)＋h(ni))i=1,2,……,k

若用最大代價(jià)法，則其計(jì)算公式為：

h（n）=max｛c（n，ni）＋h（ni）｝(1≤i≤k)

（4）若n是端節(jié)點(diǎn)，但又不是終止節(jié)點(diǎn)，則n不可擴(kuò)展，其代價(jià)定義為h（n）=∞

（5）根節(jié)點(diǎn)的代價(jià)即為解樹的代價(jià)。301．解樹的代價(jià)

在與/或樹的啟發(fā)式搜索過程中30例：設(shè)右圖是一棵與/或樹，其中包括兩棵解樹，左邊的解樹由S0、A、t1、C及t3組成；右邊的解樹由S0、B、t2、D及t4組成。在此與/或樹中，t1、t2、t3、t4為終止節(jié)點(diǎn)；E、F是端節(jié)點(diǎn)；邊上的數(shù)字是該邊的代價(jià)。請計(jì)算解樹的代價(jià)。S0ABt1Ct3Et2Dt4F與／或樹的代價(jià)22463521解：先計(jì)算左邊的解樹

按和代價(jià)：h（S0）=2＋4＋6＋2=14

按最大代價(jià)：h（S0）=8＋2=10

再計(jì)算右邊的解樹

按和代價(jià)：h（S0）=1＋5＋3＋2=11

按最大代價(jià)：h（S0）=6＋2=8

在本例中，無論按和代價(jià)還是最大代價(jià)，右邊的解樹都是最優(yōu)解樹。但在有些情況下，當(dāng)采用的代價(jià)法不同時(shí)，找到的最優(yōu)解樹有可能不同。31例：設(shè)右圖是一棵與/或樹，其中包括兩棵解樹，左邊的解樹由S312．希望樹

為了找到最優(yōu)解樹，搜索過程的任何時(shí)刻都應(yīng)該選擇那些最有希望成為最優(yōu)解樹一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展。由于這些節(jié)點(diǎn)及其父節(jié)點(diǎn)所構(gòu)成的與/或樹最有可能成為最優(yōu)解樹的一部分，因此稱它為希望解樹，也簡稱為希望樹。需要注意，希望解樹是會隨搜索過程而不斷變化的。定義：希望解樹T

（1）初始節(jié)點(diǎn)S0在希望樹T中；

（2）如果n是具有子節(jié)點(diǎn)n1，n2，…，nk的或節(jié)點(diǎn)，則n的某個(gè)子節(jié)點(diǎn)ni在希望樹T中的充分必要條件是

h（n）=min{c（n，ni）＋h（ni）}1≤i≤k

（3）如果n是與節(jié)點(diǎn)，則n的全部子節(jié)點(diǎn)都在希望樹T中。322．希望樹

為了找到最優(yōu)解樹，搜索過程的任何時(shí)刻都應(yīng)32

與／或樹的啟發(fā)式搜索需要不斷地選擇、修正希望樹，其搜索過程如下：

（1）把初始節(jié)點(diǎn)S0放入Open表中，計(jì)算h（S0）；

（2）計(jì)算希望樹T；

（3）依次在Open表中取出T的端節(jié)點(diǎn)放入Closed表，記節(jié)點(diǎn)為n；

（4）如果節(jié)點(diǎn)n為終止節(jié)點(diǎn)，則做下列工作：

①標(biāo)記節(jié)點(diǎn)n為可解節(jié)點(diǎn)；

②在T上應(yīng)用可解標(biāo)記過程，對n的先輩節(jié)點(diǎn)中的所有可解節(jié)點(diǎn)進(jìn)行標(biāo)記；

③如果初始節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn)，則T就是最優(yōu)解樹，成功退出；

④

否則，從Open表中刪去具有可解先輩的所有節(jié)點(diǎn)；

⑤轉(zhuǎn)第（2）步。二.與/或樹的啟發(fā)式搜索過程33與／或樹的啟發(fā)式搜索需要不斷地選擇、修正希望樹，其搜33（5）如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn)，但可擴(kuò)展，則做下列工作：

①擴(kuò)展節(jié)點(diǎn)n，生成n的所有子節(jié)點(diǎn)；

②把這些子節(jié)點(diǎn)都放入Open表中，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)n的指針；

③計(jì)算這些子節(jié)點(diǎn)及其先輩節(jié)點(diǎn)的h值；

④

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

（6）如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn)，且不可擴(kuò)展，則做下列工作：

①

標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；

②

在T上應(yīng)用不可解標(biāo)記過程，對n的先輩節(jié)點(diǎn)中的所有不可解節(jié)點(diǎn)進(jìn)行標(biāo)記；

③

如果初始節(jié)點(diǎn)S0能夠被標(biāo)記為不可解節(jié)點(diǎn)，則問題無解，失敗退出；

④否則，從Open表中刪去具有不可解先輩的所有節(jié)點(diǎn)；

⑤轉(zhuǎn)第（2）步。34（5）如果節(jié)點(diǎn)n不是終止節(jié)點(diǎn)，但可擴(kuò)展，則做下列工作：

34例，搜索過程每次擴(kuò)展節(jié)點(diǎn)時(shí)都同時(shí)擴(kuò)展兩層，且按一層或節(jié)點(diǎn)、一層與節(jié)點(diǎn)的間隔方式進(jìn)行擴(kuò)展。設(shè)初始節(jié)點(diǎn)為S0，對S0擴(kuò)展后得到的與/或樹如下圖所示。其中，端節(jié)點(diǎn)B、C、E、F下面的數(shù)字是用啟發(fā)函數(shù)估算出的h值，節(jié)點(diǎn)A、D旁邊的數(shù)字是按和代價(jià)法計(jì)算出來的節(jié)點(diǎn)代價(jià)。此時(shí)，S0的右子樹是當(dāng)前的希望樹，下面對其端節(jié)點(diǎn)進(jìn)行擴(kuò)展。S0ADBCEF873332擴(kuò)展S0后的與／或樹835例，搜索過程每次擴(kuò)展節(jié)點(diǎn)時(shí)都同時(shí)擴(kuò)展兩層，且35擴(kuò)展節(jié)點(diǎn)E，由右子樹求出的h（S0）=12，而由左子樹求出的h（S0）=9。故當(dāng)前的希望樹應(yīng)改為左子樹。對B擴(kuò)展兩層。由于H和I是可解節(jié)點(diǎn)，調(diào)用可解標(biāo)記過程，得節(jié)點(diǎn)G、B也為可解節(jié)點(diǎn)，但不能標(biāo)記S0為可解節(jié)點(diǎn)，須繼續(xù)擴(kuò)展。當(dāng)前的希望樹仍然是左子樹。對C擴(kuò)展。擴(kuò)展兩層后得到的與／或樹如圖3所示。S0ADBCEF8332

3222776119圖1擴(kuò)展E后的與／或樹S0ADBCEF8332

3222776119GKHILJ002226圖2擴(kuò)展B后的與／或樹S0DEFABC8332

3222776119IGKHLJ002226MNP005229圖3擴(kuò)展C后的與／或樹9由于N和P是可解節(jié)點(diǎn)，調(diào)用可解標(biāo)記過程，得節(jié)點(diǎn)M、C、A也為可解節(jié)點(diǎn)，進(jìn)而S0為可解節(jié)點(diǎn)。求出了代價(jià)最小的解樹，即最優(yōu)解樹，如圖中粗線所示。按和代價(jià)法，該最優(yōu)解樹的代價(jià)為9。36擴(kuò)展節(jié)點(diǎn)E，由右子樹求出的h（S0）=1236

博弈是一類富有智能行為的競爭活動，如下棋、打牌、戰(zhàn)爭等。博弈可分為雙人完備信息博弈和機(jī)遇性博弈。所謂雙人完備信息博弈，就是兩位選手對壘，輪流走步，每一方不僅知道對方已經(jīng)走過的棋步，而且還能估計(jì)出對方未來的走步。對弈的結(jié)果是一方贏，另一方輸；或者雙方和局。所謂機(jī)遇性博弈，是指存在不可預(yù)測性的博弈，例如擲幣等。對機(jī)遇性博弈，由于不具備完備信息，因此不作討論。假設(shè)博弈的一方為MAX，另一方為MIN。在博弈過程的每一步，可供MAX和MIN選擇的行動方案都可能有多種。從MAX方的觀點(diǎn)看，可供自己選擇的那些行動方案之間是“或”的關(guān)系，選擇哪個(gè)方案完全是由自己決定的；而對那些可供MIN選擇的行動方案之間則是“與”的關(guān)系，主動權(quán)掌握在MIN的手里，任何一個(gè)方案都有可能被MIN選中，MAX必須防止那種對自己最為不利的情況的發(fā)生。4.6博弈樹的啟發(fā)式搜索一.概述37博弈是一類富有智能行為的競爭活動，如下棋、打37若把雙人完備信息博弈過程用圖表示出來，就可得到一棵與/或樹，這種與/或樹被稱為博弈樹。在博弈樹中，那些下一步該MAX走步的節(jié)點(diǎn)稱為MAX節(jié)點(diǎn)，而下一步該MIN走步的節(jié)點(diǎn)稱為MIN節(jié)點(diǎn)。博弈樹具有如下特點(diǎn)：（l）博弈的初始狀態(tài)是初始節(jié)點(diǎn)；（2）博弈樹中的“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的；（3）整個(gè)博弈過程始終站在某一方的立場上，所有能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。例如，站在MAX方，所有能使MAX方獲勝的節(jié)點(diǎn)都是可解節(jié)點(diǎn)，所有能使MIN方獲勝的節(jié)點(diǎn)都是不可解節(jié)點(diǎn)。38若把雙人完備信息博弈過程用圖表示出來，就可得38對簡單的博弈問題，可以生成整個(gè)博弈樹，找到必勝的策略。但對于復(fù)雜的博弈，如國際象棋，大約有10120個(gè)節(jié)點(diǎn)，要生成整個(gè)搜索樹是不可能的。一種可行的方法是用當(dāng)前正在考察的節(jié)點(diǎn)生成一棵部分博弈樹，由于該博弈樹的葉節(jié)點(diǎn)一般不是哪一方的獲勝節(jié)點(diǎn)，因此，需利用估價(jià)函數(shù)f(n)對葉節(jié)點(diǎn)進(jìn)行靜態(tài)評估，對MAX有利的節(jié)點(diǎn)其估價(jià)函數(shù)取正值；那些對MIN有利的節(jié)點(diǎn)，其估價(jià)函數(shù)取負(fù)值；那些使雙方均等的節(jié)點(diǎn)，其估價(jià)函數(shù)取接近于0的值。二.極大極小過程為了計(jì)算非葉節(jié)點(diǎn)的值，必須從葉節(jié)點(diǎn)向上倒推。對于MAX節(jié)點(diǎn)，由于MAX方總是選擇估值最大的走步，因此，MAX節(jié)點(diǎn)的倒推值應(yīng)該取其后繼節(jié)點(diǎn)估值的最大值。對于MIN節(jié)點(diǎn)，由于MIN方總是選擇使估值最小的走步，因此MIN節(jié)點(diǎn)的倒推值應(yīng)取其后繼節(jié)點(diǎn)估值的最小值。這樣一步一步的計(jì)算倒推值，直至求出初始節(jié)點(diǎn)的倒推值為止。這一過程稱為極大極小過程。39對簡單的博弈問題，可以生成整個(gè)博弈樹，找到必39例：一字棋游戲。設(shè)有一個(gè)三行三列的棋盤，如下圖所示，兩個(gè)棋手輪流走步，每個(gè)棋手走步時(shí)往空格上擺一個(gè)自己的棋子，誰先使自己的棋子成三子一線為贏。設(shè)MAX方的棋子用×標(biāo)記，MIN方的棋子用

○標(biāo)記，并規(guī)定MAX方先走步。

解：為了對葉節(jié)點(diǎn)進(jìn)行靜態(tài)估值，規(guī)定估價(jià)函數(shù)e（P）如下：

若P是MAX的必勝局，則e（P）=+∞；

若P是MIN的必勝局，則e（P）=-∞；一字棋棋盤若P對MAX、MIN都是勝負(fù)未定局，則e（P）=e（+P）－e（-P）

其中，e（+P）表示棋局P上有可能使×成三子一線的數(shù)目；e（-P）表示棋局P上有可能使○成三子一線的數(shù)目。40例：一字棋游戲。設(shè)有一個(gè)三行三列的棋盤，如下圖所示，兩個(gè)棋40例如，對圖1所示的棋局有估價(jià)函數(shù)值e（P）＝6-4＝2圖1棋局1在搜索過程中，具有對稱性的棋局認(rèn)為是同一棋局。例如，圖2所示的棋局可以認(rèn)為是同一個(gè)棋局，這樣可以大大減少搜索空間。圖3給出了第一著走棋以后生成的博弈樹。圖中葉節(jié)點(diǎn)下面的數(shù)字是該節(jié)點(diǎn)的靜態(tài)估值，非葉節(jié)點(diǎn)旁邊的數(shù)字是計(jì)算出的倒推值。從圖中可以看出，對MAX來說S2是一著最好的走棋，它具有較大的倒推值。圖2對稱棋局的例子41例如，對圖1所示的棋局有估價(jià)函數(shù)值e（P）＝6-4＝2圖41

圖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=242

圖3一子棋的極大極小搜42極大極小值算法FunctionMAX-MIN-DECISION(state)returnsanaction inputs:state(currentstateingame) v←MAX-VALUE(state) returntheactioninSUCCESSORS(state)withvaluevFunctionMAX-VALUE(state)returnsautilityvalue ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞ fora,sinSUCCESSORS(state)dov←MAX(v,MIN-VALUE(s)) returnv (a=action招數(shù))FunctionMIN-VALUE(state)returnsautilityvalue ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ fora,sinSUCCESSORS(state)dov←MIN(v,MAX-VALUE(s)) returnv43極大極小值算法FunctionMAX-MIN-DECISI43上述極大極小過程是先生成與/或樹，然后再計(jì)算各節(jié)點(diǎn)的估值，這種生成節(jié)點(diǎn)和計(jì)算估值相分離的搜索方式，需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn)，因此搜索效率較低。如果能邊生成節(jié)點(diǎn)邊對節(jié)點(diǎn)估值，從而可以剪去一些沒用的分枝，這種技術(shù)稱為α-β剪枝過程。三.α-β剪枝<=23S0DEFABC5332對于一個(gè)與節(jié)點(diǎn)來說，它取當(dāng)前子節(jié)點(diǎn)中的最小倒推值作為它倒推值的上界，稱該值為β值。對于一個(gè)或節(jié)點(diǎn)來說，它取當(dāng)前子節(jié)點(diǎn)中的最大倒推值作為它倒推值的下界，稱該值為α

值。44上述極大極小過程是先生成與/或樹，然后再計(jì)算44α-β剪枝的方法如下：

（1）MAX節(jié)點(diǎn)的α值為當(dāng)前子節(jié)點(diǎn)的最大倒推值；

（2）

MIN節(jié)點(diǎn)的β值為當(dāng)前子節(jié)點(diǎn)的最小倒推值；

（3）

α-β剪枝的規(guī)則如下：

①

任何MAX節(jié)點(diǎn)n的α值大于或等于它先輩節(jié)點(diǎn)的β值，則n以下的分枝可停止搜索，并令節(jié)點(diǎn)n的倒推值為α。這種剪枝稱為β剪枝。

②

任何MIN節(jié)點(diǎn)n的β值小于或等于它先輩節(jié)點(diǎn)的α值，則n以下的分枝可停止搜索，并令節(jié)點(diǎn)n的倒推值為β。這種剪枝稱為α剪枝。

三.α-β剪枝≥αmin≤βmax≥α45α-β剪枝的方法如下：

（1）MAX節(jié)點(diǎn)的α值45S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≥0＝0≤-6＝0≤0＝4＊＊＊＊＊α-β剪枝的例子T446S0ABCDFGHEIJKLMNPQRS4861580-6446S00-330031653-322-3-254-3089-347S00-330031653-322-3-254-3089-347S00-330031653-322-3-254-3089-3＊＊＊＊＊＊跳棋程序的學(xué)習(xí)策略48S00-330031653-322-3-254-3089-348-剪枝算法在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回值基礎(chǔ)上增加了判斷FunctionALPHA-BETA-SEARCH(state)returnsanaction inputs:state(currentstateingame) v←MAX-VALUE(state,-∞,+∞) returntheactioninSUCCESSORS(state)withvaluev49-剪枝算法在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回49-剪枝算法FunctionMAX-VALUE(state,,)returnsautilityvalue inputs:state ,thevalueofthebestalternativeforMAXalongthepathtostate ,thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←-∞ fora,sinSUCCESSORS(state)do v←MAX(v,MIN-VALUE(s,,)) ifv≥thenreturnv

←MAX(,v) returnv50-剪枝算法FunctionMAX-VALUE(stat50-剪枝算法FunctionMIN-VALUE(state,,)returnsautilityvalue inputs:state ,thevalueofthebestalternativeforMAXalongthepathtostate thevalueofthebestalternativeforMINalongthepathtostate ifTERMINAL-TEST(state)thenreturnUTILITY(state) v←+∞ fora,sinSUCCESSORS(state)do v←MIN(v,MAX-VALUE(s,

,)) ifv≤thenreturnv

←MIN(,v) returnv51-剪枝算法FunctionMIN-VALUE(stat51產(chǎn)生式系統(tǒng)與圖搜索分析產(chǎn)生式正向推理算法，可以看出，它們只能用于解決邏輯推理性問題。若要求解規(guī)劃性問題則還需要：(1)記錄動態(tài)數(shù)據(jù)庫狀態(tài)變化的歷史，這就需要增設(shè)一個(gè)CLOSED表。(2)若要回溯，則還需保存與每個(gè)動態(tài)數(shù)據(jù)庫狀態(tài)對應(yīng)的可用規(guī)則集。因?yàn)閯討B(tài)數(shù)據(jù)庫狀態(tài)與可用規(guī)則集實(shí)際是一一對應(yīng)的。(3)要進(jìn)行樹式搜索，還需設(shè)置一個(gè)OPEN表，以進(jìn)行新生動態(tài)數(shù)據(jù)庫的狀態(tài)保存和當(dāng)前動態(tài)數(shù)據(jù)庫狀態(tài)的切換。(4)還要考慮一條規(guī)則是否只允許執(zhí)行一次。若是，則要對已執(zhí)行了的規(guī)則進(jìn)行標(biāo)記。成功退出失敗退出把初始數(shù)據(jù)放入綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫中有解嗎？形成可用知識集可用知識集空？按照沖突消解策略從該知識集中選出一條知識進(jìn)行推理推出的是新事實(shí)？將該新事實(shí)加入到綜合數(shù)據(jù)庫中把用戶補(bǔ)充的新事實(shí)加入到綜合數(shù)據(jù)庫中用戶可以補(bǔ)充新事實(shí)嗎？知識庫中有可用知識嗎？YYYYYNNNNN52產(chǎn)生式系統(tǒng)與圖搜索分析產(chǎn)生式正向推理算法，52可以看出，二者實(shí)際是一回事。圖搜索技術(shù)描述了問題求解的方法，產(chǎn)生式系統(tǒng)則給出了實(shí)施這種方法的一種計(jì)算機(jī)程序系統(tǒng)的結(jié)構(gòu)模式。這樣，問題求解、圖搜索和產(chǎn)生式系統(tǒng)三者的關(guān)系是：問題求解是目的，圖搜索是方法，產(chǎn)生式系統(tǒng)是形式。53可以看出，二者實(shí)際是一回事。圖搜索技術(shù)描述了問題求解53前面討論的各種搜索方法都沒有用到問題本身的特性信息，只是按照事先設(shè)定的線路進(jìn)行搜索，具有較大的盲目性。事實(shí)上，如果能夠利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程，則對搜索將是十分有益的。這種利用問題自身的特性信息來引導(dǎo)搜索過程的搜索方法稱為啟發(fā)式搜索。由于啟發(fā)式搜索方法具有較強(qiáng)的針對性，因此，可以縮小搜索范圍，提高搜索效率。4.5狀態(tài)空間的啟發(fā)式搜索54前面討論的各種搜索方法都沒有用到問題本身的特54

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

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

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

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

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

③能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上被刪除。

一般來說，搜索過程所使用的啟發(fā)性信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無用節(jié)點(diǎn)就越少。55啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息55

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

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

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

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

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

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

f（S0）=0＋3=3

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

2831476557例：八數(shù)碼難題。設(shè)問題的初始狀態(tài)S0和目標(biāo)狀態(tài)Sg如前57二.A算法

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

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

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

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

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

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

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

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

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

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

1．全局擇優(yōu)搜索59每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí)，總是從Open表的所有節(jié)點(diǎn)中選擇59由于上述算法的第（7）步要對Open表中的全部節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大重新進(jìn)行排序，這樣在算法第（3）步取出的節(jié)點(diǎn)就一定是Open表的所有節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此，它是一種全局擇優(yōu)的搜索方式。

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

8321476528371465

23847652384765

S9

4123847651238476512378465S5

5S66

S8

6

S7

4SgS10

4S11

6S1

4S2

4

S3

5S4

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

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

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

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

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

2．局部擇優(yōu)搜索(瞎子爬山法)62在局部擇優(yōu)搜索中，每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時(shí)，總是從62

由于這一算法的第（6）步僅是把剛生成的子節(jié)點(diǎn)按其估價(jià)函數(shù)值從小到大放入Open表的首都，這樣在算法第（3）步取出的節(jié)點(diǎn)僅是剛生成的子節(jié)點(diǎn)中估價(jià)函數(shù)值最小的一個(gè)節(jié)點(diǎn)。因此，它是一種局部擇優(yōu)的搜索方式。對這一算法進(jìn)一步分析也可以發(fā)現(xiàn)：如果取估價(jià)函數(shù)f（n）=g（n），則它將退化為代價(jià)樹的深度優(yōu)先搜索；如果取估價(jià)函數(shù)f（n）=d（n），則它將退化為深度優(yōu)先搜索?？梢姡疃葍?yōu)先搜索和代價(jià)樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個(gè)特例。63由于這一算法的第（6）步僅是把剛生成的子節(jié)點(diǎn)63三.A*算法前面討論的啟發(fā)式搜索算法，都沒有對估價(jià)函數(shù)f(n)作任何限制。實(shí)際上，估價(jià)函數(shù)對搜索過程是十分重要的，如果選擇不當(dāng)，則有可能找不到問題的解，或者找到的不是問題的最優(yōu)解。為此，需要對估價(jià)函數(shù)進(jìn)行某些限制。A*算法就是對估價(jià)函數(shù)加上一些限制后得到的一種啟發(fā)式搜索算法。64三.A*算法前面討論的啟發(fā)式搜索算法，都沒64假設(shè)f*(n)為從初始節(jié)點(diǎn)S0出發(fā)，約束經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)值。估價(jià)函數(shù)f(n)是f*(n)的估計(jì)值。顯然，f*（n）應(yīng)由以下兩部分所組成：一部分是從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià)，記為g*（n）；另一部分是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，記為h*（n），當(dāng)問題有多個(gè)目標(biāo)節(jié)點(diǎn)時(shí)，應(yīng)取其中代價(jià)最小的一個(gè)。因此有

f*（n）＝g*（n）＋h*（n）

把估價(jià)函數(shù)f(n)與f*(n)相比，g（n）是對g*（n）的一個(gè)估計(jì)，h（n）是對h*（n）的一個(gè)估計(jì)。在這兩個(gè)估計(jì)中，盡管g（n）的值容易計(jì)算，但它不一定就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià)，很有可能從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的真正最小代價(jià)還沒有找到，故有g(shù)（n）≥g*（n）。

有了g*（n）和h*（n）的定義，如果對A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的g（n）和h（n）分別提出如下限制：

第一，g（n）是對g*（n）的估計(jì)，且g（n）＞0；

第二，h（n）是h*（n）的下界，即對任意節(jié)點(diǎn)n均有

h（n）≤h*（n）。

則稱得到的算法為A*算法。65假設(shè)f*(n)為從初始節(jié)點(diǎn)S0出發(fā)，約束經(jīng)過65A*算法的有關(guān)特性。

1．A*算法的可納性

一般來說，對任意一個(gè)狀態(tài)空間圖，當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在時(shí)，如果搜索算法能在有限步內(nèi)找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。A*算法是可采納的。(證明略）。

2.A*算法的最優(yōu)性

A*算法的搜索效率很大程度上取決于估價(jià)函數(shù)h（n）。一般來說，在滿足h（n）≤h*（n）的前提下，h（n）的值越大越好。h（n）的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少，搜索效率就越高。A*算法的這一特性也稱為信息性。(證明略)66A*算法的有關(guān)特性。

1366A*算法應(yīng)用舉例

例：八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀態(tài)和前例相同。要求用A*算法解決該問題。

解：在上例中，我們?nèi)（n）=W（n）。盡管我們對h*（n）不能確切知道，但當(dāng)采用單位代價(jià)時(shí)，通過對“不在位”數(shù)碼個(gè)數(shù)的估計(jì)，可以得出至少要移動W（n）步才能到達(dá)目標(biāo)，顯然有W（n）≤h*（n）。因此，前例中所定義的h（n）滿足A*算法的限制條件。

這里再取另外一種啟發(fā)函數(shù)h（n）=P（n），P（n）定義為每一個(gè)數(shù)碼與其目標(biāo)位置之間距離（不考慮夾在其間的數(shù)碼）的總和，同樣可以斷定至少要移動P（n）步才能到達(dá)目標(biāo)，因此有P（n）≤h*（n），即滿足A*算法的限制條件。

23847655238476167A*算法應(yīng)用舉例

例：八數(shù)碼難題。問題的初始狀態(tài)和目標(biāo)狀6728314765h*=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）的搜索樹68283h*=4,f=4S0232832868例：設(shè)有如下結(jié)構(gòu)的移動將牌游戲B代表黑色牌，W代表白色牌；E代表該位置為空。玩法：當(dāng)一個(gè)牌移入相鄰的空位時(shí)，費(fèi)用等于挑過的牌數(shù)加1。一個(gè)牌至多可跳過兩個(gè)牌進(jìn)入空位置，其費(fèi)用等于跳過的牌數(shù)加1。要求把所有的B都移到所有的W的右邊，設(shè)計(jì)h(x)。解：顯然W左邊的B越少越接近目標(biāo)，因此可用W左邊B的個(gè)數(shù)作為h(x)h(x)=3*(每個(gè)W左邊B個(gè)數(shù)的總和）h(x)=3*(2+2+3)=21BBBWWWEBBBWWWE69例：設(shè)有如下結(jié)構(gòu)的移動將牌游戲BBBWWWEBBBWWWE169例：傳教士和野人問題。請用A*算法解決該問題。

解：用m表示左岸的傳道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)，用三元組（m，c，b）表示問題的狀態(tài)。

對A*算法，首先需要確定估價(jià)函數(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é)點(diǎn)的深度。通過分析可知h（n）＜h*(n)，滿足A*算法的限制條件。

M-C問題的搜索過程如下頁圖所示。在該圖中，每個(gè)節(jié)點(diǎn)旁邊還標(biāo)出了該節(jié)點(diǎn)的h值和f值。70例：傳教士和野人問題。請用A*算法解決該問題。

解：用m表示70(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)71(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=717219724.4與/或樹的盲目搜索734.4與/或樹的盲目搜索2073概念:直接可解的簡單問題稱為本原問題，本原問題對應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)，在與或圖（樹）中無子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“與”關(guān)系，則該節(jié)點(diǎn)便稱為與節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“或”關(guān)系，則該節(jié)點(diǎn)便稱為或節(jié)點(diǎn)。注意，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)?？山庑耘袆e(1)一個(gè)節(jié)點(diǎn)是可解，則節(jié)點(diǎn)須滿足下列條件之一:①終止節(jié)點(diǎn)是可解節(jié)點(diǎn)；②一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解；③一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)至少有一個(gè)可解。(2)一個(gè)節(jié)點(diǎn)是不可解，則節(jié)點(diǎn)須滿足下列條件之一:①非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)；②一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)至少有一個(gè)不可解；③一個(gè)或節(jié)點(diǎn)不可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都不可解。74概念:2174一.與/或樹的一般搜索與/或樹的搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。其一般搜索過程如下：

（1）把原始問題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)點(diǎn)；

（2）應(yīng)用分解或等價(jià)變換操作對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；

（3）為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；

（4）選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第（2）步和第（3）步，在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，直到初始節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。

上述搜索過程將形成一棵與/或樹，這種由搜索過程形成的與/或樹稱為搜索樹。當(dāng)搜索成功時(shí)，經(jīng)可解標(biāo)記過程標(biāo)識的由初始節(jié)點(diǎn)及其下屬的可解節(jié)點(diǎn)構(gòu)成的子樹稱為解樹。用與/或樹法表示的問題求解過程與狀態(tài)空間法類似，也是通過搜索來實(shí)現(xiàn)對問題求解的。與/或樹的搜索策略也分為盲目搜索和啟發(fā)式搜索兩大類。75一.與/或樹的一般搜索與/或樹的搜索過程實(shí)75搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的，即由子節(jié)點(diǎn)的可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的可解性；由子節(jié)點(diǎn)的不可解性確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)的不可解性。在與/或樹中，除端節(jié)點(diǎn)和終止節(jié)點(diǎn)外，一個(gè)節(jié)點(diǎn)的可解性完全是由其子節(jié)點(diǎn)來決定的。對與節(jié)點(diǎn)，只有其所有子節(jié)點(diǎn)都為可解時(shí)它才為可解，只要有一個(gè)子節(jié)點(diǎn)不可解它就是不可解的；對或節(jié)點(diǎn)，只要有一個(gè)子節(jié)點(diǎn)可解它就是可解的，僅當(dāng)所有子節(jié)點(diǎn)都是不可解時(shí)它才為不可解。這種由可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為可解節(jié)點(diǎn)的過程稱為可解標(biāo)記過程；由不可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為不可解節(jié)點(diǎn)的過程稱為不可解標(biāo)記過程。

由于與/或樹搜索的目標(biāo)是尋找解樹，因此，如果搜索過程確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn)，則其不可解的后裔節(jié)點(diǎn)就可從搜索樹中刪去；同樣，如果搜索過程能確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn)，則其后裔節(jié)點(diǎn)也可從搜索樹中刪去。76搜索過程中的可解標(biāo)記過程與不可解標(biāo)記過程都是自下而上進(jìn)行的，76與狀態(tài)空間的廣度優(yōu)先搜索類似，只是在搜索過程中需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，其搜索算法如下：

（1）把初始節(jié)點(diǎn)S0放人Open表中；

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

（3）如果節(jié)點(diǎn)n可擴(kuò)展，則做下列工作：

①擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；

②考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。若有，則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)記過程對其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0能夠被標(biāo)記為可解節(jié)點(diǎn)，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點(diǎn)，則從Open表中刪去具有可解先輩的節(jié)點(diǎn)；

③

轉(zhuǎn)第（2）步。二.與/或樹的廣度優(yōu)先搜索77與狀態(tài)空間的廣度優(yōu)先搜索類似，只是在搜索過程77（4）如果節(jié)點(diǎn)n不可擴(kuò)展，則做下列工作：

①

標(biāo)記節(jié)點(diǎn)n為不可解節(jié)點(diǎn)；

②

應(yīng)用不可解標(biāo)記過程對節(jié)點(diǎn)n的先輩中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始解節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點(diǎn)，則從Open表中刪去具有不可解先輩的節(jié)點(diǎn)；

③轉(zhuǎn)第（2）步。78（4）如果節(jié)點(diǎn)n不可擴(kuò)展，則做下列工作：

78例：設(shè)有如下圖所示的與/或樹，節(jié)點(diǎn)按圖中所標(biāo)注的順序號進(jìn)行擴(kuò)展，其中標(biāo)有t1、t2、t3的節(jié)點(diǎn)是終止節(jié)點(diǎn)，A、B、C為不可解的端節(jié)點(diǎn)。

與/或樹的廣度優(yōu)先搜索123A4t1t3CBt25搜索過程為：

（1）先擴(kuò)展1號節(jié)點(diǎn)，生成2號節(jié)點(diǎn)和3號節(jié)點(diǎn)，由于這兩個(gè)子節(jié)點(diǎn)都不是終止節(jié)點(diǎn)，因此接著擴(kuò)展2號節(jié)點(diǎn)。（2）擴(kuò)展2號節(jié)點(diǎn)，生成A節(jié)點(diǎn)和4號節(jié)點(diǎn)。由于這兩個(gè)子節(jié)點(diǎn)均不是終止節(jié)點(diǎn)，因此接著擴(kuò)展3號節(jié)點(diǎn)。（3）擴(kuò)展3