一章人工智能蔡自興

第一章搜索問題內容： 狀態(tài)空間的搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關鍵問題： 如何利用知識，盡可能有效地找到問題的解（最佳解）。1搜索問題題（續(xù)1）S0Sg問題全狀狀態(tài)空間間搜索空間間解路徑2搜索問題題（續(xù)2）討論的問問題：有哪些常常用的搜搜索算法法。問題有解解時能否否找到解解。找到的解解是最佳佳的嗎？？什么情況況下可以以找到最最佳解？？求解的效效率如何何。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ī)規(guī)則給出出一個固固定排序序，在搜搜索時，，對當前前狀態(tài)依依次檢查查每條規(guī)規(guī)則，在在當前狀狀態(tài)未使使用過的的規(guī)則中中找到第第一條可可應用規(guī)規(guī)則應用用于當前前狀態(tài)，，得到的的新狀態(tài)態(tài)設置為為當前狀狀態(tài)，并并重復以以上搜索索。如果當前前狀態(tài)無無規(guī)則可可用，或或者所有有規(guī)則已已經用過過仍未找找到問題題的解，，則將當當前狀態(tài)態(tài)的前一一個狀態(tài)態(tài)（即直直接生成成該狀態(tài)態(tài)的狀態(tài)態(tài)）設置置為當前前的狀態(tài)態(tài)。重復復以上搜搜索，直直到找到到問題的的解。回溯策略略18遞歸的思思想回溯有多多種實現現方法,,其中遞遞歸是一一種最直直接的實實現方法法.從前有座山……從前有座山……

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

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

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

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

