人工智能第三章 搜索策略 2010

第三章產(chǎn)生式系統(tǒng)的搜索策略

回溯策略

圖搜索策略：無信息的圖搜索

啟發(fā)式的圖搜索1/15/20231產(chǎn)生式系統(tǒng)的費(fèi)用信息（知識(shí)）完備信息0無信息計(jì)算費(fèi)用控制費(fèi)用規(guī)則應(yīng)用費(fèi)用產(chǎn)生式系統(tǒng)費(fèi)用1/15/202323.1回溯策略1/15/20233

一、回溯算法BACKTRACK

算法中用到的部分變量、常量、謂詞、函數(shù)：變量：DATA，RDATA：狀態(tài)變量RULES,PATH：表變量常量：NIL:空表----LISP語言中的常量，也可用（）謂詞：TERM(DATA):DATA滿足結(jié)束條件時(shí)，為真DEADEND(DATA):DATA不在解路上，為真（往下到達(dá)目標(biāo)的可能性來定義這個(gè)謂詞：若從DATA當(dāng)前狀態(tài)往下走到達(dá)目標(biāo)的可能性很小時(shí)，則放棄這個(gè)狀態(tài)）NULL(X):表X為空表時(shí)，為真函數(shù)：APPRULES(DATA):將DATA所有可用規(guī)則進(jìn)行排序所得到的表FIRST(X):取表Ｘ的頭TAIL(X):取表Ｘ的尾CONS(E,X):將Ｅ加入表Ｘ前1/15/20234BACKTRACK過程RecursiveProcedureBACKTRACK（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←R（DATA）；8．PATH←BACKTRACK（RDATA）；9．ifPATH＝FAIL，goLOOP；10.returnCONS（R，PATH）.1/15/20235帶來的問題及解決方案⑴若DEADEND定義不好，則無限產(chǎn)生新的非終止的狀態(tài)描述。（既不成功又不失敗的節(jié)點(diǎn)）

解決方案：設(shè)置門檻數(shù)，即搜索深度BOUND，當(dāng)遞歸調(diào)用超過這個(gè)深度時(shí)returnFAIL，引起回溯。⑵程序中只有DATA和RDATA，回溯過程中將生成的狀態(tài)都丟棄了，有可能陷入循環(huán)，重復(fù)地產(chǎn)生一系列非終止?fàn)顟B(tài)。（實(shí)質(zhì)屬于情況(1)）

解決方案：在過程中保存一個(gè)狀態(tài)描述表DATALIST：記錄從初始狀態(tài)到當(dāng)前狀態(tài)路徑上的所有狀態(tài)----遞歸變量變成DATALIST，取表頭為DATA。加比較：當(dāng)產(chǎn)生新狀態(tài)RDATA時(shí)，比較是否為DATALIST中的一個(gè)狀態(tài)（在這個(gè)表中），若是，則returnFAIL，引起回溯，選擇其它的Rule。1/15/20236四皇后問題：4枚皇后放在44的國(guó)際象棋棋盤上，如何放置使得它們不能相互俘獲。俘獲：同行；同列；同對(duì)角線綜合數(shù)據(jù)庫：以狀態(tài)為節(jié)點(diǎn)的有向圖狀態(tài)：44矩陣初始狀態(tài)：空矩陣規(guī)則：Rij:ifi=1時(shí)，矩陣中無皇后標(biāo)志，或4i>1時(shí)，矩陣的i-1行有一個(gè)皇后標(biāo)志，then在矩陣的第i行第j列放一個(gè)皇后標(biāo)記結(jié)束條件：TERM為真矩陣中有4個(gè)皇后標(biāo)志，且不能相互俘獲控制策略：回溯DEADEND(DATA):DATA中存在1對(duì)皇后相互俘獲，為真APPRULES(RULES):Rij排在Rik之前j<k二、回溯策略例……四皇后問題1/15/20237四皇后問題存在的問題：回溯的次數(shù)很多，22次回溯。原因：沒有關(guān)于問題的探索性信息指導(dǎo)規(guī)則排序。解決方法之一：在規(guī)則排序過程中使用一些探索性信息，減少回溯次數(shù)，提高算法效率．例：使用函數(shù)diag(i,j)來修改APPRULES(RULES)

diag(i,j)：通過單元（i，j）的最長(zhǎng)對(duì)角線的長(zhǎng)度．

