級人工智能原理

前面討論的各種搜索方法都沒有用到問題本身的特性信息，只是按照事先設(shè)定的線路進展搜索，具有較大的盲目性?，F(xiàn)實上，假設(shè)可以利用搜索過程所得到的問題本身的一些特性信息來指點搜索過程，那么對搜索將是非常有益的。這種利用問題本身的特性信息來引導(dǎo)搜索過程的搜索方法稱為啟發(fā)式搜索。由于啟發(fā)式搜索方法具有較強的針對性，因此，可以減少搜索范圍，提高搜索效率。4.5形狀空間的啟發(fā)式搜索1啟發(fā)式搜索方法所根據(jù)的是問題本身的啟發(fā)性信息，而啟發(fā)性信息又是經(jīng)過估價函數(shù)作用到搜索過程中的。1．啟發(fā)性信息一.啟發(fā)性信息和估價函數(shù)啟發(fā)性信息是指那種與詳細問題求解過程有關(guān)的，并可指點搜索過程朝著最有希望方向前進的控制信息。啟發(fā)性信息普通有以下三種：

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

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

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

普通來說，搜索過程所運用的啟發(fā)性信息的啟發(fā)才干越強，擴展的無用節(jié)點就越少。22．估價函數(shù)用來估計節(jié)點重要性的函數(shù)稱為估價函數(shù)。估價函數(shù)f〔n〕被定義為從初始節(jié)點S0出發(fā)，經(jīng)過節(jié)點n到達目的節(jié)點Sg的一切途徑中最小途徑代價的估計值。它的普通方式為

f〔n〕=g〔n〕＋h〔n〕

其中，g〔n〕是從初始節(jié)點S0到節(jié)點n的實踐代價；h〔n〕是從節(jié)點n到目的節(jié)點S0的最優(yōu)途徑的估計代價。對g〔n〕的值，可以按指向父節(jié)點的指針，從節(jié)點n反向跟蹤到初始節(jié)點S0,得到一條從初始節(jié)點S0到節(jié)點n的最小代價途徑，然后把這條途徑上一切有向邊的代價相加，就得到g〔n〕的值。對h〔n〕的值，那么需求根據(jù)問題本身的特性來確定，它表達的是問題本身的啟發(fā)性信息，因此也稱h〔n〕為啟發(fā)函數(shù)。ng(n)h(n)3例：八數(shù)碼難題。設(shè)問題的初始形狀S0和目的形狀Sg如前所述，且估價函數(shù)為:f〔n〕=d〔n〕＋W〔n〕

其中，d〔n〕表示節(jié)點n在搜索樹中的深度；w〔n〕表示節(jié)點n中“不在位〞的數(shù)碼個數(shù)。請計算初始形狀S0的估價函數(shù)值f〔S0〕。

解：在本例的估價函數(shù)中，取g〔n〕=d〔n〕，h〔n〕=W〔n〕。它闡明是用從S0到n的途徑上的單位代價表示實踐代價，用n中“不在位〞的數(shù)碼個數(shù)作為啟發(fā)信息。普通來說，某節(jié)點中的“不在位〞的數(shù)碼個數(shù)越多，闡明它離目的節(jié)點越遠。

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

f〔S0〕=0＋3=3

這個例子僅是為了闡明估價函數(shù)的含義及估價函數(shù)值的計算。在問題搜索過程中，除了需求計算初始節(jié)點的估價函數(shù)之外，更多的是要計算新生成節(jié)點的估價函數(shù)值。283147654二.A算法在圖搜索算法中，假設(shè)能在搜索的每一步都利用估價函數(shù)f〔n〕=g〔n〕＋h〔n〕對Open表中的節(jié)點進展排序，那么該搜索算法為A算法。由于估價函數(shù)中帶有問題本身的啟發(fā)性信息，因此，A算法也被稱為啟發(fā)式搜索算法。

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

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

〔2〕假設(shè)Open表為空，那么問題無解，失敗退出；

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

〔4〕調(diào)查節(jié)點n能否為目的節(jié)點。假設(shè)是，那么找到了問題的解，勝利退出；

〔5〕假設(shè)節(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)搜索6由于上述算法的第〔7〕步要對Open表中的全部節(jié)點按其估價函數(shù)值從小到大重新進展排序，這樣在算法第〔3〕步取出的節(jié)點就一定是Open表的一切節(jié)點中估價函數(shù)值最小的一個節(jié)點。因此，它是一種全局擇優(yōu)的搜索方式。

