第一章搜索問題

第一章搜索問題

搜索是人工智能中的一個(gè)基本問題，并與推理密切相關(guān)，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。

1內(nèi)容： 狀態(tài)空間的搜索問題搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問題： 如何利用知識(shí)，盡可能有效地找到問題的解（最佳解）。2基本概念1.什么是搜索？

根據(jù)問題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的求解路線，使問題得到圓滿解決的過程稱為搜索。2.盲目搜索盲目搜索是按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策略。3基本概念

啟發(fā)式搜索是在搜索中加入了與問題有關(guān)的啟發(fā)式信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。

3.啟發(fā)式搜索

由于搜索總是按預(yù)先規(guī)定的路線進(jìn)行，沒有考慮到問題本身的特性，所以這種搜索具有盲目性，效率不高，不便于復(fù)雜問題的求解。啟發(fā)式搜索優(yōu)于盲目搜索。但由于啟發(fā)式搜索需要具有與問題本身特性有關(guān)的信息，而這并非對(duì)每一類問題都可方便地抽取出來,因此盲目搜索仍不失為一種應(yīng)用較多的搜索策略。

41.1狀態(tài)空間表示法

狀態(tài)空間表示法是人工智能中最基本的形式化方法，是討論問題求解技術(shù)的基礎(chǔ)。狀態(tài)空間表示法是用“狀態(tài)”和“算符”來表示問題的一種方法。其中“狀態(tài)”用以描述問題求解過程中不同時(shí)刻的狀況；“算符”表示對(duì)狀態(tài)的操作，算符的每一次使用就使問題由一種狀態(tài)變換為另一種狀態(tài)。當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就是問題的一個(gè)解。

51.狀態(tài)

狀態(tài)是描述問題求解過程中任一時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu)，一般用一組變量或多維數(shù)組Sk=(Sk0,Sk1,…,Skn)表示，當(dāng)給每個(gè)分量以確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)。2.算符

引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作稱為算符。操作可以是一個(gè)機(jī)械的步驟、過程、規(guī)則或算子，指出了狀態(tài)之間的關(guān)系。63.狀態(tài)空間

由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間，一般用一個(gè)三元組表示：（S,F,G）其中S是問題求解過程中所有可達(dá)的合法狀態(tài)構(gòu)成的集合；F是算符的集合；G是目標(biāo)狀態(tài)的集合。問題的狀態(tài)空間可以用一個(gè)賦值有向圖來表示，稱為狀態(tài)空間圖。其中，節(jié)點(diǎn)表示狀態(tài)；有向邊（弧）表示算符。

7傳教士與野人問題

例：設(shè)N個(gè)傳教士帶領(lǐng)N個(gè)野人劃船渡河，且為安全起見，渡河需遵循兩個(gè)約束：（1）船上的人數(shù)不得超過載重限量，設(shè)為K個(gè)人；（2）為預(yù)防野人攻擊，任何時(shí)刻（包括兩岸、船上）野人數(shù)目不得超過傳教士數(shù)目。應(yīng)如何規(guī)劃渡河方案？為便于理解狀態(tài)空間表示法，可簡化該問題到一個(gè)特例：N=3，K=2。8解：首先選取描述問題狀態(tài)的方法。在這個(gè)問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。從而可用一個(gè)三元組來表示狀態(tài)S=(m,c,b)其中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。右岸的狀態(tài)可由下式確定：右岸修道士數(shù)m'=3-m右岸野人數(shù)c'=3-c右岸船數(shù)b'=1-b在這種表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32種狀態(tài)。9

這32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)，有意義的狀態(tài)只有16種：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了這些狀態(tài)，還需要考慮可進(jìn)行的操作。

操作是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。每個(gè)操作都應(yīng)當(dāng)滿足如下條件：

一是船至少有一個(gè)人（m或c）操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的m和c的增加數(shù)目；二是每次操作船上人數(shù)不得超過2個(gè)；三是操作應(yīng)保證不產(chǎn)生非法狀態(tài)。因此，操作應(yīng)由條件部分和動(dòng)作部分：條件：只有當(dāng)其條件具備時(shí)才能使用動(dòng)作：刻劃了應(yīng)用此操作所產(chǎn)生的結(jié)果。

10操作的表示：

用符號(hào)Pij表示從左岸到右岸的運(yùn)人操作用符號(hào)Qij表示從右岸到左岸的操作其中：i表示船上的修道士人數(shù)j表示船上的野人數(shù)操作集本問題有10種操作可供選擇：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}下面以P01和Q01為例來說明這些操作的條件和動(dòng)作。操作符號(hào)條件動(dòng)作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=0,m=0或3，c≤2b=1,c=c+1

11

于是，從初始狀態(tài)出發(fā)，可畫出該問題的狀態(tài)空間有向圖，見圖1.1。

o(220)(110)oo(021)111020110102(331)o01o(320)o(321)o(311)o(221)(031)o02o(010)(011)o01o(000)0201020120011011o(310)o(300)o(020)o(111)

圖1.1傳教士與野人問題的狀態(tài)空間圖