29一些基本本概念節(jié)點深度度：根節(jié)點深深度=0其它節(jié)點點深度==父節(jié)點點深度++1012330一些基本本概念（（續(xù)1））路徑設一節(jié)點點序列為為(n0,n1,…,nk)，對于于i=1,…,,k，若若任一節(jié)節(jié)點ni-1都具有一一個后繼繼節(jié)點ni，則該節(jié)節(jié)點序列列稱為從從n0到nk的長度為為k的一一條路徑徑。路徑的耗耗散值一條路徑徑的耗散散值等于于連接這這條路徑徑各節(jié)點點間所有有耗散值值的總和和。用C(ni,nj)表示從ni到nj的路徑的的耗散值值.路路徑耗散散值可按按如下遞遞推公式式計算：：C(ni,t))=C(ni,nj)+C(nj,t)31一些基本本概念（（續(xù)1））擴展一個個節(jié)點生成出該該節(jié)點的的所有后后繼節(jié)點點，并給給出它們們之間的的耗散值值。這一一過程稱稱為“擴擴展一個個節(jié)點””。32一般的圖圖搜索算算法1,G=G0(G0=s),,OPEN::=(s);///設置open表表,最初初只含有有初始點點s2,CLOSED::=());//設置置closed表,初初始為空空表3,LOOP:IFOPEN==())THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,,OPEN)),ADD((n,CLOSED);//n為為當前節(jié)節(jié)點5,IFGOAL(n))THENEXIT(SUCCESS);6,EXPAND((n)→→{mi},G:=ADD((mi,G));//子節(jié)節(jié)點集{{mi}中不包包含n的的父輩節(jié)節(jié)點33一般的圖圖搜索算算法（續(xù)續(xù)）7,標標記和修修改指針針：ADD((mj,OPEN)),并標記mj到n的指指針；//mj為open表表和closed表中中未出現現過的子子結點計算是否否要修改改mk、ml到n的指指針；//mk為已出現現在open表表中的子子結點，，ml為已出現現在closed表中中的子結結點，{{mj}={mj}∪{mk}∪{ml}計算是否否要修改改ml到其后繼繼節(jié)點的的指針；8,對對OPEN中的的節(jié)點按按某種原則則重新排序序；9,GOLOOP；34說明這里給出出的是一一個圖搜搜索的一一般框架架，不是是一個具具體的算算法，關關鍵是算算法的第第8步，按不不同的原原則對OPEN表進行排排序，將將得到不不同的圖圖搜索算算法。算法中有有兩個表表：OPEN表和CLOSED表。其中中OPEN表記錄的的是已經經被生成成出來，，但還沒沒有被擴擴展的節(jié)節(jié)點；CLOSED表記錄的的是已經經被擴展展過的節(jié)節(jié)點。35幾類節(jié)點點的圖例例說明如上圖所所示，假假設n是當前被被擴展的的節(jié)點。。在n被擴展之之前，節(jié)節(jié)點mk和ml已經被生生成出來來了，其其中mk還沒有被被擴展，，他們在在OPEN表中，而而ml已經被擴擴展了，，他們在在CLOSED表中。當當n被擴展時時，它生生成了節(jié)節(jié)點mi，mi由mj、mk和ml三部分組組成，其其中mj是新出現現的節(jié)點點。36算法解釋釋圖搜索算算法，簡簡單地說說就是，，每次從從OPEN表中中取出第第一個節(jié)節(jié)點進行行擴展，，生成的的新節(jié)點點放到OPEN表中，，然后按按照某種種原則對對OPEN表進進行排序序。不同的排排序原則則構成了了不同的的圖搜索索算法。。值得注意意的是算算法成功功結束的的判斷方方法，是是當從OPEN表中取取出一個個節(jié)點后后，再判判斷該節(jié)節(jié)點是否否是目標標節(jié)點，，而不是是在擴展展節(jié)點，，生成新新節(jié)點時時判斷。。這一點點一定要要注意，，在后面面將可以以看到，，這是構構成某些些最優(yōu)算算法的關關鍵所在在。37算法解釋釋這個過程程是在第第8步要要對OPEN表表上的節(jié)節(jié)點進行行排序，，以便在在第4步步能選出出一個““最好””的節(jié)點點優(yōu)先擴擴展。不不同的排排序方法法便可構構成形式式多樣的的專門搜搜索算法法，這在在后面還還要進一一步討論論。如果選出出待擴展展的節(jié)點點是目標標節(jié)點，，則算法法在第5步成功功結束，，并可根根據回溯溯到s的的指針給給出解路路徑。如如果某個個循環(huán)中中，搜索索樹不再再剩有待待選的節(jié)節(jié)點，即即OPEN表變變空時，，則過程程失敗結結束，問問題找不不到解。。38算法解釋釋現在說明明一下第第7步中中標記和和修改指指針的問問題。如果要搜搜索的隱隱含圖是是一棵樹樹，則可可肯定第第6步生生成的后后繼節(jié)點點不可能能是以前前生成過過的，這這時搜索索圖就是是搜索樹樹，不存存在mk、ml這種類型型的子節(jié)節(jié)點，因因此不必必進行修修改指針針的操作作。如果要搜搜索的隱隱含圖不不是一棵棵樹，則則有可能能出現這這樣的的子節(jié)點點，就是是說這時時又發(fā)現現了到達達的新通通路，這這樣就要要比較不不同路徑徑的耗散散值，把把指針修修改到具具有較小小耗散值值的路徑徑上。39例如，下下圖所示示的兩個個搜索圖圖中，實實心圓點點在CLOSED表中（已已擴展過過的節(jié)點點），空空心圓點點則在OPEN表中（待待擴展點點）。先設下一一步輪到到要擴展節(jié)點點6，并設生生成的兩兩個子節(jié)節(jié)點，其其中有一一個4已在OPEN中，那么么原先路路徑（s→3→→2→4）耗散值值為5（設每段段路徑均均為單位位耗散）），新路路徑（s→6→→4）的耗散散值為4，所以4的指針應應由指向向2修正到指指向6，如圖2.5（a）所示。。接著設下下一循環(huán)環(huán)要擴展節(jié)點點1，若節(jié)點點1只生成一一個子節(jié)節(jié)點2（它已在在CLOSED上），顯顯然這時時節(jié)點2原先指向向節(jié)點3的指針，，要修改改到指向向節(jié)點1，由此又又引起子節(jié)點3的指針又又修改為為指向2，如圖2.5（b）所示。。401.3無無信息息圖搜索索過程無信息圖圖搜索屬屬于盲目目搜索，，這里給給兩種常常用的無無信息圖圖搜索方方法：深度優(yōu)先先搜索寬度優(yōu)先先搜索41所謂深度度優(yōu)先搜搜索，就就是在每每次擴展展一個節(jié)節(jié)點時，，選擇到到目前為為止深度度最深的的節(jié)點優(yōu)優(yōu)先擴展展。第7步中中的ADD（mj，OPEN）表表示將被被擴展節(jié)節(jié)點n的的所有新新子節(jié)點點mj加到OPEN表表的前面面。開始始時，OPEN表中只只有一個個初始節(jié)節(jié)點s，，s被擴擴展，其其子節(jié)點點被放入入OPEN表中中。在算法的的第3步步，OPEN表表的第一一個元素素(設為為n)被被取出擴擴展，這這時節(jié)點點n的深深度在OPEN表中是是最大的的，OPEN表表中的其其他節(jié)點點的深度度都不會會超過n的深度度。n的的子節(jié)點點被放到到OPEN表的的最前面面。由于于子節(jié)點點的深度度要大于于父節(jié)點點的深度度，實際際上OPEN表表是按照照節(jié)點的的深度進進行排序序的，深深度深的的節(jié)點被被排在了了前面，，而深度度淺的節(jié)節(jié)點被放放在了后后面。這這樣當下下一個循循環(huán)再次次取出OPEN表的第第一個元元素時，，實際上上選擇的的就是到到目前為為止深度度最深的的節(jié)點，，從而實實現了深深度優(yōu)先先的搜索索策略。。42一般情況況下，當當問題有有解時，，深度優(yōu)優(yōu)先搜索索不但不不能保證證找到最最優(yōu)解，，也不能能保證一一定能找找到解。。如果問問題的狀狀態(tài)空間間是有限限的，則則可以保保證找到到解，當當問題的的狀態(tài)空空間是無無限的時時，則可可能陷入入"深淵淵"，而而找不到到解。為為此，像像回溯算算法一樣樣，可以以加上對搜搜索的深深度限制制。其方法法是在算算法的第第7步，，當節(jié)點點的深度度達到限限制深度度時，則則不將其其子節(jié)點點加入到到OPEN表中中，從而而實現對對搜索深深度的限限制。當當然，這這個深度度限制應應該設置置的合適適，深度度過深影影響搜索索的效率率，而深深度過淺淺，則可可能影響響找到問問題的解解。43回溯和深深度優(yōu)先先的區(qū)別別在有些書書上所講講的深度度優(yōu)先實實際上指指的是我我們這里里所說的的回溯策策略，在在本書中中還是將將二者區(qū)區(qū)分開來來。從形形式上來來說，二二者確實實很相似似，所表表現出來來的都是是每次選選擇深度度最深的的節(jié)點首首先擴展展。但二二者還是是有區(qū)別別的，這這里所說說的深度度優(yōu)先屬屬于圖搜搜索策略略，不足足是占用用較多的的存儲空空間，好好處是對對于特殊殊的問題題，可能能會提高高搜索的的效率。。44設某問題題的狀態(tài)態(tài)空間如如圖所示示。從圖圖中可以以看出該該問題的的特點：：初始節(jié)節(jié)點有若若干個子子節(jié)點，，每個子子節(jié)點都都鏈接到到三條很很深的路路徑中，，而目標標假定在在最右邊邊的路徑徑中。當當采用回回溯策略略時，由由于回溯溯策略只只保留從從初始節(jié)節(jié)點到當當前節(jié)點點的一條條路徑，，所以從從第一個個子節(jié)點點（從左左數）進進入第一一條路徑徑搜索（（從左遍遍數），，回溯后后，又進進入第二二條路徑徑。由于于沒有找找到解，，又回溯溯到第二二個子節(jié)節(jié)點。從從第二個個子節(jié)點點，同樣樣要搜索索第一條條路徑、、第二條條路徑。。第三個個字節(jié)點點、第四四個子節(jié)節(jié)點………也都同同樣。這這樣，第第一和第第二條路路徑將被被多次搜搜索，影影響了搜搜索的效效率。而而對于深深度優(yōu)先先策略（（單指這這里所說說的圖搜搜索深度度優(yōu)先）），由于于保留了了所有已已經搜索索過的路路徑，當當通過第第一個節(jié)節(jié)點搜索索了第一一、第二二條路徑徑后，當當通過第第二個子子節(jié)點搜搜索時，，由于第第一、第第二條路路徑已經經被搜索索，并且且被記錄錄了，所所以就不不必重復復搜索了了，提高高了搜索索的效率率。這一一點在算算法中是是如何體體現出來來的呢？？關鍵是是算法的的第7步步，在n的子節(jié)節(jié)點中，，只將mj類節(jié)點加加入到了了OPEN表中中，而對對于mk類節(jié)點和和ml類節(jié)點則則不予考考慮。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目目標在{{mi}中THENEXIT((SUCCESS);;9,ADD((mj,OPEN)),并并標記mj到n的指指針;10,GOLOOP;46231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標47深度優(yōu)先先搜索的的性質一般不能能保證找找到最優(yōu)優(yōu)解當深度限限制不合合理時，，可能找找不到解解，可以以將算法法改為可可變深度度限制最壞情況況時，搜搜索空間間等同于于窮舉與回溯法法的差別別：圖搜搜索是一個通通用的與與問題無無關的方方法48寬度優(yōu)先先搜索同深度優(yōu)優(yōu)先算法法一樣，，寬度優(yōu)優(yōu)先算法法也是從從一般的的圖搜索索算法變變化而成成。在深深度優(yōu)先先搜索中中，每次次選擇深深度最深深的節(jié)點點首先擴擴展，而而寬度優(yōu)優(yōu)先搜索索則正好好相反，，每次選選擇深度最淺淺的節(jié)點優(yōu)優(yōu)先擴展展。與深深度優(yōu)先先算法不不同的只只是第7步，這里里ADD（OPEN，mj）表示將將mj類子節(jié)點點放到OPEN表的后邊邊，從而而實現了了對OPEN表中的元元素按節(jié)節(jié)點深度度排序，，只不過過這次將將深度淺淺的節(jié)點點放在OPEN表的前面面了，而而深度深深的節(jié)點點被放在在了OPEN表的后邊邊。當問問題有解解時，寬寬度優(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目目標在{{mi}中THENEXIT((SUCCESS);;8,ADD((OPEN,mj),并標記mj到n的指指針;9,GOLOOP;5023184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標823418765451寬度優(yōu)先先搜索的的性質當問題有有解時，，一定能能找到解解當問題為為單位耗耗散值，，且問題題有解時時，一定定能找到到最優(yōu)解解方法與問問題無關關，具有有通用性性效率較低低屬于圖搜搜索方法法521.4啟啟發(fā)式式圖搜索索利用知識識來引導導搜索，，達到減減少搜索索范圍，，降低問問題復雜雜度的目目的。啟發(fā)信息息的強度度強：降低低搜索工工作量，，但可能能導致找找不到最最優(yōu)優(yōu)解解弱：一般般導致工工作量加加大，極極限情況況下變?yōu)闉槊っつ克阉魉?，但可可能可以以找到最最?yōu)解53希望：引入啟發(fā)發(fā)知識，，在保證證找到最最佳解的的情況下下，盡可可能減少少搜索范范圍，提提高搜索索效率。。54基本思想想啟發(fā)式搜搜索過程程中，要要對OPEN表表進行排排序，這這就需要要有一種種方法來來計算待待擴展節(jié)節(jié)點有希希望通向向目標節(jié)節(jié)點的不不同程度度，我們們總是希希望能找找到最有有希望通通向目標標節(jié)點的的待擴展展節(jié)點優(yōu)優(yōu)先擴展展。一種最常常用的方方法是定定義一個個評價函函數f（（Evaluationfunction）對對各個子子節(jié)點進進行計算算，其目目的就是是用來估估算出““有希望望”的節(jié)節(jié)點來。。定義一個個評價函函數可以以參考的的原則有有：一個個節(jié)點處處在最佳佳路徑上上的概率率；求出出任意一一個節(jié)點點與目標標節(jié)點集集之間的的距離度度量或差差異度量量；根據據格局（（博弈問問題）或或狀態(tài)的的特點來來打分。。即根據據問題的的啟發(fā)信信息，從從概率角角度、差差異角度度或記分分法給出出計算評評價函數數的方法法。551.啟啟發(fā)式搜搜索算法法A（A算法））啟發(fā)式搜搜索算法法A，一般簡簡稱為A算法，是是一種典典型的啟啟發(fā)式搜搜索算法法。其基本思思想是：：定義一一個評價價函數f，對當前前的搜索索狀態(tài)進進行評估估，找出出一個最最有希望望的節(jié)點點來擴展展。評價函數數的格式式：f(n))=g(n)++h((n)f(n))：評價價函數h(n))：啟發(fā)發(fā)函數56符號的意意義g*(n)：從s到n的最短路路徑的耗耗散值h*(n)：從n到g的最短路路徑的耗耗散值f*(n)=g*(n)+h*(n)：從s經過n到g的最短路路徑的耗耗散值g(n))、h(n))、f(n))分別是g*(n)、h*(n)、f*(n)的估計值值,是一種預預測。A算法就是是利用這這種預測測，來達達到有效效搜索的的目的的的。它每每次按照照f(n)值的大小小對OPEN表中的元元素進行行排序，，f值小的節(jié)節(jié)點放在在前面，，而f值大的節(jié)節(jié)點則被被放在OPEN表的后面面，這樣樣每次擴擴展節(jié)點點時，都都是選擇擇當前f值最小的的節(jié)點來來優(yōu)先擴擴展。57A算法利用評價價函數f（n））＝g（（n）＋＋h（n）來排排列OPEN表表節(jié)點順順序的圖圖搜索算算法稱為為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}①計算f((n,mi):=g(n,,mi)+h((mi);//g（n，mi）是從s通過n到mi的耗散值值，f（n，mi）是從s通過n、mi到目標節(jié)節(jié)點耗散散值的估估計。59A算法（（續(xù)）②ADD((mj,OPEN)),標標記mj到n的指指針；③IFf(n,,mk)<f((mk)THENf(mk):=f(n,,mk),標記mk到n的指指針；//比比較f（n,,mk）和f（（mk），f（mk）是擴展展n之前前計算的的耗散值值。④IFf(n,,ml)<f((ml)THENf(ml):=f(n,,ml),標記ml到n的指指針,ADD(ml,OPEN));7,OPEN中的節(jié)點點按f值值從小到到大排序序；8,GOLOOP；60A算法同同樣由一一般的圖圖搜索算算法改變變而成。。在算法法的第7步，按按照f值值從小到到大對OPEN表中的的節(jié)點進進行排序序，體現現了A算算法的含含義。算法要計計算f((n)、、g(n)和h(n))的值，，g(n)根據據已經搜搜索的結結果，按按照從初初始節(jié)點點s到節(jié)節(jié)點n的的路徑，，計算這這條路徑徑的耗散散值就可可以了。。而h((n)是是與問題題有關的的，需要要根據具具體的問問題來定定義。有有了g((n)和和h(n)的值值，將他他們加起起來就得得到f((n)的的值。注意A算算法的結結束條件件：當從從OPEN中取取出第一一節(jié)點時時，如果果該節(jié)點點是目標標節(jié)點，，則算法法成功結結束。而而不是在在擴展一一個節(jié)點點時，只只要目標標節(jié)點一一出現就就立即結結束。我我們在后后面將會會看到，，正是由由于有了了這樣的的結束判判斷條件件，才使使得A算算法有很很好的性性質。61算法中f（n））規(guī)定為為對從初初始節(jié)點點s出發(fā)發(fā)，約束束通過節(jié)節(jié)點n到到達目標標點t，，最小耗耗散值路路徑的耗耗散值f*(n)的估估計值，，通常取取正值。。f（n））由兩個個分量組組成，其其中g（（n）是是到目前前為止，，從s到到n的一一條最小小耗散值值路徑的的耗散值值，是作作為從s到n最最小耗散散值路徑徑的耗散散值g**(n))的估計計值，h（n））是從n到目標標節(jié)點t，最小小耗散值值路徑的的耗散值值h*((n)的的估計值值。62一個A算算法的例例子定義評價價函數：：f(n))=g(n)++h((n)g(n))為從初初始節(jié)點點到當前前節(jié)點的的耗散值值h(n))為當前前節(jié)點““不在位位”的將將牌數

