第一章搜索問題內(nèi)容： 狀態(tài)空間的搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問題： 如何利用知識(shí)，盡可能有效地找到問題的解（最佳解）。1搜索問題（續(xù)1）S0Sg問題全狀態(tài)空間搜索空間解路徑2搜索問題（續(xù)2）討論的問題：有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。31.1回溯策略例：皇后問題4()5()Q((1,1))6()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2,4))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))11()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))15()((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))16()((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))17回溯策略屬于盲目搜索的一種?；厮莶呗允沁@樣一種策略：

首先將規(guī)則給出一個(gè)固定排序，在搜索時(shí)，對當(dāng)前狀態(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)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前的狀態(tài)。重復(fù)以上搜索，直到找到問題的解。回溯策略18遞歸的思想回溯有多種實(shí)現(xiàn)方法,其中遞歸是一種最直接的實(shí)現(xiàn)方法.從前有座山……從前有座山……

從前有座山……19回溯搜索算法 遞歸過程：BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。20回溯搜索算法遞歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;//滿足結(jié)束條件時(shí)返回2, IFDEADEND(DATA)RETURNFAIL;//不合法狀態(tài)的回溯點(diǎn)3, RULES:=APPRULES(DATA);//可應(yīng)用規(guī)則集4, LOOP:IFNULL(RULES)RETURNFAIL;//全部規(guī)則均失敗的回溯點(diǎn)5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);//刪去第一條規(guī)則，減少可應(yīng)用規(guī)則表的長度7, RDATA:=GEN(R,DATA);//調(diào)用規(guī)則R作用于當(dāng)前狀態(tài)，生成新狀態(tài)8, PATH:=BACKTRACK(RDATA);//對新狀態(tài)遞歸調(diào)用9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);//返回解路徑規(guī)則表21遞歸的思想（續(xù)）當(dāng)前狀態(tài)n目標(biāo)狀態(tài)tr1r2ri-1rim1m2mi-1mi22存在問題及解決辦法解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)問題：深度問題死循環(huán)問題23一些深入問題在回溯策略中，也可以引入一些與問題有關(guān)的信息來加快搜索解的速度。 基本思想(以皇后問題為例)：

盡可能選取劃去對角線上位置數(shù)最少的。QQQQ322324回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。25回溯搜索算法11,DATA:=FIRST(DATALIST)//設(shè)置DATA為當(dāng)前狀態(tài)2,IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL; //TAIL取尾操作，取DATALIST中除第一個(gè)以外的所有元素，如果DATA在TAIL(DATALIST）中存在，則說明有回路，返回FAIL，必須回溯.3,IFTERM(DATA)RETURNNIL;//找到目標(biāo)，結(jié)束4,IFDEADEND(DATA)RETURNFAIL;//狀態(tài)不合法，返回FAIL，必須回溯.5,IFLENGTH(DATALIST)>BOUND RETURNFAIL;//LENGTH計(jì)算DATALIST的長度，即搜索深度，當(dāng)搜索深度大于BOUND值時(shí)，搜索失敗，返回FAIL，必須回溯.6,RULES:=APPRULES(DATA);//APPRULES計(jì)算DATA的可應(yīng)用規(guī)則集，依某種原則（任意排列或啟發(fā)式排列）排列后附給RULES.7,LOOP:IFNULL(RULES)RETURNFAIL;//規(guī)則用完沒找到目標(biāo)，返回FAIL,必須回溯。26回溯搜索算法1（續(xù)）8, R:=FIRST(RULES);//取第一條規(guī)則9, RULES:=TAIL(RULES);//刪去第一條規(guī)則，減少可應(yīng)用規(guī)則表的長度10,RDATA:=GEN(R,DATA);//調(diào)用規(guī)則R作用于當(dāng)前狀態(tài)，生成新狀態(tài)11,RDATALIST:=CONS(RDATA,DATALIST);//將新狀態(tài)加入到表DATALIST中12,PATH:=BACKTRCK1(RDATALIST)//遞歸調(diào)用本過程13,IFPATH=FAILGOLOOP;//遞歸調(diào)用失敗，轉(zhuǎn)移調(diào)用另一規(guī)則進(jìn)行測試14,RETURNCONS(R,PATH);//返回解路徑規(guī)則表27分析這個(gè)算法與BACKRACK的差別是遞歸過程自變量是狀態(tài)的鏈表。在過程BACKRACK1中，形參DATALIST是從初始狀態(tài)到當(dāng)前狀態(tài)的逆序表，即初始狀態(tài)排在表的最后，當(dāng)前狀態(tài)排在表的最前面。在第2、5步增設(shè)了兩個(gè)回溯點(diǎn)以檢驗(yàn)是否重新訪問已出現(xiàn)過的狀態(tài)和限定搜索深度范圍。

