人工智能：第1章 搜索問題

第一章搜索問題1狼、羊、白菜游戲2野人過河游戲3第一章搜索問題內(nèi)容:

狀態(tài)空間的搜索問題。搜索方式:盲目搜索啟發(fā)式搜索關(guān)鍵問題:

如何利用知識(shí),盡可能有效地找到問題的解(最佳解)。4人類的思維過程,可以看作是一個(gè)搜索的過程。從小學(xué)到現(xiàn)在,你一定遇到過很多種的智力游戲問題,比方說在前面介紹的傳教士和野人問題。如果你來做這個(gè)智力游戲的話,在每一次渡河之后,都會(huì)有幾種渡河方案供你選擇,究竟哪種方案才有利于在滿足題目所規(guī)定的約束條件下順利過河呢？經(jīng)過反復(fù)努力和試探,你終于找到了一種解決辦法。在高興之余,你馬上可能又會(huì)想到,這個(gè)方案所用的步驟是否最少？也就是說它是最優(yōu)的嗎？如果不是,如何才能找到最優(yōu)的方案？在計(jì)算機(jī)上又如何實(shí)現(xiàn)這樣的搜索？這些問題實(shí)際上就是本章我們要介紹的搜索問題。5學(xué)習(xí)目標(biāo)掌握回溯搜索算法,深度優(yōu)先搜索算法,寬度優(yōu)先搜索算法和A(A*)搜索算法,對(duì)典型問題,掌握啟發(fā)式函數(shù)的定義方法。學(xué)習(xí)指南了解算法的每一個(gè)過程和細(xì)節(jié)問題,掌握一些重要的定理和結(jié)論,在有條件的情況下,程序?qū)崿F(xiàn)每一個(gè)算法,求解一些典型的問題。難重點(diǎn)回溯搜索算法,A*算法及其性質(zhì),改進(jìn)的A*算法。6狀態(tài)空間表示法人工智能的多個(gè)研究領(lǐng)域從求解現(xiàn)實(shí)問題的過程來看，都可抽象為一個(gè)“問題求解”過程問題求解過程實(shí)際上就是一個(gè)“搜索過程”為了進(jìn)行搜索，首先必須用某種形式把問題表示出來“狀態(tài)空間表示法”就是用來表示問題及其搜索過程的一種方法7狀態(tài)空間表示法狀態(tài)空間表示法是用“狀態(tài)”和“算子”來表示問題的一種方法狀態(tài)：用來描述問題求解過程中不同時(shí)刻的狀況算子：表示對(duì)狀態(tài)的操作，算子的每次使用就使問題由一種狀態(tài)變換為另一種狀態(tài)當(dāng)達(dá)到目標(biāo)狀態(tài)時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算子的序列就是問題的一個(gè)解8狀態(tài)空間表示法狀態(tài)狀態(tài)是描述問題求解過程中任一時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu)，一般用一組變量的有序組合表示:S(s0,s1,…)，si是狀態(tài)的分量當(dāng)給每一分量以確定的值時(shí)，就得到一個(gè)具體的狀態(tài)SK(SK0,SK1,…)算子引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作稱為算子。產(chǎn)生式系統(tǒng)中，每一條產(chǎn)生式規(guī)則就是一個(gè)算子狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間，一般用三元組表示:(S0,F,Sg)S0:所有初始狀態(tài)構(gòu)成的集合F:算子的集合Sg:目標(biāo)狀態(tài)的集合9例子:HanoiTower二階hanoitowerSK=(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).問題的初始狀態(tài)集合S={S0},目標(biāo)集合為G={S4,S8}算子分別用A(i,j),B(i,j)表示A(i,j):盤片A從柱i移到柱jB(i,j):盤片B從柱i移到柱j全部可能的算子：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)10111213狀態(tài)空間表示法首先必須定義狀態(tài)的描述形式，通過使用這種描述可把問題的一切狀態(tài)都表示出來。其實(shí)還要定義一組算子，通過使用算子可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)問題的求解過程就是一個(gè)不斷把算子作用于狀態(tài)的過程算子的一次使用，就使問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)?？赡苡卸鄠€(gè)算子序列都可使問題從初始狀態(tài)變到目標(biāo)狀態(tài)，這就得到了多個(gè)解，我們把使用算子最少的解稱為最優(yōu)解對(duì)于任何一種狀態(tài)，可使用的算子可能不止一個(gè)，這樣由一個(gè)狀態(tài)所生成的后繼狀態(tài)就可能有多個(gè)。當(dāng)對(duì)這些后繼狀態(tài)使用算子生成更進(jìn)一步狀態(tài)時(shí)，首先應(yīng)對(duì)哪一狀態(tài)進(jìn)行操作呢？這取決于搜索策略，不同搜索策略的操作順序是不相同的。14搜索技術(shù)