12二階梵塔問題設(shè)用Sk=(Sk0,Sk1)表示問題的狀態(tài)，Sk0表示金片A所在鋼針號(hào)，Sk1表示金片B所在鋼針號(hào)，全部可能的狀態(tài)有九種：S0=(1,1),S1=(1,2),S2=(1,3)S3=(2,1),S4=(2,2),S5=(2,3)S6=(3,1),S7=(3,2),S8=(3,3)13

ABABAB123123123二階梵塔問題的初始狀態(tài)和目標(biāo)狀態(tài)問題的初始狀態(tài)集合為S={S0}目標(biāo)狀態(tài)集合為G={S4,S5}

初始狀態(tài)S0和目標(biāo)狀態(tài)S4、S8如圖所示

S0=(1,1)S4=(2,2)S8=(3,3)14操作分別用A(i,j)和B(i,j)表示A(i,j)表示把金片A從第i號(hào)鋼針移到j(luò)號(hào)鋼針上；B(i,j)表示把金片B從第i號(hào)鋼針一到第j號(hào)鋼針上。共有12種操作，它們分別是：A(1,2)A(1,3)A(2,1)A(2,3)A(3,1)A(3,2)B(1,2)B(1,3)B(2,1)B(2,3)B(3,1)B(3,2)根據(jù)上述9種可能的狀態(tài)和12種操作，可構(gòu)成二階梵塔問題的狀態(tài)空間圖，如下圖所示。15(3,3)(1,3)(1,2)(2,2)二階梵塔的狀態(tài)空間圖從初始節(jié)點(diǎn)(1,1)到目標(biāo)節(jié)點(diǎn)(2,2)及(3,3)的任何一條路徑都是問題的一個(gè)解。其中，最短的路徑長度是3，它由3個(gè)操作組成。例如，從(1,1)開始，通過使用操作A(1,3)、B(1,2)及A(3,2)，可到達(dá)(3,3)。A(1,2)B(1,3)A(2,3)(1,1)(3,1)(3,2)(2,1)(2,3)A(1,3)B(1,2)A(3,2)16狀態(tài)空間表示法的幾點(diǎn)說明

用狀態(tài)空間方法表示問題時(shí)，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可把問題的一切狀態(tài)都表示出來。其次，還要定義一組算符，通過使用算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。問題的求解過程是一個(gè)不斷把算符作用于狀態(tài)的過程。如果在使用某個(gè)算符后得到的新狀態(tài)是目標(biāo)狀態(tài)，就得到了問題的一個(gè)解。這個(gè)解是從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。

17

算符的一次使用，就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。可能有多個(gè)算符序列都可使問題從初始狀態(tài)變到目標(biāo)狀態(tài)，這就得到了多個(gè)解。把其中使用算符最少的解稱為最優(yōu)解。例如在上例中，問題有無數(shù)條解答路徑(因?yàn)閯澊僮骺赡?,但只有4個(gè)最優(yōu)解，都包含了11個(gè)操作算子。這只是從解中算符的個(gè)數(shù)來評(píng)價(jià)解的優(yōu)劣，今后將會(huì)看到評(píng)價(jià)解的優(yōu)劣不僅要看使用算符的數(shù)量，還要看使用算符時(shí)所付出的耗散值，只有總耗散值最小的解才是最優(yōu)解。18

對(duì)任何一個(gè)狀態(tài)，可使用的算符可能不止一個(gè)，這樣由一個(gè)狀態(tài)所生成的后繼狀態(tài)就可能有多個(gè)。當(dāng)對(duì)這些后繼狀態(tài)使用算符生成更進(jìn)一步的狀態(tài)時(shí)，首先應(yīng)對(duì)哪個(gè)狀態(tài)進(jìn)行擴(kuò)展呢？這取決于搜索策略，不同的搜索策略的擴(kuò)展順序是不同的，這正是本章要討論的問題。

除了少數(shù)像“傳教士與野人”這樣的簡單的問題外，描述狀態(tài)空間的圖一般都很大，無法直觀地畫出，只能將其視為隱含圖，在搜索解答路徑的過程中只畫出搜索時(shí)直接涉及到的節(jié)點(diǎn)和弧線，構(gòu)成所謂的搜索圖。狀態(tài)空間、搜索圖和解答路徑之間的關(guān)系，可以用下圖表示。19狀態(tài)空間、搜索圖和解答路徑的關(guān)系圖

S0Sg問題全部狀態(tài)空間搜索空間解路徑20搜索問題（續(xù)）討論的問題：有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。211.2回溯策略