281.2圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

29一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1012330一些基本概念（續(xù)1）路徑 設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對于i=1,…,k，若任一節(jié)點(diǎn)ni-1都具有一個(gè)后繼節(jié)點(diǎn)ni，則該節(jié)點(diǎn)序列稱為從n0到nk的長度為k的一條路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值.路徑耗散值可按如下遞推公式計(jì)算：

C(ni,t)=C(ni,nj)+C(nj,t)31一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。32一般的圖搜索算法1,G=G0(G0=s),OPEN:=(s);//設(shè)置open表,最初只含有初始點(diǎn)s2,CLOSED:=();//設(shè)置closed表,初始為空表3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);//n為當(dāng)前節(jié)點(diǎn)5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);

//子節(jié)點(diǎn)集{mi}中不包含n的父輩節(jié)點(diǎn)33一般的圖搜索算法（續(xù)）7,標(biāo)記和修改指針：

ADD(mj,OPEN),并標(biāo)記mj到n的指針；//mj為open表和closed表中未出現(xiàn)過的子結(jié)點(diǎn)

計(jì)算是否要修改mk、ml到n的指針；

//mk為已出現(xiàn)在open表中的子結(jié)點(diǎn)，ml為已出現(xiàn)在closed表中的子結(jié)點(diǎn)，{mj}={mj}∪{mk}∪{ml}

計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；

8,對OPEN中的節(jié)點(diǎn)按某種原則重新排序；9,GOLOOP；34說明這里給出的是一個(gè)圖搜索的一般框架，不是一個(gè)具體的算法，關(guān)鍵是算法的第8步，按不同的原則對OPEN表進(jìn)行排序，將得到不同的圖搜索算法。

算法中有兩個(gè)表：OPEN表和CLOSED表。其中OPEN表記錄的是已經(jīng)被生成出來，但還沒有被擴(kuò)展的節(jié)點(diǎn)；CLOSED表記錄的是已經(jīng)被擴(kuò)展過的節(jié)點(diǎn)。

35幾類節(jié)點(diǎn)的圖例說明如上圖所示，假設(shè)n是當(dāng)前被擴(kuò)展的節(jié)點(diǎn)。在n被擴(kuò)展之前，節(jié)點(diǎn)mk和ml已經(jīng)被生成出來了，其中mk還沒有被擴(kuò)展，他們在OPEN表中，而ml已經(jīng)被擴(kuò)展了，他們在CLOSED表中。當(dāng)n被擴(kuò)展時(shí)，它生成了節(jié)點(diǎn)mi，mi由mj、mk和ml三部分組成，其中mj是新出現(xiàn)的節(jié)點(diǎn)。36算法解釋圖搜索算法，簡單地說就是，每次從OPEN表中取出第一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展，生成的新節(jié)點(diǎn)放到OPEN表中，然后按照某種原則對OPEN表進(jìn)行排序。不同的排序原則構(gòu)成了不同的圖搜索算法。值得注意的是算法成功結(jié)束的判斷方法，是當(dāng)從OPEN表中取出一個(gè)節(jié)點(diǎn)后，再判斷該節(jié)點(diǎn)是否是目標(biāo)節(jié)點(diǎn)，而不是在擴(kuò)展節(jié)點(diǎn)，生成新節(jié)點(diǎn)時(shí)判斷。這一點(diǎn)一定要注意，在后面將可以看到，這是構(gòu)成某些最優(yōu)算法的關(guān)鍵所在。37算法解釋這個(gè)過程是在第8步要對OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便在第4步能選出一個(gè)“最好”的節(jié)點(diǎn)優(yōu)先擴(kuò)展。不同的排序方法便可構(gòu)成形式多樣的專門搜索算法，這在后面還要進(jìn)一步討論。如果選出待擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則算法在第5步成功結(jié)束，并可根據(jù)回溯到s的指針給出解路徑。如果某個(gè)循環(huán)中，搜索樹不再剩有待選的節(jié)點(diǎn)，即OPEN表變空時(shí)，則過程失敗結(jié)束，問題找不到解。