修改后的APPRULES(RULES):ifdiag（i，j）＜diag（i，k）,thenRij排在Rik前．ifdiag（i，j）=diag（i，k），then與以前相同Rij排在Pik之前j<k1/15/20238課堂練習(xí)：請(qǐng)用回溯搜索策略BACKTRACK求解四皇后問題，要求規(guī)則排序使用對(duì)角函數(shù)diag(i,j)。如果diag(i,j)＜diag(i,k)，則在排序中把Rij放在Rik的前面；如果diag(i,j)=diag(i,k)，j<k,則把Rij放在Rik的前面。其中diag(i,j)定義為通過單元(i,j)的最長(zhǎng)對(duì)角線的長(zhǎng)度．1/15/20239三、BACKTRACK算法的修改與補(bǔ)充RecursiveProcedureBACKTRACK（DATA）s1．ifTERM（DATA），returnNIL；s2．ifDEADEND（DATA），returnFAIL；s3．RULES←APPRULES（DATA）；s4．LOOP：ifNULL（RULES）；returnFAIL；s5．R←FIRST（RULES）；s6．RULES←TAIL（RULES）；s7．RDATA←R（DATA）s8．PATH←BACKTRACK（RDATA）；s9．ifPATH＝FAIL，goLOOP；s10．returnCONS（R，PATH）DATA換成DATALISTs0DATA←FIRST(DATALIST)；s0’ifMEMBER(DATA,TAIL(DATALIST)returnFAIL;s2’ifLENGTH(DATALIST)>BOUND,returnFAIL；

s7’RDATALIST←CONS(RDATA,DATALIST）；s8PATH←BACKTRACK1（RDATALIST）1/15/202310兩層以上的回溯×××××1/15/2023113.2圖搜索策略1/15/202312一、相關(guān)概念有向圖：G=(P,A)，P:點(diǎn)集A:弧集弧:兩點(diǎn)間有方向的線。如果有一條弧從節(jié)點(diǎn)ni出發(fā)指向nj；則節(jié)點(diǎn)nj稱為節(jié)點(diǎn)ni的子節(jié)點(diǎn)，節(jié)點(diǎn)ni稱為節(jié)點(diǎn)nj的父親節(jié)點(diǎn)．對(duì)于產(chǎn)生式系統(tǒng)，節(jié)點(diǎn)：用狀態(tài)描述標(biāo)記?。河靡?guī)則標(biāo)記假定圖中的每一個(gè)節(jié)點(diǎn)只有有限個(gè)子節(jié)點(diǎn)。

1/15/202313路：節(jié)點(diǎn)序列(ni0,ni1,…，nik)稱為從節(jié)點(diǎn)ni0到節(jié)點(diǎn)nik的一條長(zhǎng)度為k的路徑，其中，對(duì)于j=1，…，k，每一個(gè)nij都是nij-1的子節(jié)點(diǎn)。如果存在一條從節(jié)點(diǎn)ni到節(jié)點(diǎn)nj的路徑，則節(jié)點(diǎn)nj稱做是從節(jié)點(diǎn)ni出發(fā)可達(dá)到的，節(jié)點(diǎn)nj稱做節(jié)點(diǎn)ni的后裔，節(jié)點(diǎn)ni稱做是節(jié)點(diǎn)nj的祖先。解路徑：從初始節(jié)點(diǎn)到一個(gè)滿足終止條件節(jié)點(diǎn)的路徑。圖搜索策略把尋找從初始狀態(tài)描述到目標(biāo)描述的規(guī)則序列問題轉(zhuǎn)化成尋找有向圖的解路徑問題．1/15/202314有向樹：每一個(gè)節(jié)點(diǎn)最多只有一個(gè)父親的有向圖．根節(jié)點(diǎn)：有向樹中沒有父節(jié)點(diǎn)的節(jié)點(diǎn)葉節(jié)點(diǎn)：有向樹中沒有子節(jié)點(diǎn)的節(jié)點(diǎn)有向樹中節(jié)點(diǎn)的深度:

1)

根節(jié)點(diǎn)的深度是0，

2)其它節(jié)點(diǎn)的深度等于它父節(jié)點(diǎn)的深度加1。1/15/202315加權(quán)有向圖（權(quán)圖）：每條弧線上都有使用費(fèi)用（正數(shù)）的圖。例：從節(jié)點(diǎn)ni到節(jié)點(diǎn)nj的有向孤的費(fèi)用：C(ni,nj)