搜索技術(shù)是人工智能的基本技術(shù)之一,在人工智能各應(yīng)用領(lǐng)域中被廣泛地使用。早期的人工智能程序與搜索技術(shù)聯(lián)系就更為緊密，幾乎所有的早期的人工智能程序都是以搜索為基礎(chǔ)的。例如，A.Newell(艾倫·紐厄爾)和H·A·Simon(西蒙)等人編寫的LT(LogicTheorist)程序,J.Slagle寫的符號(hào)積分程序SAINT,A·Newell和H·A·Simon寫的GPS(GeneralProblemSolver)程序,H·Gelernter(格倫特爾)寫的Geometrytheorem-provingmachine程序,R.Fikes(菲克斯)和N.Nilsson(尼爾遜)寫的STRIPS(StanfordResearchInstituteProblemSolver)程序以及A.Samuel(塞繆爾)寫的Chechers程序等,都使用了各種搜索技術(shù)?，F(xiàn)在,搜索技術(shù)滲透在各種人工智能系統(tǒng)中,可以說沒有哪一種人工智能的應(yīng)用不用搜索方法,在專家系統(tǒng)、自然語言理解、自動(dòng)程序設(shè)計(jì)、模式識(shí)別、機(jī)器人學(xué)、信息檢索和博弈都廣泛使用搜索技術(shù)。15搜索技術(shù)

搜索問題是AI核心理論問題之一一般一個(gè)問題可以用好幾種搜索技術(shù)解決,選擇一種好的搜索技術(shù)對(duì)解決問題的效率很有關(guān)系,甚至關(guān)系到求解問題有沒有解。搜索方法好的標(biāo)準(zhǔn),一般認(rèn)為有兩個(gè)：(1)搜索空間小;(2)解最佳。16搜索技術(shù)

搜索從問題性質(zhì)上來看,可分為一般搜索和博奕搜索,從處理方法上來看,可分為盲目搜索和啟發(fā)式搜索，還可以分得更細(xì)。當(dāng)所給定的問題用狀態(tài)空間表示時(shí),則求解過程可歸結(jié)為對(duì)狀態(tài)空間的搜索。當(dāng)問題有解時(shí),使用不同的搜索策略,找到解的搜索空間范圍是有區(qū)別的。一般來說,對(duì)大空間問題,搜索策略是要解決組合爆炸的問題。17搜索問題(續(xù)1)S0Sg18搜索問題(續(xù)2)討論的問題:有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何？19搜索策略

通常搜索策略的主要任務(wù)是確定如何選取規(guī)則的方式。有兩種基本方式:一種是不考慮給定問題所具有的特定知識(shí),系統(tǒng)根據(jù)事先確定好的某種固定排序,依次調(diào)用規(guī)則或隨機(jī)調(diào)用規(guī)則,這實(shí)際上是盲目搜索的方法,一般統(tǒng)稱為無信息引導(dǎo)的搜索策略。另一種是考慮問題領(lǐng)域可應(yīng)用的知識(shí),動(dòng)態(tài)地確定規(guī)則的排序,優(yōu)先調(diào)用較合適的規(guī)則使用,這就是通常稱為啟發(fā)式搜索策略或有信息引導(dǎo)的搜索策略。20AI領(lǐng)域的搜索方法(1)求任一解路的搜索策略回溯法(Backtracking)爬山法(HillClimbing)寬度優(yōu)先法(Breadth-first)深度優(yōu)先法(Depth-first)限定范圍搜索法(BeamSearch)最佳優(yōu)先法(Best-first)(2)求最佳解路的搜索策略大英博物館法(BritishMuseum)分枝界限法(BranchandBound)動(dòng)態(tài)規(guī)劃法(DynamicProgramming)最佳圖搜索法(A*)21AI領(lǐng)域的搜索方法(3)求與或關(guān)系解圖的搜索法一般與或圖搜索法(AO*)極小極大法(Minimax)剪枝法(Alpha-betaPruning)啟發(fā)式剪枝法(HeuristicPruning)22搜索策略分類23盲目搜索方法盲目搜索是不利用問題的有關(guān)信息,而根據(jù)事先確定好的某種固定的搜索方法進(jìn)行搜索。典型的盲目搜索方法是深度優(yōu)先搜索和寬度優(yōu)先搜索(亦稱廣度優(yōu)先搜索),這是兩種基本搜索方法241.1回溯策略回溯策略屬于盲目搜索的一種。所謂回溯策略,簡(jiǎn)單地說是這樣一種策略:首先將規(guī)則給出一個(gè)固定的排序,在搜索時(shí),對(duì)當(dāng)前狀態(tài)(搜索開始時(shí),當(dāng)前狀態(tài)是初始狀態(tài))依次檢測(cè)每一條規(guī)則,在當(dāng)前狀態(tài)未使用過的規(guī)則中找到第一條可觸發(fā)規(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ù)以上搜索,直到找到問題的解,或者試探了所有可能后仍找不到問題的解為止?；厮莶呗钥梢杂卸喾N實(shí)現(xiàn)的方法,其中用遞歸法實(shí)現(xiàn)也許是最簡(jiǎn)單的方法了,本書中給出的就是這種算法。25遞歸的思想從前有座山……