38算法解釋現(xiàn)在說明一下第7步中標(biāo)記和修改指針的問題。如果要搜索的隱含圖是一棵樹，則可肯定第6步生成的后繼節(jié)點(diǎn)不可能是以前生成過的，這時(shí)搜索圖就是搜索樹，不存在mk、ml這種類型的子節(jié)點(diǎn)，因此不必進(jìn)行修改指針的操作。如果要搜索的隱含圖不是一棵樹，則有可能出現(xiàn)這樣的子節(jié)點(diǎn)，就是說這時(shí)又發(fā)現(xiàn)了到達(dá)的新通路，這樣就要比較不同路徑的耗散值，把指針修改到具有較小耗散值的路徑上。39例如，下圖所示的兩個(gè)搜索圖中，實(shí)心圓點(diǎn)在CLOSED表中（已擴(kuò)展過的節(jié)點(diǎn)），空心圓點(diǎn)則在OPEN表中（待擴(kuò)展點(diǎn)）。先設(shè)下一步輪到要擴(kuò)展節(jié)點(diǎn)6，并設(shè)生成的兩個(gè)子節(jié)點(diǎn)，其中有一個(gè)4已在OPEN中，那么原先路徑（s→3→2→4）耗散值為5（設(shè)每段路徑均為單位耗散），新路徑（s→6→4）的耗散值為4，所以4的指針應(yīng)由指向2修正到指向6，如圖2.5（a）所示。接著設(shè)下一循環(huán)要擴(kuò)展節(jié)點(diǎn)1，若節(jié)點(diǎn)1只生成一個(gè)子節(jié)點(diǎn)2（它已在CLOSED上），顯然這時(shí)節(jié)點(diǎn)2原先指向節(jié)點(diǎn)3的指針，要修改到指向節(jié)點(diǎn)1，由此又引起子節(jié)點(diǎn)3的指針又修改為指向2，如圖2.5（b）所示。401.3無信息圖搜索過程無信息圖搜索屬于盲目搜索，這里給兩種常用的無信息圖搜索方法：深度優(yōu)先搜索寬度優(yōu)先搜索41所謂深度優(yōu)先搜索，就是在每次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，選擇到目前為止深度最深的節(jié)點(diǎn)優(yōu)先擴(kuò)展。第7步中的ADD（mj，OPEN）表示將被擴(kuò)展節(jié)點(diǎn)n的所有新子節(jié)點(diǎn)mj加到OPEN表的前面。開始時(shí)，OPEN表中只有一個(gè)初始節(jié)點(diǎn)s，s被擴(kuò)展，其子節(jié)點(diǎn)被放入OPEN表中。在算法的第3步，OPEN表的第一個(gè)元素(設(shè)為n)被取出擴(kuò)展，這時(shí)節(jié)點(diǎn)n的深度在OPEN表中是最大的，OPEN表中的其他節(jié)點(diǎn)的深度都不會(huì)超過n的深度。n的子節(jié)點(diǎn)被放到OPEN表的最前面。由于子節(jié)點(diǎn)的深度要大于父節(jié)點(diǎn)的深度，實(shí)際上OPEN表是按照節(jié)點(diǎn)的深度進(jìn)行排序的，深度深的節(jié)點(diǎn)被排在了前面，而深度淺的節(jié)點(diǎn)被放在了后面。這樣當(dāng)下一個(gè)循環(huán)再次取出OPEN表的第一個(gè)元素時(shí)，實(shí)際上選擇的就是到目前為止深度最深的節(jié)點(diǎn)，從而實(shí)現(xiàn)了深度優(yōu)先的搜索策略。42一般情況下，當(dāng)問題有解時(shí)，深度優(yōu)先搜索不但不能保證找到最優(yōu)解，也不能保證一定能找到解。如果問題的狀態(tài)空間是有限的，則可以保證找到解，當(dāng)問題的狀態(tài)空間是無限的時(shí)，則可能陷入"深淵"，而找不到解。為此，像回溯算法一樣，可以加上對搜索的深度限制。其方法是在算法的第7步，當(dāng)節(jié)點(diǎn)的深度達(dá)到限制深度時(shí)，則不將其子節(jié)點(diǎn)加入到OPEN表中，從而實(shí)現(xiàn)對搜索深度的限制。當(dāng)然，這個(gè)深度限制應(yīng)該設(shè)置的合適，深度過深影響搜索的效率，而深度過淺，則可能影響找到問題的解。