回溯策略是一種試探性策略，屬于盲目搜索的一種。它首先將規(guī)則給出一個(gè)固定的排序，在搜索時(shí)，對(duì)當(dāng)前狀態(tài)（搜索開始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測每一條規(guī)則，在當(dāng)前狀態(tài)未使用過的規(guī)則中找到第一條可應(yīng)用規(guī)則，應(yīng)用于當(dāng)前狀態(tài)，得到的新狀態(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索。如果當(dāng)前狀態(tài)無規(guī)則可用，或者所有規(guī)則已經(jīng)被試探過仍未找到問題的解，則將當(dāng)前狀態(tài)的前一狀態(tài)設(shè)置為當(dāng)前狀態(tài)。重復(fù)以上搜索，直到找到問題的解，或者試探了所有可能后仍找不到問題的解為止。22回溯策略的實(shí)現(xiàn)方法

回溯策略有多種實(shí)現(xiàn)的方法，其中遞歸法是一種最直接的實(shí)現(xiàn)方法。

下面定義一個(gè)遞歸過程BACKTRCK，實(shí)現(xiàn)回溯策略。其功能是：如果從當(dāng)前狀態(tài)DATA到目標(biāo)狀態(tài)有路徑存在，則返回以規(guī)則序列表示的從DATA到目標(biāo)狀態(tài)的路徑；如果從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)沒有路徑存在，則返回FAIL。23遞歸的思想從前有座山……從前有座山……

從前有座山……24回溯搜索算法 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。25回溯搜索算法的符號(hào)說明

DATA:變量，表示當(dāng)前狀態(tài)；TERM():謂詞函數(shù)，當(dāng)狀態(tài)變量DATA滿足結(jié)束條件時(shí)，TERM(DATA)取真。DEADEND():謂詞函數(shù)，當(dāng)狀態(tài)變量DATA為非法狀態(tài)時(shí)，DEADEND(DATA)取真.APPRULES():函數(shù)，計(jì)算出適用于DATA的規(guī)則集，并依據(jù)某種原則(任意排列或按啟發(fā)式準(zhǔn)則)排列后賦給RULES(規(guī)則集序列表)。26FIRST(RULES):函數(shù)，取出規(guī)則列表RULES中的第一條規(guī)則。TAIL(RULES):函數(shù)，刪去RULES中的第一條規(guī)則。GEN(R,DATA):函數(shù)，調(diào)用規(guī)則R作用于當(dāng)前狀態(tài)DATA，生成一個(gè)新的狀態(tài)RDATA。CONS(R,PATH):函數(shù)，構(gòu)造新表，把規(guī)則R加到當(dāng)前解路徑表的前頭。NIL:常量,表示空表；LOOP:常量,循環(huán)標(biāo)號(hào)；FAIL:常量，回溯點(diǎn)標(biāo)記；27回溯搜索算法遞歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);28遞歸的思想（圖）當(dāng)前狀態(tài)n目標(biāo)狀態(tài)gm1m2…mkmir1r2rkri29遞歸的思想(續(xù))遞歸過程BACKTRACK是將循環(huán)與遞歸結(jié)合在一起的。求從當(dāng)前狀態(tài)n到目標(biāo)狀態(tài)g的路徑，一是要探索n的i個(gè)子狀態(tài)m1,m2,…,mi中，通過哪一個(gè)子狀態(tài)可以到達(dá)目標(biāo)狀態(tài)g。這一點(diǎn)是通過循環(huán)實(shí)現(xiàn)的，每次從n的可應(yīng)用規(guī)則中，選一個(gè)規(guī)則rk(k=1,2,

…,i)作用于n，生成子狀態(tài)mk，體現(xiàn)的是“橫向”探索。二是“縱向”探索。為了探索n的某一個(gè)子狀態(tài)mk是否可以到達(dá)目標(biāo)狀態(tài)g，算法通過遞歸來完成，即把mk又當(dāng)成當(dāng)前狀態(tài)，探索mk的子狀態(tài)到g是否有路徑存在，如此進(jìn)行下去。30例：在一個(gè)4×4的國際象棋棋盤上，一次一個(gè)地?cái)[放4枚皇后棋子，擺好后要滿足：每行、每列和對(duì)角線上只允許出現(xiàn)一枚棋子。問如何擺放？四皇后問題不合法狀態(tài)合法狀態(tài)31

每個(gè)狀態(tài)由1至4個(gè)元素的集合構(gòu)成，每個(gè)元素可表示為一對(duì)數(shù)ij，1≤i，j≤4，表示在第i行第j列的一個(gè)棋子。例如上圖的兩個(gè)布局可表示為(11233144)和(12243143)。問題的初始狀態(tài)表示為()，問題的目標(biāo)狀態(tài)應(yīng)滿足問題的要求。

規(guī)則集:if1≤i≤4且Length(DATA)=i－1thenAPPEND(DATA(ij))(1≤j≤4)共有16條規(guī)則，每條規(guī)則Rij表示滿足前提條件下，在ij處放一棋子。規(guī)則按先行后列從小到大排列。32()33()Q((1,1))34()QQ((1,1))((1,1)(2,3))35()Q((1,1))((1,1)(2,3))36()QQ((1,1))((1,1)(2,3))((1,1)(2,4))37()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))38()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))39()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))40()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))41()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))42()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))43()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))44()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))45存在問題及解決辦法

解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)