從前有座山……

從前有座山……26Fibonacci數(shù)列1202年，意大利家斐波那契在提出了一個(gè)關(guān)于兔子繁殖的問題：

如果一對(duì)兔子每月能生一對(duì)小兔(一雄一雌)，而每對(duì)小兔在它出生後的第三個(gè)月里，又能開始生一對(duì)小兔，假定在

不發(fā)生死亡的情況下，由一對(duì)出生的小兔開始，50個(gè)月后會(huì)有多少對(duì)兔子？當(dāng)n＞1時(shí)，F(xiàn)n+2=Fn+1+Fn，而F0=F1=127一個(gè)遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12328回溯搜索算法 BACKTRACK(DATA)

DATA:當(dāng)前狀態(tài)。 返回值:從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑

(以規(guī)則表的形式表示)

或FAIL。29回溯搜索算法遞歸過程BACKTRACK(DATA)①IFTERM(DATA),RETURNNIL;TERM取真即找到目標(biāo),則過程返回空表NIL。②IFDEADEND(DATA),RETURNFAIL;DEADEND取真,即該狀態(tài)不合法,則過程返回FAIL,必須回溯。③RULES:＝APPRULES(DATA);APPRULES計(jì)算DATA的可應(yīng)用規(guī)則集,依某種原則(任意排列或按啟發(fā)式準(zhǔn)則)排列后賦給RULES。④LOOP:IFNULL(RULES),RETURNFAIL;NULL取真,即規(guī)則用完未找到目標(biāo),過程返回FAIL,必須回溯。⑤R:＝FIRST(RULES);取頭條可應(yīng)用規(guī)則30回溯搜索算法⑥RULES:＝TAIL(RULES);刪去頭條規(guī)則,減少可應(yīng)用規(guī)則表的長(zhǎng)度。⑦RDATA:＝GEN(R,DATA);調(diào)用規(guī)則R作用于當(dāng)前狀態(tài),生成新狀態(tài)。⑧PATH:＝BACKTRACK(RDATA);對(duì)新狀態(tài)遞歸調(diào)用本過程。⑨IFPATH＝FAIL,GOLOOP;當(dāng)PATH＝FAIL時(shí),遞歸調(diào)用失敗,則轉(zhuǎn)移調(diào)用另一規(guī)則進(jìn)行測(cè)試。⑩RETURNCONS(R,PATH);過程返回解路徑規(guī)則表(或局部解路徑子表)。31遞歸的思想321.1回溯策略四皇后問題:在一個(gè)4×4的國(guó)際象棋棋盤上,一次一個(gè)地?cái)[布四枚皇后棋子,擺好后要滿足每行,每列和對(duì)角線上只允許出現(xiàn)一枚棋子,即棋子間不許相互俘獲。圖2.2給出棋盤的幾個(gè)勢(shì)態(tài),其中a,b滿足目標(biāo)條件,c,d,e為不合法狀態(tài),即不可能構(gòu)成滿足目標(biāo)條件的中間勢(shì)態(tài)。33綜合數(shù)據(jù)庫:DATA＝L(表),L的元素{ij},1i,j4

。DATA非空時(shí),其表元素表示棋子所在的行和列。因只有4個(gè)棋子,故表元素個(gè)數(shù)最多為4。上圖中a,b分別記為(12243143)和(13213442),c,d,e分別記為(1121),(1122),(112331)等等。規(guī)則集:if1i4且Length(DATA)＝i-1

thenAPPEND(DATA(ij))(1j4)

共16條規(guī)則,每條規(guī)則Rij表示滿足前提條件下,在ij處放一棋子。34()35()Q((1,1))36()QQ((1,1))((1,1)(2,3))37()Q((1,1))((1,1)(2,3))38()QQ((1,1))((1,1)(2,3))((1,1)(2,4))39()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3,2))40()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3,2))41()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3,2))42()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3,2))43()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3,2))Q((1,2))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))45()((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))46()((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))47一些深入的問題失敗原因分析,多步回溯QQ48一些深入問題(續(xù))回溯搜索中知識(shí)的利用 基本思想(以皇后問題為例):