43回溯和深度優(yōu)先的區(qū)別在有些書上所講的深度優(yōu)先實(shí)際上指的是我們這里所說的回溯策略，在本書中還是將二者區(qū)分開來。從形式上來說，二者確實(shí)很相似，所表現(xiàn)出來的都是每次選擇深度最深的節(jié)點(diǎn)首先擴(kuò)展。但二者還是有區(qū)別的，這里所說的深度優(yōu)先屬于圖搜索策略，不足是占用較多的存儲(chǔ)空間，好處是對于特殊的問題，可能會(huì)提高搜索的效率。44設(shè)某問題的狀態(tài)空間如圖所示。從圖中可以看出該問題的特點(diǎn)：初始節(jié)點(diǎn)有若干個(gè)子節(jié)點(diǎn)，每個(gè)子節(jié)點(diǎn)都鏈接到三條很深的路徑中，而目標(biāo)假定在最右邊的路徑中。當(dāng)采用回溯策略時(shí)，由于回溯策略只保留從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的一條路徑，所以從第一個(gè)子節(jié)點(diǎn)（從左數(shù)）進(jìn)入第一條路徑搜索（從左遍數(shù)），回溯后，又進(jìn)入第二條路徑。由于沒有找到解，又回溯到第二個(gè)子節(jié)點(diǎn)。從第二個(gè)子節(jié)點(diǎn)，同樣要搜索第一條路徑、第二條路徑。第三個(gè)字節(jié)點(diǎn)、第四個(gè)子節(jié)點(diǎn)……也都同樣。這樣，第一和第二條路徑將被多次搜索，影響了搜索的效率。而對于深度優(yōu)先策略（單指這里所說的圖搜索深度優(yōu)先），由于保留了所有已經(jīng)搜索過的路徑，當(dāng)通過第一個(gè)節(jié)點(diǎn)搜索了第一、第二條路徑后，當(dāng)通過第二個(gè)子節(jié)點(diǎn)搜索時(shí)，由于第一、第二條路徑已經(jīng)被搜索，并且被記錄了，所以就不必重復(fù)搜索了，提高了搜索的效率。這一點(diǎn)在算法中是如何體現(xiàn)出來的呢？關(guān)鍵是算法的第7步，在n的子節(jié)點(diǎn)中，只將mj類節(jié)點(diǎn)加入到了OPEN表中，而對于mk類節(jié)點(diǎn)和ml類節(jié)點(diǎn)則不予考慮。

45深度優(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;46231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)47深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個(gè)通用的與問題無關(guān)的方法48寬度優(yōu)先搜索同深度優(yōu)先算法一樣，寬度優(yōu)先算法也是從一般的圖搜索算法變化而成。在深度優(yōu)先搜索中，每次選擇深度最深的節(jié)點(diǎn)首先擴(kuò)展，而寬度優(yōu)先搜索則正好相反，每次選擇深度最淺的節(jié)點(diǎn)優(yōu)先擴(kuò)展。與深度優(yōu)先算法不同的只是第7步，這里ADD（OPEN，mj）表示將mj類子節(jié)點(diǎn)放到OPEN表的后邊，從而實(shí)現(xiàn)了對OPEN表中的元素按節(jié)點(diǎn)深度排序，只不過這次將深度淺的節(jié)點(diǎn)放在OPEN表的前面了，而深度深的節(jié)點(diǎn)被放在了OPEN表的后邊。當(dāng)問題有解時(shí)，寬度優(yōu)先算法不但能一定找到解，而且在單位耗散的情況下，可以保證找到最優(yōu)解。49寬度優(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;5023184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)823418765451寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時(shí)，一定能找到解當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法521.4啟發(fā)式圖搜索利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解53希望：引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。54基本思想啟發(fā)式搜索過程中，要對OPEN表進(jìn)行排序，這就需要有一種方法來計(jì)算待擴(kuò)展節(jié)點(diǎn)有希望通向目標(biāo)節(jié)點(diǎn)的不同程度，我們總是希望能找到最有希望通向目標(biāo)節(jié)點(diǎn)的待擴(kuò)展節(jié)點(diǎn)優(yōu)先擴(kuò)展。一種最常用的方法是定義一個(gè)評(píng)價(jià)函數(shù)f（Evaluationfunction）對各個(gè)子節(jié)點(diǎn)進(jìn)行計(jì)算，其目的就是用來估算出“有希望”的節(jié)點(diǎn)來。定義一個(gè)評(píng)價(jià)函數(shù)可以參考的原則有：一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率；求出任意一個(gè)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)集之間的距離度量或差異度量；根據(jù)格局（博弈問題）或狀態(tài)的特點(diǎn)來打分。即根據(jù)問題的啟發(fā)信息，從概率角度、差異角度或記分法給出計(jì)算評(píng)價(jià)函數(shù)的方法。551.啟發(fā)式搜索算法A（A算法）啟發(fā)式搜索算法A，一般簡稱為A算法，是一種典型的啟發(fā)式搜索算法。其基本思想是：定義一個(gè)評(píng)價(jià)函數(shù)f，對當(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ù)56符號(hào)的意義g*(n)：從s到n的最短路徑的耗散值h*(n)：從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值,是一種預(yù)測。A算法就是利用這種預(yù)測，來達(dá)到有效搜索的目的的。它每次按照f(n)值的大小對OPEN表中的元素進(jìn)行排序，f值小的節(jié)點(diǎn)放在前面，而f值大的節(jié)點(diǎn)則被放在OPEN表的后面，這樣每次擴(kuò)展節(jié)點(diǎn)時(shí)，都是選擇當(dāng)前f值最小的節(jié)點(diǎn)來優(yōu)先擴(kuò)展。57A算法利用評(píng)價(jià)函數(shù)f（n）＝g（n）＋h（n）來排列OPEN表節(jié)點(diǎn)順序的圖搜索算法稱為A算法。58A算法過程

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},//{mi}={mj}∪{mk}∪{ml}