問題：深度問題死循環(huán)問題46存在的問題深度問題:某些問題的某個(gè)(或某些)分支具有無窮個(gè)狀態(tài)，算法可能會(huì)落入某一個(gè)“深淵”，久遠(yuǎn)也回溯不回來，這樣，就不可能找到問題的解。死循環(huán)問題:某些問題在某一個(gè)分支上具有環(huán)路，搜索會(huì)在這個(gè)環(huán)路中一直進(jìn)行下去，同樣也回溯不出來，從而找不到問題的解。在前面的回溯算法BACKTRACK中，設(shè)置了兩個(gè)回溯點(diǎn)，一個(gè)是當(dāng)遇到非法狀態(tài)時(shí)回溯，一個(gè)是當(dāng)試探了一個(gè)狀態(tài)的所有子狀態(tài)后，仍然找不到解時(shí)回溯。47解決的辦法

為了解決這兩個(gè)問題，下面將給出回溯算法BACKTRACK1將增加兩個(gè)回溯點(diǎn)：一個(gè)是用一個(gè)常量BOUND來限制算法所能夠搜索的最大深度，當(dāng)當(dāng)前狀態(tài)的深度達(dá)到了限制深度時(shí)，算法將進(jìn)行回溯，從而可以避免可以落入“深淵”；另一個(gè)是將過程的參數(shù)用從初始狀態(tài)到當(dāng)前狀態(tài)的表來替代原來的當(dāng)前狀態(tài)，當(dāng)新的狀態(tài)產(chǎn)生時(shí)，查看是否已經(jīng)在該表中出現(xiàn)了。如果出現(xiàn)過，則表明有環(huán)路存在，算法將進(jìn)行回溯，從而解決了環(huán)路問題。48回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。49回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMEMBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);50回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);51一些深入的問題失敗原因分析、多步回溯QQ52一些深入問題（續(xù)）

回溯搜索中知識(shí)的利用

基本思想(以皇后問題為例):充分利用問題的信息對(duì)RULES中的操作排序，可獲得更高的效率。例如使用函數(shù)diag(i,j)，其定義是通過位置{ij}的最長的對(duì)角線的長度。如果diag(i,j)<diag(m,n)，則將Rij排在Rmn的前面，盡可能選取劃去對(duì)角線上位置數(shù)最少的，這時(shí)搜索過程只回溯了2次就找到了目標(biāo)狀態(tài)。QQQQ322353練習(xí)：八皇后問題541.3圖搜索策略問題的引出回溯搜索與圖搜索的區(qū)別是：

回溯搜索:只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。

圖搜索:保留所有已經(jīng)搜索過的路徑。55一般的圖搜索思想

首先把問題的初始狀態(tài)（即初始節(jié)點(diǎn)）作為當(dāng)前狀態(tài)，選擇適用的算符對(duì)其進(jìn)行操作，生成一組子節(jié)點(diǎn)，然后檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解；若不出現(xiàn)，則按某種搜索策略從已生成的子節(jié)點(diǎn)中再選一個(gè)作為當(dāng)前狀態(tài)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或不再有可供操作的狀態(tài)及算符時(shí)為止。56使用到的表OPEN表狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)CLOSED表編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)57一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1012358一些基本概念（續(xù)1）

路徑設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。

路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。59一些基本概念（續(xù)2）

擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。60一般圖搜索算法的符號(hào)說明

s---指示初始狀態(tài)節(jié)點(diǎn)；G---指示搜索圖；

OPEN---用于存放待擴(kuò)展節(jié)點(diǎn)的表；

CLOSE---用于存放已擴(kuò)展節(jié)點(diǎn)的表；

FIRST(OPEN)---指示取OPEN表首的節(jié)點(diǎn)作為當(dāng)前要被擴(kuò)展的節(jié)點(diǎn)n；REMOVE(n,OPEN)---將節(jié)點(diǎn)n從OPEN表中刪去；ADD(n,CLOSE)---把節(jié)點(diǎn)n加入到CLOSE表中；

EXPAND(n)---擴(kuò)展節(jié)點(diǎn)n。

61一般的圖搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);62一般的圖搜索算法（續(xù)）7,標(biāo)記和修改指針： ADD(mj,OPEN),并標(biāo)記mj到n的指針； 計(jì)算是否要修改mk、ml到n的指針； 計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；8,對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序；9,GOLOOP；63節(jié)點(diǎn)類型說明…...…...…...…...…...mjmkmln

全新節(jié)點(diǎn)，mj；

已出現(xiàn)于OPEN表的節(jié)點(diǎn)，如mk；

已出現(xiàn)于CLOSE表的節(jié)點(diǎn)，如ml；

64修改指針舉例123456s65123456修改指針舉例（續(xù)）s661.4無信息圖搜索過程

深度優(yōu)先搜索

寬度優(yōu)先搜索67一、深度優(yōu)先搜索過程1，把初始節(jié)點(diǎn)s放入OPEN表；2，若OPEN表為空，則問題無解，退出；3，把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSE表；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)放入到OPEN表的首部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。6869有界深度優(yōu)先搜索算法1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標(biāo)記mj到n的指針;10,GOLOOP;70重排九宮問題23184765