路徑的費(fèi)用:路徑上所有弧費(fèi)用的和．兩節(jié)點(diǎn)間具有最小費(fèi)用的路徑：是此兩節(jié)點(diǎn)間所有弧費(fèi)用的費(fèi)用總和最小的一條路。

最佳解路徑：費(fèi)用最小的解路徑。

1/15/202316隱含圖：由部分節(jié)點(diǎn)和一組其它節(jié)點(diǎn)生成規(guī)則所確定的圖．圖搜索控制策略的目標(biāo)：從隱含圖出發(fā)生成一個(gè)部分明確的圖，使該明確圖中含有目標(biāo)節(jié)點(diǎn)．圖搜索非形式定義假定：所有隱含圖中有向弧的費(fèi)用大于某一個(gè)小的正數(shù)ε

問題：求隱含圖中初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)集{ti}中任意成員的一條具有最小費(fèi)用的解路徑。1/15/202317二、一般的圖搜索過程GRAPHSEARCHOPEN表：未擴(kuò)展的節(jié)點(diǎn)CLOSED表：已擴(kuò)展或正在擴(kuò)展的節(jié)點(diǎn)G：搜索圖，動(dòng)態(tài)變化，部分明確的圖1/15/2023181．G←{s}，OPEN←（s）．2．CLOSED←NIL．3．LOOP：IFOPEN=NIL,THENFAIL．4．n←FIRST(OPEN)，OPEN←TAIL(OPEN),CONS(n,CLOSED)．5．IFTERM(n)，THEN成功結(jié)束（解路徑可通過追溯G中從n到s的指針獲得）。6．?dāng)U展節(jié)點(diǎn)n，令M={m︱m是n的子節(jié)點(diǎn)，且m不是n的祖先}，G←G∪M7．（設(shè)置指針，調(diào)整指針）對(duì)于mM,(1)若mCLOSED,mOPEN,建立m到n的指針，并CONS(m,OPEN).(2)(a)mOPEN,考慮是否修改m的指針.(b)mCLOSED,考慮是否修改m及在G中后裔的指針。8．重排OPEN表中的節(jié)點(diǎn)（按某一任意確定的方式或者根據(jù)探索信息）。9．GOLOOPProcedureGRAPHSEARCH1/15/202319Note1:算法結(jié)束時(shí)，OPEN:樹的葉節(jié)點(diǎn)CLOSED:1)非葉節(jié)點(diǎn)2)被選來擴(kuò)展但無后裔的葉節(jié)點(diǎn)Note2:如果搜索的隱含圖是一棵樹，步驟6和步驟7得以簡(jiǎn)化：step6:擴(kuò)展節(jié)點(diǎn)n，令M={m︱m是n的子節(jié)點(diǎn)}，G←G∪Mstep7:建立m到n的指針，并CONS(m,OPEN).Note3:如果搜索的隱含圖不是樹，則需確定是否需要指針修改。1/15/2023203.3無信息的圖搜索過程

若在GRAPHSEARCH的步驟8中對(duì)OPEN表中節(jié)點(diǎn)的排序不使用關(guān)于問題的探索性信息，則必須任意規(guī)定一種排序方式，所得到的搜索過程叫作無信息的。一般有兩種無信息的圖搜索過程：深度優(yōu)先搜索與寬度優(yōu)先搜索．在人工智能中，一般說來人們對(duì)無信息的過程不感興趣．1/15/202321無信息的圖搜索過程深度優(yōu)先搜索：排列OPEN表中的節(jié)點(diǎn)時(shí)按它們?cè)谒阉鳂渲械纳疃冗f降排序。深度最大的節(jié)點(diǎn)放在表的前面，深度相等的節(jié)點(diǎn)以任意方式排序．寬度優(yōu)先搜索：在排列OPEN表中節(jié)點(diǎn)時(shí)按它們?cè)谒阉鲌D中的深度遞增順序，深度最小的節(jié)點(diǎn)放在表的前面。

8-數(shù)碼問題例子

1/15/2023223.4啟發(fā)式圖搜索過程

無信息的搜索方式需要產(chǎn)生大量的節(jié)點(diǎn)才能找到解路徑。這些節(jié)點(diǎn)都需要在內(nèi)存中保存起來。由此可見無信息搜索方式所需存儲(chǔ)空間是相當(dāng)大的。而實(shí)際上計(jì)算機(jī)所能提供的存儲(chǔ)總是有限的，因此我們必須尋找效率更高的搜索方法。