①計(jì)算f(n,mi):=g(n,mi)+h(mi);

//g（n，mi）是從s通過n到mi的耗散值，f（n，mi）是從s通過n、mi到目標(biāo)節(jié)點(diǎn)耗散值的估計(jì)。

59A算法（續(xù)）

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

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

//比較f（n,mk）和f（mk），f（mk）是擴(kuò)展n之前計(jì)算的耗散值。

④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；60A算法同樣由一般的圖搜索算法改變而成。在算法的第7步，按照f值從小到大對OPEN表中的節(jié)點(diǎn)進(jìn)行排序，體現(xiàn)了A算法的含義。算法要計(jì)算f(n)、g(n)和h(n)的值，g(n)根據(jù)已經(jīng)搜索的結(jié)果，按照從初始節(jié)點(diǎn)s到節(jié)點(diǎn)n的路徑，計(jì)算這條路徑的耗散值就可以了。而h(n)是與問題有關(guān)的，需要根據(jù)具體的問題來定義。有了g(n)和h(n)的值，將他們加起來就得到f(n)的值。注意A算法的結(jié)束條件：當(dāng)從OPEN中取出第一節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則算法成功結(jié)束。而不是在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，只要目標(biāo)節(jié)點(diǎn)一出現(xiàn)就立即結(jié)束。我們在后面將會(huì)看到，正是由于有了這樣的結(jié)束判斷條件，才使得A算法有很好的性質(zhì)。61算法中f（n）規(guī)定為對從初始節(jié)點(diǎn)s出發(fā)，約束通過節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)t，最小耗散值路徑的耗散值f*(n)的估計(jì)值，通常取正值。f（n）由兩個(gè)分量組成，其中g(shù)（n）是到目前為止，從s到n的一條最小耗散值路徑的耗散值，是作為從s到n最小耗散值路徑的耗散值g*(n)的估計(jì)值，h（n）是從n到目標(biāo)節(jié)點(diǎn)t，最小耗散值路徑的耗散值h*(n)的估計(jì)值。

62一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)： f(n)=g(n)+h(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值 h(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)

283164751238476563h計(jì)算舉例 h(n)=42

831

64751234576

8642831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)12345665根據(jù)目標(biāo)節(jié)點(diǎn)L返回到s的指針，可得解路徑S(4)，B(4)，E(5)，I(5)，K(5)，L(5)662．爬山法爬山法（局部搜索算法）672．爬山法過程Hill-climbing

①n:=s；s為初始節(jié)點(diǎn)

②LOOP：IFGOAL（n）THENEXIT(SUCCESS)；

③EXPAND（n）→{mi}，計(jì)算h(mi)，nextn:=m(minh(mi)的節(jié)點(diǎn))；

④IFh(n)<h(nextn)THENEXIT(FAIL);

⑤n:=nextn；

⑥GOLOOP；

顯然如果將山頂作為目標(biāo)，h(n)表示山頂與當(dāng)前位置n之間高度之差，則該算法相當(dāng)于總是登向山頂，在單峰的條件下，必能到達(dá)山峰。683．分支界限法分支界限法是優(yōu)先擴(kuò)展當(dāng)前具有最小耗散值分支路徑的端節(jié)點(diǎn)n，其評(píng)價(jià)函數(shù)為f(n)=g(n)。該算法的基本思想很簡單，實(shí)際上是建立一個(gè)局部路徑（或分支）的隊(duì)列表，每次都選耗散值最小的那個(gè)分支上的端節(jié)點(diǎn)來擴(kuò)展，直到生成出含有目標(biāo)節(jié)點(diǎn)的路徑為止。

69過程Branch-Bound

①Q(mào)UEUE:=(s-s)，g(s)=0;

②LOOP：IFQUEUE=()THENEXIT(FAIL);