盡可能選取劃去對(duì)角線上位置數(shù)最少的。QQQQ322349回溯算法存在的問題及解決辦法解決辦法:對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)問題:深度問題死循環(huán)問題50回溯搜索算法1BACKTRACK1(DATALIST)

DATALIST:從初始到當(dāng)前的狀態(tài)表(逆向)

返回值:從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑

(以規(guī)則表的形式表示)

或FAIL。51回溯搜索算法11. DATA:=FIRST(DATALIST)2. IFMENBER(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);52回溯搜索算法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);531.2圖搜索策略問題的引出回溯搜索策略的一個(gè)特點(diǎn)就是只保留了從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑(無論是BACKTRACK還是BACKTRACK1都是如此),當(dāng)回溯出現(xiàn)時(shí),回溯點(diǎn)處進(jìn)行的搜索將被算法“忘記”,其好處是節(jié)省了存儲(chǔ)空間,而不足是這些被回溯掉的已經(jīng)搜索過的部分,不能被以后使用。與此相對(duì)應(yīng)的,將所有搜索過的狀態(tài)都記錄下來的搜索方法稱為"圖搜索",搜索過的路徑除了可以重復(fù)利用外,其最大的優(yōu)點(diǎn)是可以更有效地利用與問題有關(guān)的一些知識(shí),從而達(dá)到啟發(fā)式搜索的目的。保留所有已經(jīng)搜索過的路徑。

54一些基本概念節(jié)點(diǎn)深度:

根節(jié)點(diǎn)深度=0

其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1012355一些基本概念(續(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的路徑的耗散值。遞歸公式:C(ni,t)＝C(ni,nj)+C(nj,t)56一些基本概念(續(xù)1)擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn),并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。57一般的圖搜索算法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);58一般的圖搜索算法(續(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;59節(jié)點(diǎn)類型說明如圖所示,假設(shè)n是當(dāng)前被擴(kuò)展的節(jié)點(diǎn)。在n被擴(kuò)展之前,節(jié)點(diǎn)mk和ml已經(jīng)被生成出來了,其中mk還沒有被擴(kuò)展,他們?cè)贠PEN表中,而ml已經(jīng)被擴(kuò)展了,他們?cè)贑LOSED表中。當(dāng)n被擴(kuò)展時(shí),它生成了節(jié)點(diǎn)mi,mi由mj,mk和ml三部分組成,其中mj是新出現(xiàn)的節(jié)點(diǎn)。