對上述算法進一步分析還可以發(fā)現(xiàn)：假設(shè)取估價函數(shù)f(n)=g〔n〕，那么它將退化為代價樹的廣度優(yōu)先搜索；假設(shè)取估價函數(shù)f(n)=d〔n〕，那么它將退化為廣度優(yōu)先搜索。可見，廣度優(yōu)先搜索和代價樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個特例。7例：八數(shù)碼難題。2834765S028314765238476528347652836475832147652837146523847652384765S94123847651238476512378465S55S66S86S74SgS104S116S14S24S35S458在部分擇優(yōu)搜索中，每當需求擴展節(jié)點時，總是從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進展擴展。其搜索過程可描畫如下：〔1〕把初始節(jié)點S0放入Open表中，f(S0)=g(S0)+h(S0);〔2〕假設(shè)Open表為空，那么問題無解，失敗退出；

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

〔4〕調(diào)查節(jié)點n能否為目的節(jié)點。假設(shè)是，那么找到了問題的解，勝利退出；

〔5〕假設(shè)節(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)搜索(瞎子爬山法)9由于這一算法的第〔6〕步僅是把剛生成的子節(jié)點按其估價函數(shù)值從小到大放入Open表的首都，這樣在算法第〔3〕步取出的節(jié)點僅是剛生成的子節(jié)點中估價函數(shù)值最小的一個節(jié)點。因此，它是一種部分擇優(yōu)的搜索方式。對這一算法進一步分析也可以發(fā)現(xiàn)：假設(shè)取估價函數(shù)f〔n〕=g〔n〕，那么它將退化為代價樹的深度優(yōu)先搜索；假設(shè)取估價函數(shù)f〔n〕=d〔n〕，那么它將退化為深度優(yōu)先搜索?？梢姡疃葍?yōu)先搜索和代價樹的深度優(yōu)先搜索是部分擇優(yōu)搜索的兩個特例。10三.A*算法前面討論的啟發(fā)式搜索算法，都沒有對估價函數(shù)f(n)作任何限制。實踐上，估價函數(shù)對搜索過程是非常重要的，假設(shè)選擇不當，那么有能夠找不到問題的解，或者找到的不是問題的最優(yōu)解。為此，需求對估價函數(shù)進展某些限制。A*算法就是對估價函數(shù)加上一些限制后得到的一種啟發(fā)式搜索算法。11假設(shè)f*(n)為從初始節(jié)點S0出發(fā)，約束經(jīng)過節(jié)點n到達目的節(jié)點的最小代價值。估價函數(shù)f(n)是f*(n)的估計值。顯然，f*〔n〕應(yīng)由以下兩部分所組成：一部分是從初始節(jié)點到節(jié)點n的最小代價，記為g*〔n〕；另一部分是從節(jié)點n到目的節(jié)點的最小代價，記為h*〔n〕，當問題有多個目的節(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é)點n的真正最小代價還沒有找到，故有g(shù)〔n〕≥g*〔n〕。

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

第一，g〔n〕是對g*〔n〕的估計，且g〔n〕＞0；

第二，h〔n〕是h*〔n〕的下界，即對恣意節(jié)點n均有h〔n〕≤h*〔n〕。

那么稱得到的算法為A*算法。12A*算法的有關(guān)特性。

1．A*算法的可納性

普通來說，對恣意一個形狀空間圖，當從初始節(jié)點到目的節(jié)點有途徑存在時，假設(shè)搜索算法能在有限步內(nèi)找到一條從初始節(jié)點到目的節(jié)點的最正確途徑，并在此途徑上終了，那么稱該搜索算法是可采用的。A*算法是可采用的。(證明略〕。

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

A*算法的搜索效率很大程度上取決于估價函數(shù)h〔n〕。普通來說，在滿足h〔n〕≤h*〔n〕的前提下，h〔n〕的值越大越好。h〔n〕的值越大，闡明它攜帶的啟發(fā)性信息越多，A*算法搜索時擴展的節(jié)點就越少，搜索效率就越高。A*算法的這一特性也稱為信息性。(證明略)13A*算法運用舉例

例：八數(shù)碼難題。問題的初始形狀和目的形狀和前例一樣。要求用A*算法處理該問題。

解：在上例中，我們?nèi)〔n〕=W〔n〕。雖然我們對h*〔n〕不能確切知道，但當采用單位代價時，經(jīng)過對“不在位〞數(shù)碼個數(shù)的估計，可以得出至少要挪動W〔n〕步才干到達目的，顯然有W〔n〕≤h*〔n〕。因此，前例中所定義的h〔n〕滿足A*算法的限制條件。