123847657123184765

23184765283147652318476528314765283164752831476528316475283164

7528371465

8321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)72有界深度優(yōu)先搜索的性質(zhì)

一般不能保證找到最優(yōu)解；

當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制；

最壞情況時(shí)，搜索空間等同于窮舉；與回溯法的差別：圖搜索是一個(gè)通用的、與問題無關(guān)的方法；73二、寬度優(yōu)先搜索過程

1，把初始節(jié)點(diǎn)s放入OPEN表；2，若OPEN表為空，則問題無解，退出；3，把OPEN表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入CLOSE表；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)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。74寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),

并標(biāo)記mj到n的指針;9,GOLOOP;75重排九宮問題23184765

123847657623184765

231847652831476523184765283147652831647528314765283164752831647528371465

832147652814376528314576123784651238476512567312384765目標(biāo)823418765477寬度優(yōu)先搜索的性質(zhì)

當(dāng)問題有解時(shí)，一定能找到解。

當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解。

方法與問題無關(guān)，具有通用性。

效率較低。

屬于圖搜索方法。78在3×3的方格棋盤上，分別放置了表有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0，目標(biāo)狀態(tài)Sg，如下圖所示。可以使用的操作有空格左移，空格上移，空格右移，空格下移即只允許把位于空格左、上、右、下方的牌移入空格。要求應(yīng)用寬度優(yōu)先和深度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。

831476512384765S0Sg練習(xí)79283147652831476523184765283147652831647583214765283714652318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg寬度優(yōu)先802831476528314765231847652831476528316475283164752831647528316754283167542816375428163754S0123456八數(shù)碼問題的深度優(yōu)先搜索如右圖一種改進(jìn)的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為dm深度優(yōu)先81漸進(jìn)式深度優(yōu)先搜索方法

目的

解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。

思想

首先給回溯法一個(gè)比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所有的分支為止。821.5啟發(fā)式圖搜索利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。

啟發(fā)信息的強(qiáng)度

強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解

弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎赡芸梢哉业阶顑?yōu)解83希望引入啟發(fā)知識(shí)，在保證找到最優(yōu)解的情況下，盡可能減少搜索范圍，提高搜索效率。84基本思想

定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。85定義評(píng)價(jià)函數(shù)的參考原則一個(gè)結(jié)點(diǎn)處在最佳路徑上的概率；求出任意一個(gè)結(jié)點(diǎn)與目標(biāo)結(jié)點(diǎn)集之間的距離度量或差異度量；根據(jù)格局（博弈問題）或狀態(tài)的特點(diǎn)來打分861啟發(fā)式搜索算法A（A算法）A算法的思想：定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的結(jié)點(diǎn)來擴(kuò)展。

評(píng)價(jià)函數(shù)的格式:f(n)=g(n)+h(n)

f(n):評(píng)價(jià)函數(shù)

h(n):啟發(fā)函數(shù)87符號(hào)的意義

g*(n):從初始結(jié)點(diǎn)s到結(jié)點(diǎn)n的最短路徑的耗散值；

h*(n):從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)g的最短路徑的耗散值；

f*(n)=g*(n)+h*(n):從初始結(jié)點(diǎn)s經(jīng)過結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)g的最短路徑的耗散值；

g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值。88A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},

計(jì)算f(n,mi):=g(n,mi)+h(mi); 89A算法（續(xù)）

ADD(mj,OPEN),標(biāo)記mj到n的指針；

IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),標(biāo)記mk到n的指針；

IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml),標(biāo)記ml到n的指針,ADD(ml,OPEN);7,OPEN中的節(jié)點(diǎn)按f值從小到大排序；8,GOLOOP；90…...…...…...…...…...mjmkmlnab91Closed表Open表92一個(gè)A算法的例子2831647512384765評(píng)價(jià)函數(shù)： f(n)=d(n)+W(n) d(n)為節(jié)點(diǎn)深度，取單位耗散值； W(n)為當(dāng)前節(jié)點(diǎn)“不在位”的牌數(shù)。 93w計(jì)算舉例 w(n)=42

831

64751234576

8w(n)=“不在位”的將牌數(shù)。942831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)123456f(n)=d(n)+w(n)952最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：h(n)≤h*(n)則A算法稱為A*算法。96A*條件舉例2

831

6475

1234576

8將牌1：1將牌2：1將牌6：1將牌8：2

8數(shù)碼問題h1(n)=w(n)=“不在位”的將牌數(shù)；h2(n)=p(n)=將牌“不在位”的距離和。97283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465s(5)A(7)B(5)C(7)D(6)E(5)F(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)12345f(n)=d(n)+p(n)98不同啟發(fā)函數(shù)下擴(kuò)展的結(jié)點(diǎn)數(shù)啟發(fā)函數(shù)h(n)=0h(n)=w(n)h(n)=p(n)擴(kuò)展結(jié)點(diǎn)數(shù)2665生成結(jié)點(diǎn)數(shù)46131199A*算法的性質(zhì)