60修改指針舉例123456s61修改指針舉例(續(xù)1)123456s62123456修改指針舉例(續(xù)2)s63123456修改指針舉例(續(xù)3)s641.3無信息圖搜索過程深度優(yōu)先搜索寬度優(yōu)先搜索65深度優(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;66深度優(yōu)先搜索

深度優(yōu)先搜索,就是在每次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí),選擇到目前為止深度最深的節(jié)點(diǎn)優(yōu)先擴(kuò)展。這一點(diǎn)是在算法的第7步體現(xiàn)出來的。第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)先的搜索策略。67231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)68深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí),可能找不到解,可以將算法改為可變深度限制最壞情況時(shí),搜索空間等同于窮舉與回溯法的差別:圖搜索是一個(gè)通用的與問題無關(guān)的方法69漸進(jìn)式深度優(yōu)先搜索方法目的解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。思想首先給回溯法一個(gè)比較小的深度限制,然后逐漸增加深度限制,直到找到解或找遍所以分支為止。70寬度優(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;71寬度優(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)了對(duì)OPEN表中的元素按節(jié)點(diǎn)深度排序,只不過這次將深度淺的節(jié)點(diǎn)放在OPEN表的前面了,而深度深的節(jié)點(diǎn)被放在了OPEN表的后邊。當(dāng)問題有解時(shí),寬度優(yōu)先算法不但能一定找到解,而且在單位耗散的情況下,可以保證找到最優(yōu)解。7223184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)823418765473寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時(shí),一定能找到解當(dāng)問題為單位耗散值,且問題有解時(shí),一定能找到最優(yōu)解方法與問題無關(guān),具有通用性效率較低屬于圖搜索方法741.4啟發(fā)式圖搜索利用知識(shí)來引導(dǎo)搜索,達(dá)到減少搜索范圍,降低問題復(fù)雜度的目的。啟發(fā)信息的強(qiáng)度強(qiáng):降低搜索工作量,但可能導(dǎo)致找不到最 優(yōu)解弱:一般導(dǎo)致工作量加大,極限情況下變?yōu)?盲目搜索,但可能可以找到最優(yōu)解75希望:引入啟發(fā)知識(shí),在保證找到最佳解的情況下,盡可能減少搜索范圍,提高搜索效率。76基本思想定義一個(gè)評(píng)價(jià)函數(shù)f,對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估,找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。771.啟發(fā)式搜索算法A(A算法)評(píng)價(jià)函數(shù)的格式:

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

h(n):啟發(fā)函數(shù)78符號(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ì)值79A算法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);

80A算法(續(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;81左圖表示出當(dāng)前要擴(kuò)展節(jié)點(diǎn)n之前的搜索圖,擴(kuò)展n后新生成的子節(jié)點(diǎn)m1({mj}),m2({mk}),m3({ml})要分別計(jì)算其評(píng)價(jià)函數(shù)值:f(m1)=g(m1)+h(m1)

f(n,m2)=g(n,m2)+h(m2)

f(n,m3)=g(n,m3)+h(m3)82一個(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ù)

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

831

64751234576

884設(shè)評(píng)價(jià)函數(shù)f(n)形式如下:f(n)=d(n)+W(n)其中d(n)代表節(jié)點(diǎn)的深度,取g(n)=d(n)表示討論單位耗散的情況;取h(n)=W(n)表示“不在位”的將牌個(gè)數(shù)作為啟發(fā)函數(shù)的度量,這時(shí)f(n)可估計(jì)出通向目標(biāo)節(jié)點(diǎn)的希望程度。下圖表示使用這種評(píng)價(jià)函數(shù)時(shí)的搜索樹,圖中括弧中的數(shù)字表示該節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f。算法每一循環(huán)結(jié)束時(shí),其OPEN表和CLOSED表的排列如下:

85862831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)123456872.爬山法過程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á)山峰。883.分支界限法分支界限法是優(yōu)先擴(kuò)展當(dāng)前具有最小耗散值分支路徑的端節(jié)點(diǎn)n,其評(píng)價(jià)函數(shù)為f(n)=g(n)。該算法的基本思想很簡(jiǎn)單,實(shí)際上是建立一個(gè)局部路徑(或分支)的隊(duì)列表,每次都選耗散值最小的那個(gè)分支上的端節(jié)點(diǎn)來擴(kuò)展,直到生成出含有目標(biāo)節(jié)點(diǎn)的路徑為止。

過程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-m

,QUEUE);

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

⑦GOLOOP;89應(yīng)用該算法求解右圖的最短路徑問題,其搜索圖如下圖所示,求解過程中QUEUE的結(jié)果簡(jiǎn)記如下(D(4)代表耗散值為4的s-D分支,其余類推):9091

初始(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é)束。924.動(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)常使用的算法。在其他方面的一些書中--如運(yùn)籌學(xué)方面的書--講到的動(dòng)態(tài)規(guī)劃方法,在形式上可能與這里介紹的有所不同,但其性質(zhì)是一樣的,而且這里所介紹的動(dòng)態(tài)規(guī)劃方法,具有更多的靈活性。動(dòng)態(tài)規(guī)劃原理:求st的最佳(最短)路徑時(shí)，對(duì)其中某個(gè)節(jié)點(diǎn)I，只要考慮sI的最佳路徑，其余sI的路徑是多余的。93過程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;94對(duì)前面圖的例子應(yīng)用該算法,其搜索圖如下圖所示,實(shí)際只剩下兩條搜索路徑,改善了搜索效率。955.最佳圖搜索算法A*(A*算法)在A算法中,如果滿足條件:

h(n)h*(n)

則A算法稱為A*算法。96A*條件舉例8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