這里再取另外一種啟發(fā)函數(shù)h〔n〕=P〔n〕，P〔n〕定義為每一個數(shù)碼與其目的位置之間間隔〔不思索夾在其間的數(shù)碼〕的總和，同樣可以斷定至少要挪動P〔n〕步才干到達目的，因此有P〔n〕≤h*〔n〕，即滿足A*算法的限制條件。2384765523847611428314765h*=4,f=4S023184765283164752831476528314765g*=12318476523184765g*=21238476512378465Sgg*=4h*=5,f=6h*=5,f=6h*=3,f=4h*=5,f=6h*=2,f=4h*=4,f=612384765g*=3h*=1,f=4h*=0,f=4h*=1,f=6八數(shù)碼難題h〔n〕=P〔n〕的搜索樹15例：設(shè)有如下構(gòu)造的挪動將牌游戲B代表黑色牌，W代表達色牌；E代表該位置為空。玩法：當一個牌移入相鄰的空位時，費用等于挑過的牌數(shù)加1。一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數(shù)加1。要求把一切的B都移到一切的W的右邊，設(shè)計h(x)。解：顯然W左邊的B越少越接近目的，因此可用W左邊B的個數(shù)作為h(x)h(x)=3*(每個W左邊B個數(shù)的總和〕h(x)=3*(2+2+3)=21BBBWWWEBBBWWWE16例：傳教士和野人問題。請用A*算法處理該問題。

解：用m表示左岸的傳道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)，用三元組〔m，c，b〕表示問題的形狀。

對A*算法，首先需求確定估價函數(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é)點的深度。經(jīng)過分析可知h〔n〕＜h*(n)，滿足A*算法的限制條件。

M-C問題的搜索過程如下頁圖所示。在該圖中，每個節(jié)點旁邊還標出了該節(jié)點的h值和f值。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)18194.4與/或樹的盲目搜索20概念:直接可解的簡單問題稱為本原問題，本原問題對應(yīng)的節(jié)點稱為終止節(jié)點，在與或圖〔樹〕中無子節(jié)點的節(jié)點稱為端節(jié)點，一個節(jié)點的子節(jié)點假設(shè)是“與〞關(guān)系，那么該節(jié)點便稱為與節(jié)點，一個節(jié)點的子節(jié)點假設(shè)是“或〞關(guān)系，那么該節(jié)點便稱為或節(jié)點。留意，終止節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終止節(jié)點?？山庑耘袆e(1)一個節(jié)點是可解，那么節(jié)點須滿足以下條件之一:①終止節(jié)點是可解節(jié)點；②一個與節(jié)點可解，當且僅當其子節(jié)點全都可解；③一個或節(jié)點可解，只需其子節(jié)點至少有一個可解。(2)一個節(jié)點是不可解，那么節(jié)點須滿足以下條件之一:①非終止節(jié)點的端節(jié)點是不可解節(jié)點；②一個與節(jié)點不可解，只需其子節(jié)點至少有一個不可解；③一個或節(jié)點不可解，當且僅當其子節(jié)點全都不可解。21一.與/或樹的普通搜索與/或樹的搜索過程實踐上是一個不斷尋覓解樹的過程。其普通搜索過程如下：

〔1〕把原始問題作為初始節(jié)點S0，并把它作為當前節(jié)點；

〔2〕運用分解或等價變換操作對當前節(jié)點進展擴展；

〔3〕為每個子節(jié)點設(shè)置指向父節(jié)點的指針；

〔4〕選擇適宜的子節(jié)點作為當前節(jié)點，反復(fù)執(zhí)行第〔2〕步和第〔3〕步，在此期間需求多次調(diào)用可解標志過程或不可解標志過程，直到初始節(jié)點被標志為可解節(jié)點或不可解節(jié)點為止。