1/15/202323啟發(fā)式搜索對(duì)于某些問題，我們可以使用與問題有關(guān)的信息幫助減少搜索量，這種信息叫做啟發(fā)信息。使用啟發(fā)信息指導(dǎo)的搜索過程叫做啟發(fā)式搜索。啟發(fā)信息用在GRAPHSEARCH的步驟8中對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序，把最有希望的節(jié)點(diǎn)排在最前面，使搜索圖沿著有利于獲得解的方向擴(kuò)展。

1/15/202324估價(jià)函數(shù)使用啟發(fā)信息的一種重要方法是采用估價(jià)函數(shù)。即一個(gè)定義在所有狀態(tài)描述上的實(shí)值函數(shù)。估價(jià)函數(shù)例：任意節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的距離度量；棋盤上對(duì)局勢(shì)的度量；一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率等等。用f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)，并且規(guī)定：1.f(n)表示從起點(diǎn)到目標(biāo)，經(jīng)由節(jié)點(diǎn)n最小費(fèi)用路徑上費(fèi)用的估計(jì)。2.以估價(jià)函數(shù)f的遞增次序（函數(shù)低排在前）排列OPEN表中的節(jié)點(diǎn)。具有相等函數(shù)值的節(jié)點(diǎn)以任意次序排序。1/15/202325例：八碼難題估價(jià)函數(shù)：f(n)=d(n)+W(n)其中d(n)是節(jié)點(diǎn)n在搜索樹中的深度，W(n)是與n對(duì)應(yīng)的狀態(tài)描述中偏離目標(biāo)的棋子的個(gè)數(shù)。用這個(gè)估價(jià)函數(shù)的圖搜索過程產(chǎn)生的搜索樹：

1/15/202326估價(jià)函數(shù)的選擇對(duì)搜索結(jié)果起著重要作用如果估價(jià)函數(shù)沒能識(shí)別出真正有希望的節(jié)點(diǎn)，則可能延長(zhǎng)搜索過程，擴(kuò)展較多的節(jié)點(diǎn)。如果估價(jià)函數(shù)過高地估計(jì)了所有點(diǎn)的希望值，則也同樣導(dǎo)致擴(kuò)展大量的節(jié)點(diǎn)．例如在八數(shù)碼問題題例中，如果讓f(n)=d(n)，則得到寬度優(yōu)先搜索．1/15/202327一些概念K(ni,nj)：任意兩點(diǎn)ni和nj間最小費(fèi)用路徑的實(shí)際費(fèi)用.若ni和nj間無通，則函數(shù)K(ni,nj)無定義。{ti}一個(gè)目標(biāo)節(jié)點(diǎn)集合，則h*(n)=min{K(n,ti)}表示從n到目標(biāo)節(jié)點(diǎn)的最小費(fèi)用路徑的費(fèi)用從n到目標(biāo)節(jié)點(diǎn)的任何費(fèi)用為h*（n）的路徑都是最佳解路徑。對(duì)不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)n，h*（n）無定義。設(shè)g*(n)=K(s，n)，則g*(n)是從s到n的最佳解路徑的費(fèi)用。設(shè)f*(n)=g*(n)+h*(n)，則f*(n)是通過n點(diǎn)的最佳解路徑的費(fèi)用．1/15/202328A算法和A*算法

設(shè)f(n)=g(n)+h(n)，我們稱使用f(n)做為估價(jià)函數(shù)的GRAPHSEARCH算法為算法A。

其中，假定g*(n)≤g(n)如果算法A中使用的啟發(fā)函數(shù)h(n)對(duì)任何節(jié)點(diǎn)n都有h(n)≤h*(n)，則稱其為算法A*。

1/15/2023293.5A*算法的可采納性

如果一個(gè)搜索算法對(duì)于任何具有解路徑的圖都能找到一條最佳路徑，則稱此算法為可采納的。

可以證明：A*算法是可采納的（如果解路徑存在，A*一定終止找到最佳解路徑）1/15/202330定理1GRAPHSEARCH對(duì)有限圖必然終止。證明：GRAPHSEARCH算法將在第3步將OPEN表中的節(jié)點(diǎn)用光而結(jié)束；或在第5步，找到目標(biāo)節(jié)點(diǎn)而結(jié)束。在算法的每一次循環(huán)都要從OPEN表中刪除一個(gè)節(jié)點(diǎn)，并生成有限個(gè)后繼加到OPEN表中。對(duì)有限圖來說，顯然這一循環(huán)不能無限進(jìn)行下去。結(jié)論得證。A*算法的可采納性1/15/202331引理1若A*不終止，OPEN表中節(jié)點(diǎn)的估價(jià)函數(shù)值可以無限變大。