283164751238476563h計算舉舉例h(n))=42831647512345768642831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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))目標12345665根據目標標節(jié)點L返回到s的指針，，可得解解路徑S(4))，B(4))，E(5))，I(5))，K(5))，L(5))662．爬山山法爬山法（（局部搜搜索算法法）672．爬山山法過程Hill--climbing①n::=s；；s為初初始節(jié)點點

②LOOP：IFGOAL（n））THENEXIT(SUCCESS)；③③EXPAND（（n）→→{mi}，計算算h(mi)，nextn:=m(minh(mi)的節(jié)點點)；④④IFh(n))<h((nextn))THENEXIT(FAIL);⑤⑤n:=nextn；⑥⑥GOLOOP；顯顯然如果果將山頂頂作為目目標，h(n))表示山山頂與當當前位置置n之間間高度之之差，則則該算法法相當于于總是登登向山頂頂，在單單峰的條條件下，，必能到到達山峰峰。683．分支支界限法法分支界限限法是優(yōu)優(yōu)先擴展展當前具具有最小小耗散值值分支路路徑的端端節(jié)點n，其評評價函數數為f((n)==g(n)。該該算法的的基本思思想很簡簡單，實實際上是是建立一一個局部部路徑（（或分支支）的隊隊列表，，每次都都選耗散散值最小小的那個個分支上上的端節(jié)節(jié)點來擴擴展，直直到生成成出含有有目標節(jié)節(jié)點的路路徑為止止。69過程Branch-Bound①QUEUE:=((s-s)，g(s))=0;;

②LOOP：IFQUEUE=(()THENEXIT(FAIL));③③PATH::=FIRST(QUEUE)，n:=LAST(PATH));④④IFGOAL((n)THENEXIT(SUCCESS));⑤⑤EXPAND(n)→{{mi}}，計算算g(mi)==g(n，mi)，REMOVE（（s--n，，QUEUE）），ADD((s-mi，QUEUE);;

⑥QUEUE中中局部路路徑g值值最小者者排在前前面；⑦⑦GOLOOP；70應用分支支界限法法求下圖圖的最短短路徑，，求解過過程中QUEUE的結結果簡記記如下（（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.結結束。724．動態(tài)態(tài)規(guī)劃法法在A算法法中，當當h(n)≡0時，則則A算法法演變?yōu)闉閯討B(tài)規(guī)規(guī)劃算法法。由于于在A算算法中，，很多問問題的啟啟發(fā)函數數h難于于定義，，因此動動態(tài)規(guī)劃劃算法是是至今一一直被經經常使用用的算法法。734．動態(tài)態(tài)規(guī)劃法法動態(tài)規(guī)劃劃法實際際上是對對分支界界限法的的改進。。從圖2.9看出，第第二循環(huán)環(huán)擴展A（3）后生成成的D（8）節(jié)點（（D（4）已在QUEUE上）和第第三循環(huán)環(huán)擴展D（4）之后生生成的A（9）節(jié)點（（A（3）已以QUEUE上）都是是多余的的分支，，因為由由s－D到達目標標的路徑徑顯然要要比s－A－D到達目標標的路徑徑要好。。因此刪刪去類似似于s－A－D或s－D－A這樣一些些多余的的路徑將將會大大大提高搜搜索效率率。動態(tài)態(tài)規(guī)劃原原理指出出，求s→t的最佳路路徑時，，對某一一個中間間節(jié)點I，只要考考慮s到I中最小耗耗散值這這一條局局部路徑徑就可以以，其余余s到I的路徑是是多余的的，不必必加以考考慮。74動態(tài)規(guī)劃劃st第一階段段第二階段段第三階段段第四階段段第五階段段754．動態(tài)態(tài)規(guī)劃法法過程Dynamic--Programming①QUEUE:=((s-s)，g(s))=0;;