上述搜索過程將構(gòu)成一棵與/或樹，這種由搜索過程構(gòu)成的與/或樹稱為搜索樹。當搜索勝利時，經(jīng)可解標志過程標識的由初始節(jié)點及其下屬的可解節(jié)點構(gòu)成的子樹稱為解樹。用與/或樹法表示的問題求解過程與形狀空間法類似，也是經(jīng)過搜索來實現(xiàn)對問題求解的。與/或樹的搜索戰(zhàn)略也分為盲目搜索和啟發(fā)式搜索兩大類。22搜索過程中的可解標志過程與不可解標志過程都是自下而上進展的，即由子節(jié)點的可解性確定父節(jié)點、祖父節(jié)點的可解性；由子節(jié)點的不可解性確定父節(jié)點、祖父節(jié)點的不可解性。在與/或樹中，除端節(jié)點和終止節(jié)點外，一個節(jié)點的可解性完全是由其子節(jié)點來決議的。對與節(jié)點，只需其一切子節(jié)點都為可解時它才為可解，只需有一個子節(jié)點不可解它就是不可解的；對或節(jié)點，只需有一個子節(jié)點可解它就是可解的，僅當一切子節(jié)點都是不可解時它才為不可解。這種由可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點為可解節(jié)點的過程稱為可解標志過程；由不可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點為不可解節(jié)點的過程稱為不可解標志過程。

由于與/或樹搜索的目的是尋覓解樹，因此，假設(shè)搜索過程確定某個節(jié)點為可解節(jié)點，那么其不可解的后裔節(jié)點就可從搜索樹中刪去；同樣，假設(shè)搜索過程能確定某個節(jié)點為不可解節(jié)點，那么其后裔節(jié)點也可從搜索樹中刪去。23與形狀空間的廣度優(yōu)先搜索類似，只是在搜索過程中需求多次調(diào)用可解標志過程或不可解標志過程，其搜索算法如下：

〔1〕把初始節(jié)點S0放人Open表中；

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

〔3〕假設(shè)節(jié)點n可擴展，那么做以下任務(wù)：

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

②調(diào)查這些子節(jié)點中能否有終止節(jié)點。假設(shè)有，那么標志這些終止節(jié)點為可解節(jié)點，并用可解標志過程對其父節(jié)點及先輩節(jié)點中的可解節(jié)點進展標志。假設(shè)初始解節(jié)點S0可以被標志為可解節(jié)點，就得到了解樹，搜索勝利，退出搜索過程；假設(shè)不能確定S0為可解節(jié)點，那么從Open表中刪去具有可解先輩的節(jié)點；

③轉(zhuǎn)第〔2〕步。二.與/或樹的廣度優(yōu)先搜索24〔4〕假設(shè)節(jié)點n不可擴展，那么做以下任務(wù)：

①標志節(jié)點n為不可解節(jié)點；

②運用不可解標志過程對節(jié)點n的先輩中不可解的節(jié)點進展標志。假設(shè)初始解節(jié)點S0也被標志為不可解節(jié)點，那么搜索失敗，闡明原始問題無解，退出搜索過程；假設(shè)不能確定S0為不可解節(jié)點，那么從Open表中刪去具有不可解先輩的節(jié)點；

③轉(zhuǎn)第〔2〕步。25例：設(shè)有如以下圖所示的與/或樹，節(jié)點按圖中所標注的順序號進展擴展，其中標有t1、t2、t3的節(jié)點是終止節(jié)點，A、B、C為不可解的端節(jié)點。

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

〔1〕先擴展1號節(jié)點，生成2號節(jié)點和3號節(jié)點，由于這兩個子節(jié)點都不是終止節(jié)點，因此接著擴展2號節(jié)點?！?〕擴展2號節(jié)點，生成A節(jié)點和4號節(jié)點。由于這兩個子節(jié)點均不是終止節(jié)點，因此接著擴展3號節(jié)點。〔3〕擴展3號節(jié)點，生成t1節(jié)點和5號節(jié)點。由于t1為終止節(jié)點，那么標志它為可解節(jié)點，并運用可解標志過程，對其先輩中的可解節(jié)點進展標志，由于t1的父節(jié)點是一個與節(jié)點，因此不能確定3號節(jié)點能否可解?！?〕擴展節(jié)點A，由于A是端節(jié)點，調(diào)用不可解標志過程，由于2號節(jié)點是或節(jié)點，因此不能確定2號節(jié)點是不可解節(jié)點。〔5〕擴展4號節(jié)點，生成t2節(jié)點和B節(jié)點。由于t2為終止節(jié)點，那么標志它為可解節(jié)點，并運用可解標志過程，標志4號節(jié)點為可解節(jié)點，標志2號節(jié)點為可解節(jié)點，但不能標志1號節(jié)點為可解節(jié)點。〔6〕擴展5號節(jié)點，生成t3節(jié)點和C節(jié)點。由于t3為終止節(jié)點，標志它為可解節(jié)點，并運用可解標志過程，標志5號節(jié)點為可解節(jié)點，標志3號節(jié)點為可解節(jié)點。標志1號節(jié)點為可解節(jié)點?！?〕搜索勝利，得到由1、2、3、4、5號節(jié)點及t1、t2、t3節(jié)點構(gòu)成的解樹。該解樹如上圖中的粗線所示。26可以帶有深度限制dm，其搜索算法如下：