證明：設(shè)n是OPEN表中的任的一節(jié)點(diǎn)，d*(n)是隱含圖中從s到n的最短路徑的長(zhǎng)度，e是圖中每條弧的最小費(fèi)用。于是有g(shù)*(n)≥d*(n).e又g(n)≥g*(n)≥d*(n).e，f(n)=g(n)+h(n)，且h(n)≥0因此f(n)≥g(n)≥

d*(n).e若A*不終止，OPEN表中節(jié)點(diǎn)的d*值會(huì)不斷增大，因此f值也會(huì)不斷增大。

A*算法的可采納性1/15/202332定理2若存在s到目標(biāo)的路，則算法A*終止前的任何時(shí)刻，OPEN表中總存在一個(gè)節(jié)點(diǎn)n’，n’在從s到目標(biāo)的最佳路徑上，且滿足f(n’)≤f*(s)

證明：設(shè)P：n0,n1,……,nk是一條最佳解路徑，其中，nk是目標(biāo)點(diǎn)，n0=s.在A*結(jié)束之前，從左向右掃描序列P，n’是P中第一個(gè)在OPEN表中的節(jié)點(diǎn)(這樣的n’是存在的：因?yàn)殚_始n0在OPEN上，算法結(jié)束前，若擴(kuò)展ni，則ni+1在OPEN上，此時(shí)不可能擴(kuò)展到nk)。由A*的定義，有f(n’)=g(n’)+h(n’)A*算法的可采納性1/15/202333因?yàn)閚’處在通往目標(biāo)的最佳解路徑上，設(shè)(n0,n1,……,n’)是s到n’的最佳解路徑。n’的所有祖先都在CLOSED表上，所以(n0,n1,……,n’)是A*發(fā)現(xiàn)的一條通向n’的最佳解路徑，g(n’)=g*(n’)由A*算法知：h(n’)≤h*(n’)，故f(n’)≤g*(n’)+h*(n’)=f*(n’)而對(duì)最佳路上任意一點(diǎn)n，有：f*(n’)=f*(s)因此，f(n’)≤f*(s)證畢。A*算法的可采納性……定理2

1/15/202334定理3若存在從s到目標(biāo)的解路，則算法A*必終止。

證明：若算法A*不終止，由引理1知，OPEN表中任意節(jié)點(diǎn)的f值隨著算法A*的運(yùn)行可以任意增大。由定理2知，算法A*終止前的任何時(shí)刻，OPEN表中總存在一個(gè)節(jié)點(diǎn)n’，使得f(n’)≤f*(s)。矛盾。A*算法的可采納性1/15/202335推論OPEN表中的任一滿足f(n)<f*(n)的節(jié)點(diǎn)n，最終將被算法A*選作擴(kuò)展節(jié)點(diǎn)

證明：設(shè)目標(biāo)節(jié)點(diǎn)集為{ti}，顯然，f(ti)≥f*(s)由定理3知，A*必停止。若停在第3步，則OPEN表中的任一節(jié)點(diǎn)都被擴(kuò)展；若停在第5步，則OPEN表中f(n)<f*(s)=f*(n)的節(jié)點(diǎn)必在找到ti之前被擴(kuò)展。證畢。A*算法的可采納性1/15/202336定理4算法A*是可采納的（即如果解路徑存在，A*一定找到最佳解路徑而終止）．證明：由定理3知，算法A*必終止。由定理2知，算法A*終止前的任何時(shí)刻，OPEN表中總存在一個(gè)節(jié)點(diǎn)n’，使得f(n’)≤f*(s)，算法A*不會(huì)終止在第3步，因此必終止在第5步，因找到一個(gè)目標(biāo)節(jié)點(diǎn)而結(jié)束。設(shè)t是算法A*找到的目標(biāo)點(diǎn)，