幾個(gè)等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始節(jié)點(diǎn)，t是目標(biāo)節(jié)點(diǎn)，n是s到t的最佳路徑上的節(jié)點(diǎn)。

A*算法的假設(shè)

設(shè)ni、nj是任意兩個(gè)節(jié)點(diǎn)，有：C(ni,nj)>其中為大于0的常數(shù)100A*算法的性質(zhì)（續(xù)1）定理1.1: 對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。101證明：首先證明算法必定會(huì)結(jié)束由于搜索圖為有限圖，如果算法能找到解，則會(huì)成功結(jié)束；如果算法找不到解，則必然會(huì)由于Open表變空而結(jié)束。因此，A*算法必然會(huì)結(jié)束102然后證明算法一定會(huì)成功結(jié)束由于至少存在一條由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，設(shè)此路徑為s=n0，n1

，…，nk=t算法開始時(shí)，節(jié)點(diǎn)n0在Open表中，而且路徑中任一節(jié)點(diǎn)ni離開Open表后，其后繼節(jié)點(diǎn)ni+1必然進(jìn)入Open表，這樣，在Open表變?yōu)榭罩?，目?biāo)節(jié)點(diǎn)必然出現(xiàn)在Open表中因此，算法必定會(huì)成功結(jié)束103A*算法的性質(zhì)（續(xù)2）引理1.1: 對(duì)無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。104A*算法的性質(zhì)（續(xù)3）引理1.2: A*結(jié)束前，OPEN表中必存在f(n)≤f*(s)。存在一個(gè)節(jié)點(diǎn)n，n在最佳路徑上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)105A*算法的性質(zhì)（續(xù)4）定理1.2: 對(duì)無限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*一定成功結(jié)束。引理1.1:

A*如果不結(jié)束，則OPEN中所有的n有f(n)>f*(s)引理1.2:

在A*結(jié)束前，必存在節(jié)點(diǎn)n，使得f(n)≤f*(s)所以，如果A*不結(jié)束，將導(dǎo)致矛盾。106A*算法的性質(zhì)（續(xù)5）推論1.1： OPEN表上任一具有f(n)<f*(s)的節(jié)點(diǎn)n，最終都將被A*選作擴(kuò)展的節(jié)點(diǎn)。由定理1.2，知A*一定結(jié)束，由A*的結(jié)束條件，OPEN表中f(t)最小時(shí)才結(jié)束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)的n，均被擴(kuò)展。得證。107A*算法的性質(zhì)（續(xù)6）定理1.3(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。108可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結(jié)束設(shè)找到的路徑s→t不是最佳的（t為目標(biāo)）則：f(t)=g(t)>f*(s)由引理1.2知結(jié)束前OPEN中存在f(n)≤f*(s)的節(jié)點(diǎn)n，所以f(n)≤f*(s)<f(t)因此A*應(yīng)選擇n擴(kuò)展，而不是t。與假設(shè)A*選擇t結(jié)束矛盾。得證。注意：A*的結(jié)束條件109A*算法的性質(zhì)（續(xù)7）推論1.2： A*選作擴(kuò)展的任一節(jié)點(diǎn)n，有f(n)≤f*(s)。由引理2.2知在A*結(jié)束前，OPEN中存在節(jié)點(diǎn)n’，f(n’)≤f*(s)設(shè)此時(shí)A*選擇n擴(kuò)展。如果n＝n’，則f(n)≤f*(s)，得證。如果n≠n’，由于A*選擇n擴(kuò)展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。110A*算法的性質(zhì)（續(xù)8）定理1.4：設(shè)對(duì)同一個(gè)問題定義了兩個(gè)A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對(duì)所有非目標(biāo)節(jié)點(diǎn)有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時(shí)，由A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和A2一樣多。簡寫：如果h2(n)>h1(n)(目標(biāo)節(jié)點(diǎn)除外)，則A1擴(kuò)展的節(jié)點(diǎn)數(shù)≥A2擴(kuò)展的節(jié)點(diǎn)數(shù)111A*算法的性質(zhì)（續(xù)9）注意：

在定理1.4中，評(píng)價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說，同一個(gè)節(jié)點(diǎn)無論被擴(kuò)展多少次，都只計(jì)算一次。112定理1.4的證明使用數(shù)學(xué)歸納法，對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納（1）當(dāng)d(n)＝0時(shí)，即只有一個(gè)節(jié)點(diǎn)，顯然定理成立。（2）設(shè)d(n)≤k時(shí)定理成立。（歸納假設(shè)）（3）當(dāng)d(n)=k+1時(shí)，用反證法。設(shè)存在一個(gè)深度為k＋1的節(jié)點(diǎn)n，被A2擴(kuò)展，但沒有被A1擴(kuò)展。而由假設(shè)，A1擴(kuò)展了n的父節(jié)點(diǎn)，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時(shí)，n將被保留在OPEN中。113定理1.4的證明（續(xù)1）所以有：f1(n)≥f*(s)即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)另一方面，由于A2擴(kuò)展了n，有f2(n)≤f*(s)即：h2(n)≤f*(s)–g2(n)(A)由于d(n)=k時(shí)，A2擴(kuò)展的節(jié)點(diǎn)A1一定擴(kuò)展，有g(shù)1(n)≤g2(n)(因?yàn)锳2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比較A、B兩式，有h1(n)≥h2(n)，與定理?xiàng)l件矛盾。故定理得證。114對(duì)h的評(píng)價(jià)方法平均分叉樹 設(shè)共擴(kuò)展了d層節(jié)點(diǎn)，共搜索了N個(gè)節(jié)點(diǎn)，則:

其中，b*稱為平均分叉樹。b*越小，說明h效果越好。實(shí)驗(yàn)表明，b*是一個(gè)比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。115對(duì)h的評(píng)價(jià)舉例例：8數(shù)碼問題，隨機(jī)產(chǎn)生若干初始狀態(tài)。使用h1： d=14,N=539, b*=1.44;d=20,N=7276， b*=1.47；使用h2： d=14,N=113, b*=1.23; d=20,N=676, b*=1.27116A*的復(fù)雜性一般來說，A*的算法復(fù)雜性是指數(shù)型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時(shí)：

abs(h(n)-h*(n))≤O(log(h*(n)))

A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下，h與h*的差別至少是和離目標(biāo)的距離成正比的。1173，A*算法的改進(jìn)問題的提出：因A算法第6步對(duì)ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。118s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)119出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因s(10)A(1)B(5)C(8)G目標(biāo)631118

在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。120解決的途徑對(duì)h加以限制能否對(duì)h增加適當(dāng)?shù)南拗?，使得第一次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。對(duì)算法加以改進(jìn)能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。121改進(jìn)的條件

可采納性不變

不多擴(kuò)展節(jié)點(diǎn)

不增加算法的復(fù)雜性122對(duì)h加以限制h(ni)ninjh(nj)c(ni,nj)定義：一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有節(jié)點(diǎn)ni和nj，其中nj是ni的子節(jié)點(diǎn)，滿足 h(ni)-h(nj)≤c(ni,nj) h(t)=0或h(ni)≤c(ni,nj)+h(nj) h(t)=0則稱h是單調(diào)的。123h單調(diào)的性質(zhì)

定理1.5：

若h(n)是單調(diào)的，則A*擴(kuò)展了節(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的最佳路徑。 即：當(dāng)A*選n擴(kuò)展時(shí)，有g(shù)(n)=g*(n)。124定理1.5的證明設(shè)n是A*擴(kuò)展的任一節(jié)點(diǎn)。當(dāng)n＝s時(shí)，定理顯然成立。下面考察n≠s的情況。設(shè)P＝(n0=s,n1,n2,…,nk=n)是s到n的最佳路徑P中一定有節(jié)點(diǎn)在CLOSED中，設(shè)P中最后一個(gè)出現(xiàn)在CLOSED中的節(jié)點(diǎn)為nj，則nj+1在OPEN中。125定理1.5的證明（續(xù)1）由單調(diào)限制條件，對(duì)P中任意節(jié)點(diǎn)ni有：h(ni)≤C(ni,ni+1)+h(ni+1)

g*(ni)+h(ni)≤g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最佳路徑上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)帶入上式有：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)從i=j到i=k-1應(yīng)用上不等式，有：g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)

注意：(nj在CLOSED中，nj+1在OPEN中)126定理1.5的證明（續(xù)2）重寫上式：f(nj+1)≤g*(n)+h(n)另一方面，A*選n擴(kuò)展，必有：f(n)=g(n)+h(n)≤f(nj+1)比較兩式，有：

g(n)≤g*(n)但已知g*(n)是最佳路徑的耗散值，所以只有：g(n)=g*(n)。得證。127h單調(diào)的性質(zhì)（續(xù)）定理1.6：

若h(n)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。即f(ni)≤f(nj)。128定理1.6的證明由單調(diào)限制條件，有：h(ni)–h(nj)≤C(ni,nj)=f(ni)-g(ni)=f(nj)-g(nj)

f(ni)-g(ni)-f(nj)+g(nj)≤C(ni,nj)=g(ni)+C(ni,nj)

f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)

≤C(ni,nj)

f(ni)-f(nj)

≤0，得證。129h單調(diào)的例子

8數(shù)碼問題：h為“不在位”的將牌數(shù)1 h(ni)-h(nj)=0 (nj為ni的后繼節(jié)點(diǎn))-1 h(t)=0 c(ni,nj)=1滿足單調(diào)的條件130對(duì)算法加以改進(jìn)一些結(jié)論：OPEN表上任以具有f(n)<f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)≤f*(s)。131改進(jìn)的出發(fā)點(diǎn)OPEN=(…………)f*(s)f值小于f*(s)的節(jié)點(diǎn)f值大于等于f*(s)的節(jié)點(diǎn)

fm:

到目前為止已擴(kuò)展節(jié)點(diǎn)的最大f值，用fm代替f*(s)132修正過程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=()THENEXIT(FAIL);3,NEST:={ni|f(ni)<fm} IFNEST≠()THENn:=NEST中g(shù)最小的節(jié)點(diǎn) ELSEn:=FIRST(OPEN), fm:=f(n);4,…,8:同過程A。133s(10)A(1)B(5)C(8)G目標(biāo)631118OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)前面的例子134h的單調(diào)化方法如果令： f(n)=max(f(n的父節(jié)點(diǎn)),g(n)+h(n))則容易證明，這樣處理后的h是單調(diào)的。135IDA*算法(IterativeDeepeningA*)基本思想：回溯與A*的結(jié)合算法簡介（非嚴(yán)格地）1，設(shè)初始值f0；2，集合S＝NULL；3，用回溯法求解問題，如果節(jié)點(diǎn)n的f值大于f0，則將該節(jié)點(diǎn)放入集合S中，并回溯；4，如果在3中找到了解，則結(jié)束； 5，如果3以失敗結(jié)束，則f0＝S中節(jié)點(diǎn)的最小f值；6，返回到2。136A*算法應(yīng)用舉例P40八數(shù)碼問題傳教士和野人問題1374其他的搜索算法

爬山法（局部搜索算法）

分支界限法動(dòng)態(tài)規(guī)劃法138爬山法（圖示）139爬山法

在g(n)0的情況下，若限制只用評(píng)價(jià)函數(shù)f(n)=h(n)去排序新擴(kuò)展出來的子節(jié)點(diǎn)，即局部排序，就可實(shí)現(xiàn)較為簡單的搜索策略：爬山法。爬山法適用于能逐步求精的問題，對(duì)于單一及值問題十分有效，但對(duì)于具有多及值的問題就無能為力了。爬山法是實(shí)現(xiàn)啟發(fā)式搜索的最簡單方法,不需設(shè)置OPEN表和CLOSE表，因?yàn)闆]有必要保存任何待擴(kuò)展節(jié)點(diǎn)，僅從當(dāng)前狀態(tài)節(jié)點(diǎn)擴(kuò)展出的子節(jié)點(diǎn)中將h(n)最小的子節(jié)點(diǎn)作為下一次考察的節(jié)點(diǎn)，其余的節(jié)點(diǎn)全部丟棄。140爬山法(hill-climbing)—就是向值增加的方向持續(xù)移動(dòng)—登高過程/如果相鄰狀態(tài)中沒有比它更高的值，則算法結(jié)束于頂峰爬山法搜索算法思想：(1)令初始狀態(tài)S0為當(dāng)前狀態(tài)(2)若當(dāng)前狀態(tài)已經(jīng)達(dá)標(biāo)，則算法運(yùn)行結(jié)束，搜索成功(3)若存在一個(gè)動(dòng)作可以作用于當(dāng)前狀態(tài)以產(chǎn)生一個(gè)新狀態(tài)，使新狀態(tài)的估計(jì)值優(yōu)于當(dāng)前狀態(tài)的估計(jì)值，則放棄當(dāng)前狀態(tài)，并令剛產(chǎn)生的新狀態(tài)為當(dāng)前狀態(tài)，轉(zhuǎn)(2)(4)取當(dāng)前狀態(tài)為相對(duì)最優(yōu)解，停止執(zhí)行算法141爬山算法Hill-climbing1,n=s;//s為初始節(jié)點(diǎn)2,LOOP:IFGOAL(n)THENEXIT(SUCCESS);3,EXPAND(n){mi},計(jì)算h(mi),nextn:=m(minh(mi)的節(jié)點(diǎn));4,IFh(n)<h(nextn)THENEXIT(FAIL);5,n:=nextn;6,GOLOOP;142分支界限法（思想）

分支界限法是優(yōu)先擴(kuò)展當(dāng)前具有最小耗散值分支路徑的端節(jié)點(diǎn)n(沒有子節(jié)點(diǎn)的節(jié)點(diǎn))，其評(píng)價(jià)函數(shù)為f(n)=g(n)。該算法的基本思想很簡單，實(shí)際上是建立一個(gè)局部路徑（或分支）的隊(duì)列表，每次都選擇耗散值最小的那個(gè)分支上的端節(jié)點(diǎn)進(jìn)行擴(kuò)展，直到生成含有目標(biāo)節(jié)點(diǎn)的路徑為止。143分支界限算法

Branch-Bound1,QUEUE:=(s-s),g(s)=0;2,LOOP:IFQUEUE=()THENEXIT(FAIL);3,PATH:=FIRST(QUEUE),n:=LAST(PATH);4,IFGOAL(n)THENEXIT(SUCCESS);5,EXPAND(n){mi},計(jì)算g(mi)=g(n,mi),REMOVE(s-n,QUEUE),ADD(s-mi,QUEUE);6,QUEUE中局部路徑g值最小者排在前面；7,GOLOOP;144分支界限法例子sDAEBFtC432455434八城市交通圖例:求解右圖從城市s到城市t的最短路徑。145分支界限搜索樹sADBAFE1g=0g=3425g=73D6g=8C11g=11E12g=12EBg=47g=9g=6g=13B10g=11F9g=1