〔1〕把初始節(jié)點S0放入Open表中；

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

〔3〕假設(shè)節(jié)點n的深度等于dm，那么轉(zhuǎn)第〔5〕步的第①點；

〔4〕假設(shè)節(jié)點n可擴展，那么做以下任務(wù)：

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

②調(diào)查這些子節(jié)點中能否有終止節(jié)點。假設(shè)有，那么標志這些終止節(jié)點為可解節(jié)點，并用可解標志過程對其父節(jié)點及先輩節(jié)點中的可解節(jié)點進展標志。假設(shè)初始節(jié)點S0可以被標志為可解節(jié)點，就得到了解樹，搜索勝利，退出搜索過程；假設(shè)不能確定S0為可解節(jié)點，那么從Open表中刪去具有可解先輩的節(jié)點；

③轉(zhuǎn)第〔2〕步。三.與/或樹的深度優(yōu)先搜索27〔5〕假設(shè)節(jié)點n不可擴展，那么做以下任務(wù)：

①標志節(jié)點n為不可解節(jié)點；

②運用不可解標志過程對節(jié)點n的先輩中不可解的節(jié)點進展標志。假設(shè)初始節(jié)點S0也被標志為不可解節(jié)點，那么搜索失敗，闡明原始問題無解，退出搜索過程；假設(shè)不能確定為不可解節(jié)點，那么從Open表中刪去具有不可解先輩的節(jié)點；

③轉(zhuǎn)第〔2〕步。

與/或樹的深度優(yōu)先搜索123A4t1t3CBt25例如，對上例所給出的與／或樹，假設(shè)按有界深度優(yōu)先搜索，且給定dm=4，那么其擴展節(jié)點的順序為：

1，3，5，2，4

其解樹與上例一樣。28與/或樹的盲目搜索是按確定道路進展的，當要選擇一個節(jié)點進展擴展時，只是根據(jù)節(jié)點在與/或樹中所處的位置，而沒有思索要付出的代價，因此求得的解樹不一定是代價最小的解樹，即不一定是最優(yōu)解樹。因此，需求思索與/或樹的啟發(fā)式搜索。在討論與／或樹的啟發(fā)式搜索過程之前，需求先討論幾個有關(guān)的概念。

一.解樹的代價與希望樹

與／或樹的啟發(fā)式搜索過程是一種利用搜索過程所得到的啟發(fā)性信息尋覓最優(yōu)解樹的過程。對搜索的每一步，算法都試圖找到一個最有希望成為最優(yōu)解樹的子樹。最優(yōu)解樹是指代價最小的那棵解樹。4.5與/或樹的啟發(fā)式搜索291．解樹的代價

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

〔1〕假設(shè)n為終止節(jié)點，那么其代價h〔n〕=0。

〔2〕假設(shè)n為或節(jié)點，且子節(jié)點為n1，n2，…，nk，那么n的代價為h〔n〕=min{c〔n，ni〕＋h〔ni〕}(1≤i≤k)其中，c〔n，ni〕是節(jié)點n到其子節(jié)點ni的邊代價。〔3〕假設(shè)n為與節(jié)點，且子節(jié)點為n1，n2，…，nk，那么n的代價可用和代價法或最大代價法。