64751234576

8將牌1:1將牌2:1將牌6:1將牌8:297A*算法的性質(zhì)一般地說對(duì)任意一個(gè)圖,當(dāng)s到目標(biāo)節(jié)點(diǎn)有一條路徑存在時(shí),如果搜索算法總是在找到一條從s到目標(biāo)節(jié)點(diǎn)的最佳路徑上結(jié)束,則稱該搜索算法是可采納的(Admissibility)。A*就具有可采納性。98A*算法的性質(zhì)A*算法的假設(shè)設(shè)ni,nj是任意兩個(gè)節(jié)點(diǎn),有: C(ni,nj)>

其中為大于0的常數(shù)幾個(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)。99A*算法的性質(zhì)(續(xù)1)定理1.1:對(duì)有限圖,如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在,則算法A一定成功結(jié)束。100

證明:設(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+1

CLOSED(ni一定能找到,因?yàn)閚0CLOSED,nkCLOSED)。由于ni在CLOSED中,必定在第6步被擴(kuò)展,且ni+1被加到OPEN中,因此在OPEN表空之前,ni+1已被處理過。若ni+1是目標(biāo)節(jié)點(diǎn),則搜索成功,否則它被加入到CLOSED中,這兩種情況都與搜索失敗的假設(shè)矛盾,因此對(duì)有限圖不失敗則成功。[證畢]101A*算法的性質(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)。102證明證明：設(shè)d*(n)是A*生成的搜索樹中，從s到任一節(jié)點(diǎn)n最短路徑長(zhǎng)度的值(設(shè)每個(gè)弧的長(zhǎng)度均為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值將增到任意大。設(shè)M=f*(s)/e，M是一個(gè)定數(shù)，所以搜索進(jìn)行到一定程度會(huì)有d*(n)>M，則f(n)≥d*(n)e≥d*(n)(f*(s)/M)≥f*(s)(d*(n)/M)>f*(s)

103A*算法的性質(zhì)(續(xù)3)引理1.2:A*結(jié)束前,OPEN表中必存在f(n)f*(s)

(n是在最佳路徑上的節(jié)點(diǎn))。104證明證明：設(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)。[證畢]105A*算法的性質(zhì)(續(xù)3)定理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ù)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ò)展。得證。107A*算法的性質(zhì)(續(xù)5)定理1.3(可采納性定理):若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑,則A*必能找到最佳解結(jié)束。108可采納性的證明由定理1.1,1.2知A*一定找到一條路徑結(jié)束設(shè)找到的路徑st不是最佳的(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ù)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)。得證。110A*算法的性質(zhì)(續(xù)7)定理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一樣多。簡(jiǎn)寫:如果h2(n)>

h1(n)(目標(biāo)節(jié)點(diǎn)除外),則A1擴(kuò)展的節(jié)點(diǎn)數(shù)A2擴(kuò)展的節(jié)點(diǎn)數(shù)111A*算法的性質(zhì)(續(xù)7)注意:

在定理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ò)展,有

g1(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下圖的搜索圖例子可看出比較的結(jié)果。當(dāng)h≡0時(shí),求得最佳解路(s,C,J,t7),其f*(s)=8,但除t1~t8外所有節(jié)點(diǎn)都擴(kuò)展了,即求出所有解路后,才找到耗散值最小的路徑。而引入啟發(fā)函數(shù)(設(shè)其函數(shù)值如圖中節(jié)點(diǎn)旁邊所示)后,除了最佳路徑上的節(jié)點(diǎn)s,C,J被擴(kuò)展外,其余的節(jié)點(diǎn)都沒有被擴(kuò)展。115對(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ī)模變化。116對(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.27117A*算法的改進(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)的原因在前面的擴(kuò)展中,并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑,如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G目標(biāo)631118120解決的途徑對(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加以限制定義:一個(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)的。h(ni)ninjh(nj)c(ni,nj)123h單調(diào)的例子8數(shù)碼問題:h為“不在位”的將牌數(shù)

-1"在位""不在位" h(ni)-h(nj)=0"不在位""不在位"1"不在位""在位" h(t)=0 c(ni,nj)=1

滿足單調(diào)的條件。 124h單調(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)。125定理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中。126定理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)127定理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)。得證。128h單調(diào)的性質(zhì)(續(xù))定理1.6:若h(n)是單調(diào)的,則由A*所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。即f(ni)f(nj)。

129定理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,得證。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)631118前面的例子:OPEN表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(