（下面用反證法證明t在最佳解路上）A*算法的可采納性1/15/202337若t不在最佳解路徑上，則f(t)=g(t)＞f*(s)由定理2，A*算法終止前，OPEN表中總有一點(diǎn)n’，使f(n’)≤f*(s)，因此f(n’)≤f(t)；在OPEN表的排序中，節(jié)點(diǎn)n’應(yīng)排在節(jié)點(diǎn)t的前面。因此，算法A*算法終止前應(yīng)選n’去擴(kuò)展，而不會(huì)選t，與算法A*終止于t矛盾。

證畢A*算法的可采納性……定理4

1/15/202338定理5算法A*選擇的任意擴(kuò)展點(diǎn)都有f(n)≤f*(s)證明：若n是目標(biāo)點(diǎn)，由定理4，f(n)≤f*(s)若n不是目標(biāo)點(diǎn)，由定理2，A*算法終止前，OPEN表中總有一點(diǎn)n’，使f(n’)≤f*(s)此時(shí)，算法A*選擇n而沒有選擇n’，必有：f(n)≤f(n’)≤f*(s)證畢。A*算法的可采納性1/15/202339定義設(shè)A1和A2是兩個(gè)A*算法，分別使用如下兩個(gè)估價(jià)函數(shù)：f1(n)=g1(n)+h1(n)f2(n)=g2(n)+h2(n)其中，h1(n)和h2(n)是h*的兩個(gè)下界．若對(duì)于所有的非目標(biāo)節(jié)點(diǎn)n，都有h2(n)＞h1(n)，則稱算法A2比算法A1有較多的信息．3.6A*算法的比較1/15/202340討論：?jiǎn)l(fā)函數(shù)的啟發(fā)能力在于它所具有的啟發(fā)性信息。1.當(dāng)h(n)≡0時(shí)，反映了啟發(fā)函數(shù)完全沒有啟發(fā)信息，要擴(kuò)展較多的節(jié)點(diǎn)．2.在具有可采納性的前提下，0≤h≤h*，h*定出了h的上界，當(dāng)h越接近h*時(shí)，它的啟發(fā)能力就越大．

A*算法的比較1/15/202341例八碼難題的A*算法的比較．圖3.7的估價(jià)函數(shù)：f1(n)=d(n)，h1(n)≡0，采用寬度優(yōu)先搜索；圖3.8的估價(jià)函數(shù)：f2(n)=d(n)+w(n)，h2(n)≡w(n)．對(duì)于所有非目標(biāo)節(jié)點(diǎn)，有h2(n)＞h1(n)，因此，圖3.7所用算法不但比圖3.8所用算法有較多的信息，而且擴(kuò)展的節(jié)點(diǎn)數(shù)要少。A*算法的比較1/15/202342定理6如果A1和A2是兩個(gè)A*算法，算法A2比A1有較多的信息，且它們搜索同一個(gè)隱含圖。若該圖存在解路徑，當(dāng)這兩個(gè)算法終止時(shí)，A2所擴(kuò)展的每一節(jié)點(diǎn)也必由A1所擴(kuò)展，即：A2擴(kuò)展的節(jié)點(diǎn)數(shù)≤A1擴(kuò)展的節(jié)點(diǎn)數(shù)證明：對(duì)A2搜索樹中的節(jié)點(diǎn)深度使用數(shù)學(xué)歸納法。設(shè)n是A2所擴(kuò)展的任一節(jié)點(diǎn)，p(n)記n在搜索樹中的深度，往證n被A1擴(kuò)展。A*算法的比較……定理6

1/15/202343當(dāng)p(n)=0時(shí)，n＝s．若s不是目標(biāo)節(jié)點(diǎn)，這兩個(gè)算法都必將擴(kuò)展s。若s是目標(biāo)節(jié)點(diǎn)，這兩個(gè)算法都不必?cái)U(kuò)展任意節(jié)點(diǎn)（包括s）．假設(shè)p(n)≤k時(shí)，n被算法A2擴(kuò)展，n也被算法A1所擴(kuò)展.設(shè)p(n)＝k＋1，因節(jié)點(diǎn)n被A2擴(kuò)展，由于n的祖先點(diǎn)被A2擴(kuò)展，根據(jù)歸納假設(shè)，節(jié)點(diǎn)n的在A2搜索樹中的所有祖先都被算法A1所擴(kuò)展．A*算法的比較……定理61/15/202344因此，節(jié)點(diǎn)n在A1的搜索樹中，且在A1的搜索樹中存在一條從s到n的路。由于A2搜索樹中點(diǎn)n之前的樹是A1搜索中點(diǎn)n之前的樹的子樹，g1(n)≤g2(n)又因?yàn)閔1(n)<h2(n)，所以f1(n)<f2(n).由于n被A2擴(kuò)展，由定理5知：f2(n)≤f*(s)故f1(n)<f2(n)≤f*(s).由推論知，點(diǎn)n必被A1擴(kuò)展，歸納完成。A*算法的比較……定理6