假設(shè)用和代價法，那么其計算公式為：h〔n〕=Σ((c(n，ni)＋h(ni))i=1,2,……,k

假設(shè)用最大代價法，那么其計算公式為：

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

〔4〕假設(shè)n是端節(jié)點，但又不是終止節(jié)點，那么n不可擴展，其代價定義為h〔n〕=∞

〔5〕根節(jié)點的代價即為解樹的代價。30例：設(shè)右圖是一棵與/或樹，其中包括兩棵解樹，左邊的解樹由S0、A、t1、C及t3組成；右邊的解樹由S0、B、t2、D及t4組成。在此與/或樹中，t1、t2、t3、t4為終止節(jié)點；E、F是端節(jié)點；邊上的數(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)解樹。但在有些情況下，當采用的代價法不同時，找到的最優(yōu)解樹有能夠不同。312．希望樹

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

〔1〕初始節(jié)點S0在希望樹T中；

〔2〕假設(shè)n是具有子節(jié)點n1，n2，…，nk的或節(jié)點，那么n的某個子節(jié)點ni在希望樹T中的充分必要條件是

h〔n〕=min{c〔n，ni〕＋h〔ni〕}1≤i≤k

〔3〕假設(shè)n是與節(jié)點，那么n的全部子節(jié)點都在希望樹T中。32與／或樹的啟發(fā)式搜索需求不斷地選擇、修正希望樹，其搜索過程如下：

〔1〕把初始節(jié)點S0放入Open表中，計算h〔S0〕；

〔2〕計算希望樹T；

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

〔4〕假設(shè)節(jié)點n為終止節(jié)點，那么做以下任務(wù)：

①標志節(jié)點n為可解節(jié)點；

②在T上運用可解標志過程，對n的先輩節(jié)點中的一切可解節(jié)點進展標志；

③假設(shè)初始節(jié)點S0可以被標志為可解節(jié)點，那么T就是最優(yōu)解樹，勝利退出；

④否那么，從Open表中刪去具有可解先輩的一切節(jié)點；

⑤轉(zhuǎn)第〔2〕步。二.與/或樹的啟發(fā)式搜索過程33〔5〕假設(shè)節(jié)點n不是終止節(jié)點，但可擴展，那么做以下任務(wù)：

①擴展節(jié)點n，生成n的一切子節(jié)點；

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

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

④轉(zhuǎn)第〔2〕步。

〔6〕假設(shè)節(jié)點n不是終止節(jié)點，且不可擴展，那么做以下任務(wù)：

①標志節(jié)點n為不可解節(jié)點；

②在T上運用不可解標志過程，對n的先輩節(jié)點中的一切不可解節(jié)點進展標志；

③假設(shè)初始節(jié)點S0可以被標志為不可解節(jié)點，那么問題無解，失敗退出；

④否那么，從Open表中刪去具有不可解先輩的一切節(jié)點；

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

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

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

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

解：為了對葉節(jié)點進展靜態(tài)估值，規(guī)定估價函數(shù)e〔P〕如下：

假設(shè)P是MAX的必勝局，那么e〔P〕=+∞；

假設(shè)P是MIN的必勝局，那么e〔P〕=-∞；一字棋棋盤假設(shè)P對MAX、MIN都是勝負未定局，那么e〔P〕=e〔+P〕－e〔-P〕

其中，e〔+P〕表示棋局P上有能夠使×成三子一線的數(shù)目；e〔-P〕表示棋局P上有能夠使○成三子一線的數(shù)目。40例如，對圖1所示的棋局有估價函數(shù)值e〔P〕＝6-4＝2圖1棋局1在搜索過程中，具有對稱性的棋局以為是同一棋局。例如，圖2所示的棋局可以以為是同一個棋局，這樣可以大大減少搜索空間。圖3給出了第一著走棋以后生成的博弈樹。圖中葉節(jié)點下面的數(shù)字是該節(jié)點的靜態(tài)估值，非葉節(jié)點旁邊的數(shù)字是計算出的倒推值。從圖中可以看出，對MAX來說S2是一著最好的走棋，它具有較大的倒推值。圖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極大極小值算法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上述極大極小過程是先生成與/或樹，然后再計算各節(jié)點的估值，這種生成節(jié)點和計算估值相分別的搜索方式，需求生成規(guī)定深度內(nèi)的一切節(jié)點，因此搜索效率較低。假設(shè)能邊生成節(jié)點邊對節(jié)點估值，從而可以剪去一些沒用的分枝，這種技術(shù)稱為α-β剪枝過程。三.α-β剪枝<=23S0DEFABC5332對于一個與節(jié)點來說，它取當前子節(jié)點中的最小倒推值作為它倒推值的上界，稱該值為β值。對于一個或節(jié)點來說，它取當前子節(jié)點中的最大倒推值作為它倒推值的下界，稱該值為α值。44α-β剪枝的方法如下：

〔1〕MAX節(jié)點的α值為當前子節(jié)點的最大倒推值；

〔2〕MIN節(jié)點的β值為當前子節(jié)點的最小倒推值；

〔3〕α-β剪枝的規(guī)那么如下：

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

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

三.α-β剪枝≥αmin≤βmax≥α45S0ABCDFGHEIJKLMNPQRS4861580-64≥4≤1≤4＝45≥5＝4≥4≥0＝0≤-6＝0≤0＝4＊＊＊＊＊α-β剪枝的例子T446S00-330031653-322-3-254-3089-347S00-330031653-322-3-254-