③PATH:=FIRST(QUEUE)，n:=LAST(PATH);

④IFGOAL(n)THENEXIT(SUCCESS);

⑤EXPAND(n)→{mi}，計(jì)算g(mi)=g(n，mi)，REMOVE（s-n，QUEUE），ADD(s-mi，QUEUE);

⑥QUEUE中局部路徑g值最小者排在前面；

⑦GOLOOP；70應(yīng)用分支界限法求下圖的最短路徑，求解過程中QUEUE的結(jié)果簡記如下（D(4)代表耗散值為4的s-D分支，其余類推）：g=771初始（s(0)）

1.（A（3）D（4））

2.（D（4）B（7）D（8））

3.（E（6）B（7）D（8）A（9））

4.（B（7）D（8）A（9）F（10）B（11））

5.（D（8）A（9）F（10）B（11）C（11）E（12））

6.（A（9）E（10）F（10）B（11）C（11）E（12））

7.（E（10）F（10）B（11）C（11）E（12）B（13））

8.（F（10）B（11）C（11）E（12）B（13）F（14）B（15））

9.（B（11）C（11）E（12）t（13）B（13）F（14）B（15））

10.（C（11）E（12）t（13）B（13）F（14）A（15）B（15）C（15））

11.（E（12）t（13）B（13）F（14）A（15）B（15）C（15））

12.（t（13）B（13）F（14）D（14）A（15）B（15）C（15）F（16））

13.結(jié)束。724．動(dòng)態(tài)規(guī)劃法在A算法中，當(dāng)h(n)≡0時(shí)，則A算法演變?yōu)閯?dòng)態(tài)規(guī)劃算法。由于在A算法中，很多問題的啟發(fā)函數(shù)h難于定義，因此動(dòng)態(tài)規(guī)劃算法是至今一直被經(jīng)常使用的算法。734．動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法實(shí)際上是對分支界限法的改進(jìn)。從圖2.9看出，第二循環(huán)擴(kuò)展A（3）后生成的D（8）節(jié)點(diǎn)（D（4）已在QUEUE上）和第三循環(huán)擴(kuò)展D（4）之后生成的A（9）節(jié)點(diǎn)（A（3）已以QUEUE上）都是多余的分支，因?yàn)橛蓅－D到達(dá)目標(biāo)的路徑顯然要比s－A－D到達(dá)目標(biāo)的路徑要好。因此刪去類似于s－A－D或s－D－A這樣一些多余的路徑將會(huì)大大提高搜索效率。動(dòng)態(tài)規(guī)劃原理指出，求s→t的最佳路徑時(shí)，對某一個(gè)中間節(jié)點(diǎn)I，只要考慮s到I中最小耗散值這一條局部路徑就可以，其余s到I的路徑是多余的，不必加以考慮。74動(dòng)態(tài)規(guī)劃st第一階段第二階段第三階段第四階段第五階段754．動(dòng)態(tài)規(guī)劃法過程Dynamic-Programming

①Q(mào)UEUE:=(s-s)，g(s)=0;

②LOOP：IFQUEUE=（）THENEXIT(FAIL);

③PATH:=FIRST(QUEUE)，n:=LAST(PATH);

④IFGOAL(n)THENEXIT(SUCCESS);

⑤EXPAND(n)→{mi}，計(jì)算g(mi)=g(n，mi)，REMOVE（s-n，QUEUE），ADD(s-mi，QUEUE);

⑥若QUEUE中有多條到達(dá)某一公共節(jié)點(diǎn)的路徑，則只保留耗散值最小的那條路徑，其余刪去，并重新排序，g值最小者排在前面；

⑦GOLOOP；

765.最佳圖搜索算法A*（OptimalSearch）當(dāng)在算法A的評(píng)價(jià)函數(shù)中，使用的啟發(fā)函數(shù)h(n)是處在h﹡（n）的下界范圍，即滿足h(n)≤h*(n)時(shí)，則我們把這個(gè)算法稱為算法A﹡。775.A*算法A﹡算法實(shí)際上是分支界限和動(dòng)態(tài)規(guī)劃原理及使用下界范圍的h相結(jié)合的算法。當(dāng)問題有解時(shí)，A﹡一定能找到一條到達(dá)目標(biāo)節(jié)點(diǎn)的最佳路徑。例如在極端情況下，若h(n)≡0（肯定滿足下界范圍條件），因而一定能找到最佳路徑;若g≡d，則算法等同于寬度優(yōu)先算法。前面已提到過，寬度優(yōu)先算法能保證找到一條到達(dá)目標(biāo)節(jié)點(diǎn)最小長度的路徑，因而這個(gè)特例從直觀上就驗(yàn)證了A﹡的一般結(jié)論。一般地說對任意一個(gè)圖，當(dāng)s到目標(biāo)節(jié)點(diǎn)有一條路徑存在時(shí)，如果搜索算法總是在找到一條從s到目標(biāo)節(jié)點(diǎn)的最佳路徑上結(jié)束，則稱該搜索算法是可采納的（Admissibility）。A﹡就具有可采納性。78對于以下的定理、引理和推論，我們只要求掌握其結(jié)論和含義，不要求掌握其具體的證明過程。但是證明過程有助于你對算法的理解。以下定理的證明，正文部分是嚴(yán)格的，而解釋部分，則不是嚴(yán)格的證明，只是從直觀上，或者從思路上進(jìn)行說明。在以下的定理證明過程中，要明確這樣幾個(gè)關(guān)系：