1/15/202345定義如果啟發(fā)函數(shù)h對(duì)任何節(jié)點(diǎn)ni和nj，只要nj是ni的后繼，都有h(ni)－h(huán)(nj)≤c(ni,nj)h(t)=0（t是目標(biāo)節(jié)點(diǎn)）則稱啟發(fā)函數(shù)h滿足單調(diào)限制．3.7單調(diào)限制1/15/202346定理7如果A*算法的啟發(fā)函數(shù)h滿足單調(diào)限制，則當(dāng)算法A*選擇節(jié)點(diǎn)n擴(kuò)展時(shí)，就已經(jīng)發(fā)現(xiàn)了通向節(jié)點(diǎn)n的最佳路徑，即g(n)=g*(n)．證明：設(shè)n是算法A*選出擴(kuò)展的任一節(jié)點(diǎn)。若n=s，則g(n)=g*(n)=0，算法A*已發(fā)現(xiàn)通向s的最佳路徑．若n≠s，設(shè)序列P=(s=n0，n1，…，nk=n)是從s到n的一條最佳路徑(不知道是否在A*的搜索樹中)。單調(diào)限制的性質(zhì)……定理7

1/15/202347當(dāng)算法A*選擇n進(jìn)行擴(kuò)展時(shí)：設(shè)P中從n0開始，串n0，…，nt都在CLOSED表中，即nt是P中從左向右CLOSED表中的最后一個(gè)節(jié)點(diǎn)，且nt≠n.此時(shí)，nt的后繼節(jié)點(diǎn)nt+1在OPEN表中．因?yàn)镻是從s到nk的最佳路，所以:g(nt+1)=g*(nt+1)單調(diào)限制的性質(zhì)……定理7

1/15/202348由已知h(n)滿足單調(diào)限制，對(duì)任意i=0,…,k-1,有g(shù)*(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)單調(diào)限制的性質(zhì)……定理7

1/15/202349因?yàn)閠≤k－1，所以t<k利用傳遞性，我們得到

g*(nt+1)+h(nt+1)≤g*(nt+2)+h(nt+2)≤...≤g*(nk)+h(nk)