②LOOP：IFQUEUE=（（）THENEXIT(FAIL));③③PATH::=FIRST(QUEUE)，n:=LAST(PATH));④④IFGOAL((n)THENEXIT(SUCCESS));⑤⑤EXPAND(n)→{{mi}}，計算算g(mi)==g(n，mi)，REMOVE（（s-n，QUEUE），ADD((s-mi，QUEUE);;

⑥若若QUEUE中有多多條到達達某一公公共節(jié)點點的路徑徑，則只只保留耗耗散值最最小的那那條路徑徑，其余余刪去，，并重新新排序，，g值最最小者排排在前面面；⑦⑦GOLOOP；；765.最佳佳圖搜索索算法A*（OptimalSearch））當在算法法A的評價函函數中，，使用的的啟發(fā)函函數h(n)是處在h﹡（n）的下界界范圍，，即滿足足h(n)≤h*(n)時，則我我們把這這個算法法稱為算算法A﹡。775.A*算法法A﹡算法實際際上是分分支界限限和動態(tài)態(tài)規(guī)劃原原理及使使用下界界范圍的的h相結合的的算法。。當問題有有解時，，A﹡一定能找找到一條條到達目目標節(jié)點點的最佳佳路徑。。例如在在極端情情況下，，若h(n))≡0（肯定滿滿足下界界范圍條條件），，因而一一定能找找到最佳佳路徑;若g≡d，則算法法等同于于寬度優(yōu)優(yōu)先算法法。前面面已提到到過，寬寬度優(yōu)先先算法能能保證找找到一條條到達目目標節(jié)點點最小長長度的路路徑，因因而這個個特例從從直觀上上就驗證證了A﹡的一般結結論。一般地說說對任意意一個圖圖，當s到目標節(jié)節(jié)點有一一條路徑徑存在時時，如果果搜索算算法總是是在找到到一條從從s到目標節(jié)節(jié)點的最最佳路徑徑上結束束，則稱稱該搜索索算法是是可采納納的（Admissibility）。A﹡就具有可可采納性性。78對于以下下的定理理、引理理和推論論，我們們只要求求掌握其其結論和和含義，，不要求求掌握其其具體的的證明過過程。但但是證明明過程有有助于你你對算法法的理解解。以下定理理的證明明，正文文部分是是嚴格的的，而解解釋部分分，則不不是嚴格格的證明明，只是是從直觀觀上，或或者從思思路上進進行說明明。在以下的的定理證證明過程程中，要要明確這這樣幾個個關系：：f*(s)=f*(t)=h*(s)，其中s是初始節(jié)節(jié)點，t是目標節(jié)節(jié)點（有有時也用用g表示）。。當n是從初始始節(jié)點到到目標節(jié)節(jié)點t的最優(yōu)路路徑上的的節(jié)點時時，f*(n)=f*((s)==f*((t)==h*((s)。5.A*算法法79A*算法法的性質質（續(xù)1）定理1..1：對有限圖圖，如果果從初始始節(jié)點s到目標標節(jié)點t有路徑徑存在，，則算法法A一定定成功結結束。證明：設設A搜索索失敗，，則算法法在第2步結束束，OPEN表表變空，，而CLOSED表中中的節(jié)點點是在結結束之前前被擴展展過的節(jié)節(jié)點。由由于圖有有解，令令（n0=s，，n1，，n2，，…，nk=t）表示示某一解解路徑，，我們從從nk開開始逆向向逐個檢檢查該序序列的節(jié)節(jié)點，找找到出現現在CLOSED表中中的節(jié)點點ni，，即niCLOSED，ni+1CLOSED（ni一定定能找到到，因為為n0CLOSED，nkCLOSED）。。由于ni在CLOSES中中，必定定在第6步被擴擴展，且且ni++1被加加到OPEN中中，因此此在OPEN表表空之前前，ni+1已已被處理理過。若若ni++1是目目標節(jié)點點，則搜搜索成功功，否則則它被加加入到CLOSED中中，這兩兩種情況況都與搜搜索失敗敗的假設設矛盾，，因此對對有限圖圖不失敗敗則成功功。[證證畢]80A*算法法的性質質（續(xù)2）引理1..1：：對無限圖圖，若有有從初始始節(jié)點s到目標標節(jié)點t的路徑徑，則A*不結結束時，，在OPEN表表中即使使最小的的一個f值也將將增到任任意大，，或有f(n))>f**(s))。該引理的的證明中中，隱含含了兩個個假設：：（1））任何兩兩個節(jié)點點之間的的耗散值值都大于于某個給給定的大大于零的的常量；；（2））h(n)對于于任何n來說，，都大于于等于零零。由由于當當問題有有解存在在時，從從初始節(jié)節(jié)點到目目標節(jié)點點的路徑徑的耗散散值總是是一個有有限的常常量。那那么在該該解路徑徑上的任任何一個個節(jié)點n，由于于f(n)=g(n))+h((n)，，而g((n)是是有限的的，h((n)≤≤h*((n)也也是有限限的（因因為h**(n))有限）），所以以f(n)也是是有限的的。而對對于一個個無限圖圖來說，，那些不不在解路路徑上的的無限路路徑，隨隨著搜索索的進行行，其耗耗散值總總會趨于于無窮大大，因此此那些在在解路徑徑上的節(jié)節(jié)點的f值值總會變變得最小小，總會會有機會會被排在在OPEN表的的第一個個位置，，從而被被A*擴擴展。而而目標節(jié)節(jié)點也是是解路徑徑上的一一個節(jié)點點，這樣樣它同樣樣會有機機會被排排在OPEN表表的第一一個位置置，從而而使得算算法成功功結束，，找到問問題的解解路徑。。81A*算法法的性質質（續(xù)2）引理1..2：：對無限圖圖，若有有從初始始節(jié)點s到目標標節(jié)點t的路徑徑，則A*不結結束時，，在OPEN表表中即使使最小的的一個f值也將將增到任任意大，，或有f(n))>f**(s))。證明：設設d﹡((n)是是A﹡生生成的搜搜索樹中中，從s到任一一節(jié)點n最短路路徑長度度的值（（設每個個弧的長長度均為為1），，搜索圖圖上每個個弧的耗耗散值為為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（設設h(n)≥0）若若A﹡不不結束，，d﹡((n)趨趨向于∞，f值將將增到任任意大。。82A*算法法的性質質（續(xù)2）該引理可可以這樣樣來理解解：如果果問題從從初始節(jié)節(jié)點s到到目標節(jié)節(jié)點g的的路徑存存在時，，則一定定有一個個最短路路徑存在在。在A*沒有有結束之之前，OPEN表中的的節(jié)點不不會為空空。由于于總是從從OPEN表中中取出節(jié)節(jié)點來擴擴展，所所以最優(yōu)優(yōu)路徑肯肯定要通通過OPEN表表中的某某個節(jié)點點，設該該節(jié)點為為n。那那么n有有兩個特特點，一一是n是是從s到到g的最最優(yōu)路徑徑上的節(jié)節(jié)點，二二是到目目前為止止已經找找到了從從s到n的最優(yōu)優(yōu)路徑。。第一點點會比較較容易接接受，第第二點是是如何保保證的呢呢？如果果到目前前為止找找到的不不是從s到n的的最優(yōu)路路徑，同同樣的理理由，在在OPEN表中中一定有有一個節(jié)節(jié)點---假定為為n'---在從從s到n的最優(yōu)優(yōu)路徑上上，當然然他也一一定在從從s到g的最優(yōu)優(yōu)路徑上上。用n'來代代替n，，重復下下去，一一直找到到滿足以以上兩個個特點的的n為止止。當然然，我們們不一定定明確的的知道到到底OPEN表表中的哪哪個節(jié)點點滿足這這樣的特特點，但但從以上上的敘述述可以知知道，這這樣的節(jié)節(jié)點一定定存在。。

對于于具有這這樣特點點的n，，由于以以上所說說的第一一個特點點有g((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))。對于于最后一一個等式式，是由由于對于于任何兩兩個最優(yōu)優(yōu)路徑上上的節(jié)點點n1和和n2，，都有f*(n1)==f*((n2))，而n和s都都是最優(yōu)優(yōu)路徑上上的節(jié)點點。引理理1.2得證。。83A*算法法的性質質（續(xù)3）引理1..3：A*結束前，，OPEN表中中必存在在f(n)≤f*(s)的節(jié)節(jié)點（n是在最最佳路徑徑上的節(jié)節(jié)點）。證明：設設從初始始節(jié)點s到目標節(jié)節(jié)點t的一條最最佳路徑徑序列為為：(n0==s，n1，…，nk=t)算法初始始化時，，s在OPEN中，由于于A﹡沒有結束束，在OPEN中存在最最佳路徑徑上的節(jié)節(jié)點。設設OPEN表中的某某節(jié)點n是處在最最佳路徑徑序列中中（至少少有一個個這樣的的節(jié)點，，因s一開始是是在OPEN上），顯顯然n的先輩節(jié)節(jié)點np已在CLOSED中，因此此能找到到s到np的最佳路路徑，而而n也在最佳佳路徑上上，因而而s到n的最佳路路徑也能能找到，，因此有有f(n)=g(n))+h((n)=g**(n)+h(n))≤g*(n)+h*(n))=f**(n))而最佳路路徑上任任一節(jié)點點均有f*（n）=f*((s)（f*(s)是最佳路路徑的耗耗散值）），所以以f(n))≤f*(s))。[證畢]84A*算法法的性質質（續(xù)3）定理1..2：對無限圖圖，若從從初始節(jié)節(jié)點s到到目標節(jié)節(jié)點t有有路徑存存在，則則A*一一定成功功結束。。證明：假假定A*不結束，，由引理理2.1有f(n)＞f*(s)，或OPEN表中最小小的一個個f值也變成成無界，，這與引引理2.2的結論矛矛盾，所所以A*只能成功功結束。。[證畢]85A*算法法的性質質（續(xù)4）推論1..1：OPEN表上任任一具有有f(n)<f*(s)的節(jié)節(jié)點n，，最終都都將被A*選作作擴展的的節(jié)點。。由定理1.2，知A*一定結束束，由A*的結束條條件，OPEN表中f(t))最小時才才結束。。而f(t))≥f*(t)＝f*(s)所以f(n))<f**(s))的n，均被擴展展。得證證。86A*算法法的性質質（續(xù)5）定理1..3((可采納納性定理理)：若存在從從初始節(jié)節(jié)點s到到目標節(jié)節(jié)點t有有路徑，，則A**必能找找到最佳佳解結束束。87可采納性性的證明明由定理1.1、、1.2知A**一定找找到一條條路徑結結束設找到的的路徑s→t不是最最佳的（（t為目目標）則：f((t)==g(t))>f*((s)由引理1.2知知結束前前OPEN中存存在f((n)≤≤f*((s)的的節(jié)點n，所以以f(n))≤f*((s)<<f(t))因此A**應選擇擇n擴展展，而不不是t。。與假設設A*選選擇t結結束矛盾盾。得證證。注意：A*的的結束條條件88A*算法法的性質質（續(xù)6）推論1..2：A*選作作擴展的的任一節(jié)節(jié)點n，，有f((n)≤≤f*((s)。。由引理2.2知知在A**結束前前，OPEN中中存在節(jié)節(jié)點n’’，f(n’’)≤f*(s)設此時A*選擇擇n擴展展。如果n＝＝n’，，則f((n)≤≤f*((s)，，得證。。如果n≠≠n’’，由于于A*選選擇n擴擴展，而而不是n’，所所以有f(n))≤f(n’)≤≤f*((s)。。得證。。89A*算法法的性質質（續(xù)7）定理1..4：設設對同一一個問題題定義了了兩個A*算法法A1和A2，若A2比A1有較多的的啟發(fā)信信息，即即對所有有非目標標節(jié)點有有h2(n)>>h1(n)，，則在具具有一條條從s到到t的路路徑的隱隱含圖上上，搜索索結束時時，由A2所擴展的的每一個個節(jié)點，，也必定定由A1所擴展，，即A1擴展的節(jié)節(jié)點數至至少和A2一樣多。。簡寫：如如果h2(n)>h1(n)((目標標節(jié)點除除外)，，則A1擴展的節(jié)節(jié)點數≥A2擴展的節(jié)節(jié)點數90A*算法法的性質質（續(xù)7）注意：在定理1.4中中，評價價指標是是“擴展展的節(jié)點點數”，，也就是是說，同同一個節(jié)節(jié)點無論論被擴展展多少次次，都只只計算一一次。91定理1..4的證證明使用數學學歸納法法，對節(jié)節(jié)點的深深度進行行歸納（1）當當d(n)＝0時，即即只有一一個節(jié)點點，顯然然定理成成立。（2）設設d(n)≤k時定理理成立。。（歸納納假設））（3）當當d(n)=k+1時時，用反反證法。。設存在一一個深度度為k＋＋1的節(jié)節(jié)點n，，被A2擴展，但但沒有被被A1擴展。而而由假設設，A1擴展了n的父節(jié)節(jié)點，即即n已經經被生成成了。因因此當A1結束時，，n將被被保留在在OPEN中。。92定理1..4的證證明（續(xù)續(xù)1）所以有：：f1(n)≥≥f*(s)即：g1(n)++h1(n)≥≥f*(s)所以：h1(n)≥≥f*(s)--g1(n)另一方面面，由于于A2擴展了n，有f2(n)≤≤f**(s))即：h2(n)≤≤f*(s)––g2(n)((A)由于d((n)==k時，，A2擴展的節(jié)節(jié)點A1一定擴展展，有g1(n)≤≤g2(n)((因為A2的路A1均走到了了)所以：h1(n)≥≥f*(s)--g1(n)≥≥f*(s)––g2(n)((B)比較A、、B兩式式，有h1(n)≥≥h2(n)，，與定定理條件件矛盾。。故定理理得證。。933，A**算法的的改進問題的提提出：因A算法法第6步步對ml類節(jié)點可可能要重重新放回回到OPEN表表中，因因此可能能會導致致多次重重復擴展展同一個個節(jié)點，，導致搜搜索效率率下降。。94s(10)A(1)B(5)C(8)G目標631118一個例子子：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))