f*(s)=f*(t)=h*(s)，其中s是初始節(jié)點(diǎn)，t是目標(biāo)節(jié)點(diǎn)（有時(shí)也用g表示）。當(dāng)n是從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)t的最優(yōu)路徑上的節(jié)點(diǎn)時(shí)，

f*(n)=f*(s)=f*(t)=h*(s)。5.A*算法79A*算法的性質(zhì)（續(xù)1）定理1.1： 對有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。證明：設(shè)A搜索失敗，則算法在第2步結(jié)束，OPEN表變空，而CLOSED表中的節(jié)點(diǎn)是在結(jié)束之前被擴(kuò)展過的節(jié)點(diǎn)。由于圖有解，令（n0=s，n1，n2，…，nk=t）表示某一解路徑，我們從nk開始逆向逐個(gè)檢查該序列的節(jié)點(diǎn)，找到出現(xiàn)在CLOSED表中的節(jié)點(diǎn)ni，即niCLOSED，ni+1CLOSED（ni一定能找到，因?yàn)閚0CLOSED，nkCLOSED）。由于ni在CLOSES中，必定在第6步被擴(kuò)展，且ni+1被加到OPEN中，因此在OPEN表空之前，ni+1已被處理過。若ni+1是目標(biāo)節(jié)點(diǎn)，則搜索成功，否則它被加入到CLOSED中，這兩種情況都與搜索失敗的假設(shè)矛盾，因此對有限圖不失敗則成功。[證畢]

80A*算法的性質(zhì)（續(xù)2）引理1.1：對無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。該引理的證明中，隱含了兩個(gè)假設(shè)：（1）任何兩個(gè)節(jié)點(diǎn)之間的耗散值都大于某個(gè)給定的大于零的常量；（2）h(n)對于任何n來說，都大于等于零。

由于當(dāng)問題有解存在時(shí)，從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑的耗散值總是一個(gè)有限的常量。那么在該解路徑上的任何一個(gè)節(jié)點(diǎn)n，由于f(n)=g(n)+h(n)，而g(n)是有限的，h(n)≤h*(n)也是有限的（因?yàn)閔*(n)有限），所以f(n)也是有限的。而對于一個(gè)無限圖來說，那些不在解路徑上的無限路徑，隨著搜索的進(jìn)行，其耗散值總會(huì)趨于無窮大，因此那些在解路徑上的節(jié)點(diǎn)的f值總會(huì)變得最小，總會(huì)有機(jī)會(huì)被排在OPEN表的第一個(gè)位置，從而被A*擴(kuò)展。而目標(biāo)節(jié)點(diǎn)也是解路徑上的一個(gè)節(jié)點(diǎn)，這樣它同樣會(huì)有機(jī)會(huì)被排在OPEN表的第一個(gè)位置，從而使得算法成功結(jié)束，找到問題的解路徑。81A*算法的性質(zhì)（續(xù)2）引理1.2：對無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。證明：設(shè)d﹡(n)是A﹡生成的搜索樹中，從s到任一節(jié)點(diǎn)n最短路徑長度的值（設(shè)每個(gè)弧的長度均為1），搜索圖上每個(gè)弧的耗散值為C(ni，ni+1)（C取正）。令e=minC(ni，ni+1)，則g﹡(n)≥d﹡(n)e。而g(n)≥g﹡(n)≥d﹡(n)e，故有：

f(n)=g(n)+h(n)≥g(n)≥d﹡(n)e（設(shè)h(n)≥0）

若A﹡不結(jié)束，d﹡(n)趨向于∞，f值將增到任意大。