而g(nt+1)=g*(nt+1)所以f(nt+1)≤g*(nk)+h(nk)＝g*(n)+h(n)又已知g*(n)≤g(n)(算法A的假設(shè)）單調(diào)限制的性質(zhì)……定理7

1/15/202350若g*(n)<g(n),則：f(nt+1)<g(n)+h(n)=f(n)說明A*算法選擇n擴(kuò)展時(shí)，OPEN表中有nt+1的f值比f(n)小，與A*選擇n擴(kuò)展矛盾。因此有：g(n)=g*(n)．單調(diào)限制的性質(zhì)……定理7

1/15/202351定理8如果A*算法啟發(fā)式函數(shù)h滿足單調(diào)限制，則A*所擴(kuò)展的節(jié)點(diǎn)序列的估價(jià)函數(shù)值是非遞減的．證明：設(shè)n1和n2是A*擴(kuò)展的點(diǎn)序列中相鄰的兩點(diǎn)，n1在前。若擴(kuò)展n1時(shí)，n2在OPEN表上，顯然:f(n1)≤f(n2)單調(diào)限制的性質(zhì)……定理8

1/15/202352若擴(kuò)展n1時(shí)，n2不在OPEN表上（自然也不在CLOSED上），則A*擴(kuò)展完n1后，立刻擴(kuò)展n2，n2是n1的后繼點(diǎn)。于是，擴(kuò)展n2時(shí)有：f(n2)=g(n2)+h(n2)=g*(n1)+c(n1,n2)+h(n2)=g(n1)+c(n1,n2)+h(n2)(由定理7）由單調(diào)性，c(n1,n2)+h(n2)≥

h(n1)所以f(n2)≥g(n1)+h(n1)=

f(n1)單調(diào)限制的性質(zhì)……定理8

1/15/202353A*算法的總結(jié)與討論1.

A*算法搜索隱含圖時(shí)，有解必停，且必停在最佳解路上；2.A*算法啟發(fā)函數(shù)的啟發(fā)能力在于它所具有的啟發(fā)性信息。在滿足h(n)≤h*(n)的前提下，啟發(fā)函數(shù)越大，其所包含的啟發(fā)信息越多，所擴(kuò)展的節(jié)點(diǎn)越少；1/15/202354A*算法的總結(jié)與討論3.若啟發(fā)函數(shù)滿足單調(diào)限制，則每走一步都在最佳解路上，且啟發(fā)式函數(shù)不減，簡(jiǎn)化了算法的第7步（調(diào)整指針）；4.當(dāng)A*不滿足單調(diào)限制時(shí)，后擴(kuò)展節(jié)點(diǎn)的f函數(shù)值可能比先擴(kuò)展節(jié)點(diǎn)的f函數(shù)值小，可以對(duì)算法A*做一些適當(dāng)?shù)男薷?，以提高算法A*的執(zhí)行效率：1/15/202355A*算法的總結(jié)與討論

保存一個(gè)全局變量F，存放A*已擴(kuò)展節(jié)點(diǎn)的估價(jià)函數(shù)值的最大值,根據(jù)定理5，F(xiàn)≤f*(s)．若OPEN表中有節(jié)點(diǎn)n，滿足f(n)＜F，由推論知，n最終必將被擴(kuò)展．可以不選最小的f值而選最小的g值．因?yàn)檫@些節(jié)點(diǎn)最終都必將被擴(kuò)展．這樣能提高擴(kuò)展節(jié)點(diǎn)在最佳路徑上的幾率，減少指針的調(diào)整，提高算法效率．1/15/2023563.8算法A的啟發(fā)能力定義設(shè)A1和A2是兩個(gè)啟發(fā)式算法，它們分別使用估價(jià)函數(shù)f1和f2，如果在尋找解路徑的過程中，A1所用的計(jì)算費(fèi)用比A2少，則說A1比A2有較強(qiáng)的啟發(fā)能力，也可以說估價(jià)函數(shù)f1比f2有較強(qiáng)的啟發(fā)能力．1/15/202357算法A的啟發(fā)能力算法A的啟發(fā)能力受如下三個(gè)重要因素的影響（1）算法A所找到的解路徑的費(fèi)用。（2）算法A在尋找這條解路徑的過程中所需要擴(kuò)展的節(jié)點(diǎn)數(shù)。（3）計(jì)算啟發(fā)函數(shù)所需要的計(jì)算量。1/15/202358h(n)≤h*(n)保證了A*的可采納性，可采納性可能意味著算法需要擴(kuò)展更多的節(jié)點(diǎn)，使總的費(fèi)用提高。有時(shí)，犧牲可采納性可以提高算法的啟發(fā)能力。例：h(n)=P(n)+3S(n)P(n)：每個(gè)數(shù)碼離“家”距離的和S(n)：對(duì)n的記分算法A的啟發(fā)能力1/15/202359有時(shí)，把估價(jià)函數(shù)寫成：f=g+h的形式很小時(shí)，強(qiáng)調(diào)寬度優(yōu)先

很大時(shí)，強(qiáng)調(diào)啟發(fā)分量一般與深度成反比。算法A的啟發(fā)能力1/15/202360正向搜索：從初始節(jié)點(diǎn)到目標(biāo)的搜索反向搜索：從目標(biāo)節(jié)點(diǎn)到初始節(jié)點(diǎn)的搜索雙向搜索：正向和反向搜索的結(jié)合搜索需要產(chǎn)生的節(jié)點(diǎn)數(shù)寬度優(yōu)先搜索，使用雙向搜索要優(yōu)越許多對(duì)于啟發(fā)式搜索，評(píng)價(jià)單向搜索和雙向搜索的優(yōu)劣很復(fù)雜，使用不當(dāng)可能是單向搜索量的二倍。3.9有關(guān)算法1/15/202361分階段搜索：為了完成搜索過程，可對(duì)搜索圖進(jìn)行修剪，釋放出一部分存儲(chǔ)空間。把OPEN表具有最小f值的一些節(jié)點(diǎn)打上標(biāo)記，記住這些結(jié)點(diǎn)和通向這些點(diǎn)的最佳路徑，刪去搜索圖其余部分。然后回復(fù)節(jié)點(diǎn)和路徑，重新開始搜索。