82A*算法的性質(zhì)（續(xù)2）該引理可以這樣來理解：如果問題從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)g的路徑存在時(shí)，則一定有一個(gè)最短路徑存在。在A*沒有結(jié)束之前，OPEN表中的節(jié)點(diǎn)不會(huì)為空。由于總是從OPEN表中取出節(jié)點(diǎn)來擴(kuò)展，所以最優(yōu)路徑肯定要通過OPEN表中的某個(gè)節(jié)點(diǎn)，設(shè)該節(jié)點(diǎn)為n。那么n有兩個(gè)特點(diǎn)，一是n是從s到g的最優(yōu)路徑上的節(jié)點(diǎn)，二是到目前為止已經(jīng)找到了從s到n的最優(yōu)路徑。第一點(diǎn)會(huì)比較容易接受，第二點(diǎn)是如何保證的呢？如果到目前為止找到的不是從s到n的最優(yōu)路徑，同樣的理由，在OPEN表中一定有一個(gè)節(jié)點(diǎn)--假定為n'--在從s到n的最優(yōu)路徑上，當(dāng)然他也一定在從s到g的最優(yōu)路徑上。用n'來代替n，重復(fù)下去，一直找到滿足以上兩個(gè)特點(diǎn)的n為止。當(dāng)然，我們不一定明確的知道到底OPEN表中的哪個(gè)節(jié)點(diǎn)滿足這樣的特點(diǎn)，但從以上的敘述可以知道，這樣的節(jié)點(diǎn)一定存在。

對于具有這樣特點(diǎn)的n，由于以上所說的第一個(gè)特點(diǎn)有g(shù)(n)=g*(n)，所以有f(n)=g*(n)+h(n)，而由于算法是A*的，所以有h(n)≤h*(n)，所以f(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)。對于最后一個(gè)等式，是由于對于任何兩個(gè)最優(yōu)路徑上的節(jié)點(diǎn)n1和n2，都有f*(n1)=f*(n2)，而n和s都是最優(yōu)路徑上的節(jié)點(diǎn)。引理1.2得證。

83A*算法的性質(zhì)（續(xù)3）引理1.3： A*結(jié)束前，OPEN表中必存在f(n)≤f*(s)的節(jié)點(diǎn)（n是在最佳路徑上的節(jié)點(diǎn)）

。證明：設(shè)從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的一條最佳路徑序列為：

(n0=s，n1，…，nk=t)

算法初始化時(shí)，s在OPEN中，由于A﹡沒有結(jié)束，在OPEN中存在最佳路徑上的節(jié)點(diǎn)。設(shè)OPEN表中的某節(jié)點(diǎn)n是處在最佳路徑序列中（至少有一個(gè)這樣的節(jié)點(diǎn)，因s一開始是在OPEN上），顯然n的先輩節(jié)點(diǎn)np已在CLOSED中，因此能找到s到np的最佳路徑，而n也在最佳路徑上，因而s到n的最佳路徑也能找到，因此有

f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)

而最佳路徑上任一節(jié)點(diǎn)均有f*（n）=f*(s)（f*(s)是最佳路徑的耗散值），所以f(n)≤f*(s)。[證畢]84A*算法的性質(zhì)（續(xù)3）定理1.2： 對無限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*一定成功結(jié)束。證明：假定A*不結(jié)束，由引理2.1有f(n)＞f*(s)，或OPEN表中最小的一個(gè)f值也變成無界，這與引理2.2的結(jié)論矛盾，所以A*只能成功結(jié)束。[證畢]85A*算法的性質(zhì)（續(xù)4）推論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ò)展。得證。86A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。87可采納性的證明由定理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é)束條件88A*算法的性質(zhì)（續(xù)6）推論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)。得證。89A*算法的性質(zhì)（續(xù)7）定理1.4：設(shè)對同一個(gè)問題定義了兩個(gè)A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對所有非目標(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ù)90A*算法的性質(zhì)（續(xù)7）注意：

在定理1.4中，評(píng)價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說，同一個(gè)節(jié)點(diǎn)無論被擴(kuò)展多少次，都只計(jì)算一次。91定理1.4的證明使用數(shù)學(xué)歸納法，對節(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中。92定理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件矛盾。故定理得證。933，A*算法的改進(jìn)問題的提出： 因A算法第6步對ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。94s(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)95出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G目標(biāo)63111896解決的途徑對h加以限制能否對h增加適當(dāng)?shù)南拗疲沟玫谝淮螖U(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。對算法加以改進(jìn)能否對算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。97改進(jìn)的條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法的復(fù)雜性98對h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對所有節(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)的。h(ni)ninjh(nj)c(ni,nj)99h單調(diào)的性質(zhì)定理1.5： 若h(