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

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

1狀態(tài)空間搜索概述

2回溯策略

3圖搜索策略

4盲目的圖搜索過程

5啟發(fā)式圖搜索過程搜索空間示意圖

搜索策略的任務(wù):確定選擇規(guī)則的方式兩種基本方式：盲目搜索(無信息引導(dǎo))：按固定的步驟啟發(fā)式搜索(有信息引導(dǎo))：考慮領(lǐng)域的知識狀態(tài)空間：求任一解路：回溯、爬山、寬度、深度、限定范圍搜索、好的優(yōu)先搜索.求最佳解路：大英博物館法、分支限界法、動態(tài)規(guī)劃法、最佳圖搜索法A*.問題歸約：求與或圖：一般求與或圖搜索法AO*、極大極小法、α-β剪支法、啟發(fā)式剪支法.1狀態(tài)空間搜索概述

1.1圖的概念

圖是由節(jié)點及連接它們的弧的集合組成.

有向圖.節(jié)點深度的表示：dn+1=dn+1路徑：N個有序的節(jié)點序列中，若相鄰的每對節(jié)點都表示一條弧，則稱該序列為長度為N的一條路徑.路徑耗散值：令C（ni，nj）為節(jié)點ni到節(jié)點nj這段路徑（或弧線）的耗散值，一條路徑的耗散值等于連接這條路徑各節(jié)點間所有弧線耗散值的總和。遞歸公式：C（ni，t）=C（ni，nj）+C（nj，t）節(jié)點的擴展：操作算子（規(guī)則）作用到節(jié)點（某一狀態(tài)）上，生成出其所有的后繼節(jié)點（新狀態(tài)），并給出解弧線的耗散值（規(guī)則代價）.1.2狀態(tài)空間圖描述的特點形式:最直觀的，顯式描述.對應(yīng)關(guān)系:節(jié)點表示問題的狀態(tài)弧表示狀態(tài)之間的關(guān)系，即求解問題的步驟初始狀態(tài)對應(yīng)于問題的已知信息，是根節(jié)點尋找從一種狀態(tài)轉(zhuǎn)換為另一種狀態(tài)的某個操作算子序列,就等價于在一個圖中尋找從一種狀態(tài)到另一種狀態(tài)的一條路徑.1.3狀態(tài)空間的搜索

思想：將問題求解轉(zhuǎn)換為狀態(tài)空間的圖搜索表示方法：定義一狀態(tài)空間S（表示狀態(tài)的數(shù)據(jù)結(jié)構(gòu)）規(guī)定一個或多個屬于該空間的初始狀態(tài)S0規(guī)定一個或多個屬于該空間的目標狀態(tài)G規(guī)定一組規(guī)則O（狀態(tài)轉(zhuǎn)換的操作）目的：將非形式的問題描述轉(zhuǎn)換成狀態(tài)空間形式描述后，便可利用狀態(tài)空間的搜索方法應(yīng)用規(guī)則和控制策略（搜索技術(shù)），找出從初始狀態(tài)到目標狀態(tài)的一條（或一組）路徑1.4搜索的概念及問題

在狀態(tài)空間中，問題的求解就是搜索即通過搜索某部分狀態(tài)空間,以求得由規(guī)則序列組成的一個解答的過程，它對應(yīng)于將一個隱式圖中包含目的節(jié)點的一部分狀態(tài)變?yōu)轱@式圖的過程搜索過程存在的幾個基本問題：

1）有解?是否一定能找到一個解2）終止?是否能終止運行或陷入一個死循環(huán)3）最佳解?若找到解時，是否是最佳解4）代價?時間與空間復(fù)雜性如何

搜索過程的具體步驟：

從初始狀態(tài)出發(fā)，并將它作為當前狀態(tài);掃描規(guī)則集合，挑選適用于當前狀態(tài)的一些規(guī)則作用在其上而得到新的狀態(tài)，并建立與父母節(jié)點的連接指針;檢查所生成的新狀態(tài)是否滿足結(jié)束狀態(tài)，如果滿足，則得解，并可沿著有關(guān)指針從結(jié)束狀態(tài)反向到達開始狀態(tài)，給出一解答路徑；否則，將這新狀態(tài)作為當前狀態(tài)，返回前一步再進行搜索.2回溯策略

含義:按規(guī)則的一個固定排序，系統(tǒng)地嘗試狀態(tài)空間中各種不同路徑的技術(shù).是一種盲目搜索.過程：從初始狀態(tài)出發(fā)，不停地、試探地尋找路徑,當遇到“死胡同”(無可用規(guī)則或規(guī)則都用完)就回溯到路徑中最近的父節(jié)點上，查看該節(jié)點是否還有其他的子節(jié)點未被擴展，如有，則沿這些子節(jié)點繼續(xù)搜索；如果找到目標，就成功退出搜索，返回解的路徑.特征：呈現(xiàn)出遞歸的性質(zhì)。求解過程在每個節(jié)點上的檢查遵循著遞歸方式.

遞歸的思想從前有座山……

從前有座山……

從前有座山……遞歸過程示例：--階乘函數(shù)的遞歸intfactorial(intn){if(n==1){return1;}else{returnn*factorial(n-1);}}

只要初始值大于零，這個函數(shù)就能夠終止停止的位置稱為基線條件，可返回一個結(jié)果遞歸必須至少擁有一個基線條件，且須確保最終會達到某個基線條件；一些符號的含義：變量：

DATA=當前狀態(tài)；RULES=規(guī)則集合序列表；R=當前調(diào)用規(guī)則；RDATA=新生成的狀態(tài)；PATH=當前解路徑表常量：

NIL=空表；FAIL=回溯點標記；LOOP=循環(huán)標號；謂詞：

TERM(DATA)；DEADEND(DATA)；NULL(RULES)；函數(shù)：APPRULES求可應(yīng)用的規(guī)則表；FIRST從表中取表頭的一個元素,TAIL除去表頭一個元素后得到的新表；GEN調(diào)用規(guī)則生成新狀態(tài)；CONS在表頭插入新元素，構(gòu)造新表；遞歸過程BACKTRACK(DATA)

BACKTRACK(DATA)ifTERM(DATA),returnNIL;滿足終止條件ifDEADEND(DATA)returnFAIL;

不合法，須回溯RULES←APPRULES(DATA)可應(yīng)用的規(guī)則表.LOOP:ifNULL(RULES)returnFAIL;

無可用規(guī)則，須回溯R←FIRST(RULES);選頭條規(guī)則RULES←TAIL(RULES);刪除該規(guī)則RDATA←GEN（R，DATA）;把R作用于當前狀態(tài)PATH←BACKTRACK(RDATA)對新狀態(tài)遞歸調(diào)用ifPATH=FAILgoLOOP;如遞歸失敗，選另一規(guī)則returnCONS(R,PATH);否則把R加在解路徑表中，過程返回解路徑規(guī)則表（或局部解路徑子表）.舉例綜合數(shù)據(jù)庫：DATA=L（表），L元素用{ij}表示，i，j的值域為{1，2，3，4}。即L表的元素表示皇后所在的行和列。如（12243143）、（13213442）、（1121）、（1122）、（112331）.四皇后問題：在一個4*4的國際象棋棋盤上，一次一個地擺布四枚皇后棋子，擺好后要滿足每行、每列和對角線上只允許出現(xiàn)一枚棋子，即棋子間不能相互俘獲.棋盤的幾種狀態(tài)

共16個規(guī)則，每條規(guī)則Rij表示滿足前提條件下，在ij處放一個棋子.控制策略:若以R11、R12、R13、R14、R21、…、R44這種先行后列固定的排序方式調(diào)用遞歸時，搜索示意圖如下圖所示.

規(guī)則集：()Q(11)R11(*,21)R21Q①(*,22)Q②(*,23)Q(*,*,31)Q③(*,*,32)Q④(*,*,33)Q⑤(*,*,34)Q⑥⑦(*,24)Q(*,*,31)⑧(*,*,32)(*,*,*,41)Q⑨(*,*,*,42)Q⑩(*,*,*,43)Q⑾(*,*,*,44)Q⑿⒀(*,*,*,33)⒁(*,*,*,34)⒂⒃⒄(12)Q(*,21)⒅(*,22)⒆(*,23)⒇(*,24)(*,*,31)(*,*,*,41)(21)(*,*,*,42)(22)(*,*,*,43)四皇后問題的固定排序搜索樹

思考：當規(guī)則序列以R11、R21、R31、R41、R12、R22、R32、…、R44這種“先列后行”固定排序方式調(diào)用BACKTRACK函數(shù)時，畫出四皇后問題的搜索樹，并標出所有回溯的先后順序。與例題的搜索過程有何異同？這2種方法存在什么問題？思路：

利用問題有關(guān)信息對規(guī)則進行動態(tài)排序方法：定義一個對角線函數(shù)Maxdiag（i，j）。該函數(shù)計算棋盤上ij單元的最長對角線長度，通過比較不同單元的函數(shù)值來決定每行（列）Rij的排序例如，若Maxdiag（i，k）小于Maxdiag（i，j），則規(guī)則順序為（Rik，Rij），即對角線短的單元，相應(yīng)的規(guī)則排在前頭，若相同，則維持原順序排序結(jié)果：按此知識排列的序列為R12、R13、R11、R14、R21、R24、R22、R23、R31、R34、R32、R33、R42、R43、R41、R44（3、3、4、4……）四皇后問題的改進：

()(12)R12(12,21)R21①Q(mào)Q(12,24)R24(12,24,31)(12,24,31,42)(12,24,31,43)②R31R42R43QQQQ

四皇后問題的動態(tài)排序搜索樹順序:R12、R13、R11、R14、R21、R24、R22、R23、R31、R34、R32、R33、R42、R43、R41、R44BACKTRACK(DATA)算法存在的問題:重復(fù)狀態(tài)引起的死循環(huán)搜索深度無限改進策略：用狀態(tài)鏈路變量DATALIST代替原狀態(tài)變量DATA;設(shè)置出現(xiàn)重復(fù)狀態(tài)的回溯點設(shè)置深度范圍限制的回溯點BACKTRACK1(DATALIST):

1

DATAFIRST(DATALIST)參數(shù):初始到當前狀態(tài)的逆序表2ifMEMBER(DATA,TAIL(DATALIST),returnFAIL回老路3

ifTERM(DATA),returnNIL到達目標，成功返回4ifDEADEND(DATA),returnFAIL到達不合理狀態(tài)，退回5

ifLENGTH(DATALIST)>BOUND,returnFAIL到深度限制6

RULESAPPRULES(DATA)得出可應(yīng)用的規(guī)則集7

LOOP:ifNULL(RULES),returnFAIL進入死胡同，退回8

RFIRST(RULES)取出第一條可應(yīng)用規(guī)則9

RULESTAIL(RULES)10RDATAGEN（R，DATA)運用規(guī)則，生成新狀態(tài)11RDATALISTCONS(RDATA,DATALIST)12PATHBACKTRACK1(RDATALIST)遞歸13ifPATH=FAIL,goLOOP14returnCONS(R,PATH)如果當前狀態(tài)S未達到目標，就對它的第一個子狀態(tài)Schild1遞歸調(diào)用回溯過程。如果在以Schild1

為根的子圖中未找到目標，就對它的兄弟子狀態(tài)Schild2再遞歸調(diào)用回溯過程;像這樣重復(fù)進行直到某個子狀態(tài)的后裔是目的狀態(tài)或者所有的子狀態(tài)都搜索完為止。而且，如果S的子狀態(tài)中沒有一個能達到目標，便回溯到S的父狀態(tài)，算法開始對S的兄弟狀態(tài)進行搜索;算法以這種方式搜索直到找到目的狀態(tài)或遍歷了所有的狀態(tài)空間為止.回溯過程總結(jié)：A1B2C8D11E3F6G9H10I4J5K7①②③④⑤⑥⑦⑧⑨⑩一個狀態(tài)空間中應(yīng)用回溯搜索的示意圖優(yōu)點：節(jié)省空間；缺點：回溯掉的部分無法復(fù)用.

3圖搜索策略

一般的圖搜索算法：1.

G:=G0(G0=s)，Open:=(s)；G表示圖，s為初始節(jié)點，設(shè)置Open表，放待擴展的節(jié)點，最初只含s.2.

Closed:=()；設(shè)置Closed表,放已擴展完的節(jié)點，起始為空表.3.

LOOP:IFOpen:=()，THENEXIT(FAIL);4.

n:=FIRST(Open)，REMOVE(n,Open)，ADD(n,Closed);稱n為當前節(jié)點.5.

IFGOAL(n)，THENEXIT(SUCCESS)；由n返回到s的路徑上的指針,可給出解路徑.如果控制系統(tǒng)保留了所有的規(guī)則應(yīng)用后生成并連接起來的狀態(tài)記錄圖，則稱控制系統(tǒng)使用了圖搜索策略.6.

EXPAND(n)→(mi),G:=ADD(mi,G)；（為實現(xiàn)無環(huán)路,子節(jié)點集{mi}中應(yīng)不包含n的先輩節(jié)點.）7.

標記和修改指針（當出現(xiàn)多路徑的情況，根據(jù)路徑耗散值選擇最好的解路,此時子節(jié)點分3種情況考慮{mi}={mj}∪{mk}∪{ml}）ADD(mj，Open),并標記mj連接到n的指針;若子節(jié)點（mj)為Open和Closed中未出現(xiàn)過的.計算是否要修改mk、ml到n的指針；若子節(jié)點已出現(xiàn)過，1）mk表示已出現(xiàn)在Open中的子節(jié)點，2）ml表示已出現(xiàn)在Closed中的子節(jié)點.計算是否要修改ml到其后繼節(jié)點的指針；8．對Open中的節(jié)點按某種原則重新排序；9．GOLOOP；

學(xué)習(xí)重點：{mi}節(jié)點類型說明mjmkml12345已擴展過的節(jié)點(Closed)待擴展的節(jié)點(Open)，狀態(tài)的排列次序就是搜索的次序s????擴展節(jié)點6得到的搜索圖

具體示例（mk）：

實心圓點：Closed中節(jié)點空心圓點：Open中節(jié)點假設(shè)每段為單位耗散現(xiàn)在要擴展節(jié)點6，設(shè)生成兩個子節(jié)點，其中節(jié)點4(mk)已在Open中;原路徑（s→3→2→4）耗散值為5，新路徑（s→6→4）耗散值為4，所以節(jié)點4的解路指針應(yīng)修正（2→6），如圖所示。

如果下一循環(huán)要擴展節(jié)點1，若節(jié)點1只生成一個子節(jié)點2(ml);

比較耗散值，顯然要修改節(jié)點2的指針（3→1）;

由此又會引起節(jié)點4指針的修改（６→２），如圖（b）所示。擴展節(jié)點1得到的搜索圖

具體示例（續(xù)）：4盲目的圖搜索過程

1)寬度優(yōu)先搜索

搜索次序：一層一層地擴展下去，直到搜索到目的狀態(tài)（如果目的狀態(tài)存在）?！獭獭獭獭獭獭獭獭獭獭虒挾葍?yōu)先搜索過程

Procedurebreadth_first_searchBegin

Open:=[start];closed:=[]*初始化

Whileopen≠[]do

Begin從Open表中刪除第一個狀態(tài)n,并放入closed中;

ifn=目的狀態(tài)thenreturn(success);

else生成n的所有子狀態(tài);從中刪除已在Open或closed中出現(xiàn)的狀態(tài);

*避免循環(huán)搜索;將其余子狀態(tài),按生成次序加入到Open表后端.

End;

End.23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標8234187654

八數(shù)碼寬度優(yōu)先搜索91011121314151617小結(jié)：寬度優(yōu)先搜索的性質(zhì)當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法2)深度優(yōu)先搜索

搜索沿一個方向一直擴展下去，直到達到一定的深度，如未找到目的狀態(tài)或無法再擴展下去，便回溯到另一條路徑繼續(xù)搜索，若還沒有找到目的狀態(tài)或無法再擴展時，再回溯到另一條路徑搜索……..。深度優(yōu)先搜索法中的搜索次序√√√√√√√√√√√√√√Proceduredepth_first_searchBeginOpen:=[start];closed:=[]；d=深度限制值*初始化

WhileOpen≠[]doBegin

從Open表中刪除第一個狀態(tài),并放入closed表中;ifn=目的狀態(tài)thenreturn(success);elseifn的深度>dthencontinue;*回溯

else生成n的所有子狀態(tài);

從中刪除已在Open或closed表中出現(xiàn)的狀態(tài);*避免循環(huán)搜索;

將其余狀態(tài),按生成的次序加入到Open表的前端.End;End.深度優(yōu)先搜索過程：231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標八數(shù)碼深度優(yōu)先搜索12378466efd=3小結(jié)：深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關(guān)的方法5啟發(fā)式圖搜索過程*

核心思想：利用所處理問題的啟發(fā)信息引導(dǎo)搜索目的：減少搜索范圍，降低問題復(fù)雜度.1)啟發(fā)式圖搜索算法A基本思路：定義一個評價函數(shù)f，對當前待搜索狀態(tài)進行評估（既考慮從起始節(jié)點到節(jié)點n的花費，又考慮從節(jié)點n到達目標節(jié)點的費用），然后找出一個最有希望的節(jié)點來擴展.函數(shù)形式為：f(n)=g(n)+h(n).n為被評價的節(jié)點。用此函數(shù)值來排列OPEN表中節(jié)點順序的圖搜索算法稱為A算法.

函數(shù)符號說明：g*(n)、h*(n)：表示各部分實際最短路徑的耗散值.f*(n)=g*(n)+h*(n)：表示從S出發(fā)，通過節(jié)點n到目標節(jié)點g的最短路徑的耗散值.f(n)、g(n)和h(n)為相應(yīng)路徑耗散值的估計值，是一種預(yù)測。A算法就是利用這種預(yù)測，來達到有效搜索的目的.g（n）可根據(jù)搜索歷史情況對g*（n）作出估計，顯然有g(shù)（n）>=g*（n）.h（n）則依賴于啟發(fā)信息，通常稱為啟發(fā)函數(shù)，是要對未來擴展的方向作出估計.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作為n的后繼節(jié)點添入G，并計算f(n-mi)=g(n-mi)+h(mi)；

ADD(mj,OPEN)，

IFf(n-mk)<f(mk)THENf(mk):=f(n-mk)，

IFf(n-ml)<f(ml)THENf(ml):=f(n-ml)，

ADD(ml,OPEN);7.OPEN中的節(jié)點按f值從小到大排序;8.

GOLOOP;算法的說明：A算法由一般的圖搜索算法改變而成.控制策略:

按照f（n）值遞增的順序?qū)PEN中的元素進行排序，f（n）值小的節(jié)點排在前面，大的放在OPEN表的后面.效果:

每次擴展節(jié)點時，優(yōu)先選擇當前f（n）值最小的節(jié)點來擴展.結(jié)論:算法A是一個好的優(yōu)先搜索策略.擴展n后新生成的子節(jié)點m1({mj})、m2({mk})、m3({ml})分別計算其評價函數(shù)值：

f(m1)=g(m1)+h(m1)f(n,m2)=g(n,m2)+h(m2)f(n,m3)=g(n,m3)+h(m3)按第6步比較不同路徑的耗散值并進行相應(yīng)的指針修正.snf(n)m2m3m31m32f(m3)m1f(m1)f(m2)f(m31)f(m32)搜索示意圖八數(shù)碼問題具體事例

：設(shè)評價函數(shù)f（n）形式如下：

f（n）=d（n）+W（n），其中,d（n）代表節(jié)點的深度，即取g（n）=d（n），表示討論單位耗散的情況；而取h（n）=W（n）表示以“不在位”的將牌個數(shù)作為啟發(fā)函數(shù)的度量；

f（n）可估計出通向目標節(jié)點的希望程度.2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目標123456OPEN表：初始化（s（4））（B（4）A（6）C（6））（D（5）E（5）A（6）C（6）F（6））（E（5）A（6）C（6）F（6）G（6）H（7））（I（5）A（6）C（6）F（6）G（6）H（7）J（7））（K（5）A（6）C（6）F（6）G（6）H（7）J（7））（L（5）A（6）C（6）F（6）G（6）H（7）J（7）M（7））第七循環(huán)結(jié)束在第4步成功退出CLOSED表：（）（s（4））（s（4）B（4））（s（4）B（4）D（5））（s（4）B（4）D（5）E（5））（s（4）B（4）D（5）E（5）I（5））（s（4）B（4）D（5）E（5）I（5）K（5））2)爬山法

過程：Hill-climbing1）n：=s；s為初始節(jié)點2）LOOP：IFGOAL（n）THENEXIT（SUCCESS）3）EXPAND（n）→{mi}，計算h（mi），

next_n：=m（minh（mi）的節(jié)點）；4）IFh（n）<h(next_n)THENEXIT(FAIL);5）n:=next_n；6）GOLOOP；顯然如果將山頂作為目標，f（n）=h（n）就表示山頂與當前位置的高度之差，則算法總是力圖登向山頂，在單峰的情況下，必能到達山峰.3)分支限界法

思想：從路徑表中，優(yōu)先擴展當前具有最小耗散值分支路徑的葉節(jié)點n，評價函數(shù)為f（n）=g（n）.過程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}，計算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；6）QUEUE中局部路徑g值最小者排在前面；7）GOLOOP；例：八城市地圖網(wǎng)

最短路徑問題的求解SDBDCEDFEBFABEBFACtg=01g=3A2g=4g=7g=83g=9g=64g=11g=105g=11g=126g=107g=139g=15g=148g=1310g=15g=151112g=14g=1613分支限界法的搜索樹

初始（s（0））1A（3）D（4）2D（4）B（7）D（8）3E（6）

B（7）D（8）A（9）4B（7）D（8）A（9）F（10）B（11）5D（8）A（9）F（10）B（11）C（11）E（12）6A（9）F（10）E（10）

B（11）C（11）E（12）7F（10）E（10）B（11）C（11）E（12）B（13）8E（10）B（11）C（11）E（12）t（13)B（13）9B（11）C（11）E（12）t（13）B（13）F（14）B（15）10C（11）E（12）t（13）B（13）F（14）B（15）A（15)C（15）11E（12）t（13）B（13）F（14）B（15）A（15）C（15）12t（13）B（13）F（14）D（14）B（15）A（15）C（15）F（16）13）結(jié)束.

4)動態(tài)規(guī)劃法

分支限界的缺點：第2循環(huán)擴展A（3）后生成的D（8）節(jié)點（D（4）已在QUEUE上）和第3循環(huán)擴展D（4）之后生成的A（9）節(jié)點（A（3）已在QUEUE上）都是多余的分支。因為由s-D(或s-A)到達目標的路徑顯然要比s-A-D(或s-D-A)到達目標的路徑要好.改進思路：如果能夠刪去類似s-A-D或s-D-A這樣一些多余的路徑，將會大大提高搜索效率.動態(tài)規(guī)劃原理：求s→t的最佳路徑時，對某個中間節(jié)點I，只要考慮s到I中具有最小耗散值這一條局部路徑就可以，其余s到I的路徑是多余的.

具有動態(tài)規(guī)劃原理的分支限界算法過程Dynamic-Programming1）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}，計算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；

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

7）GOLOOP；SAD1g=0g=3g=42BDg=7g=8×3AEg=9g=6×4BFg=11g=10×5ECg=11g=12×6tg=13動態(tài)規(guī)劃原理的搜索樹

785)最佳圖搜索算法A*

在算法A中，當h（n）≤h*（n）時，稱其為A*算法.A*算法具有如下的性質(zhì)：完備性：如果問題有解，則算法一定能找到解.(定理1.1、1.2)可采納性：如果問題有解，則算法一定能找到最佳解。即算法總能找到一條從S到目標節(jié)點的最佳路徑.(定理1.3)最優(yōu)性：設(shè)A1和A2為某問題求解的兩個A*算法，若對所有非目標節(jié)點均有h1（n）〈h2（n）≤h*（n）則算法A1展開的節(jié)點數(shù)目至少和A2一樣多。（啟發(fā)函數(shù)和A*算法的關(guān)系）(定理1.4)5)最佳圖搜索算法A*(續(xù))

通過對這幾條性質(zhì)的證明(定理）可得到幾個有助于理解A*算法的結(jié)論：A*算法結(jié)束前，OPEN表中必存在f（n）≤f*（S）的節(jié)點（n是在最佳路徑上的節(jié)點）(引理1.2)OPEN表上任一具有f（n）≤f*（S）的節(jié)點n，最終都將被A*選作擴展的節(jié)點.(推論1.1)A*選作擴展的任一節(jié)點，有f（n）≤f*（S）.(推論1.2)最優(yōu)性的示例說明:A*中啟發(fā)信息的作用.

例、比較給定各節(jié)點h2（n）值的A*算法與h1（n）≡0的A*算法，所求得最佳路徑時擴展的節(jié)點數(shù)大小

啟發(fā)函數(shù)h（n）的效果比較√f=0√f=4√f=5√f=6√f=7√f=7√f=7√f=7√f=7√f=7√f=7√f=7√f=8√f=8f=9f=9f=10f=9h=7h=5h=4h=2h=3h=3h=3h=3h=3h=1h=2h1（n）≡

0時OPEN和CLOSED表的元素排列如下：S(0)A(4),B(5),C(6)B(5),C(6),D(7),E(7),F(7)C(6),D(7),E(7),F(7),H(7),I(7)D(7),E(7),F(7),H(7),I(7),J(7),K(7)E(7),F(7),H(7),I(7),J(7),K(7),t1(11),t2(11)F(7),H(7),I(7),J(7),K(7),t1(11),t2(11),t3(11)H(7),I(7),J(7),K(7),t1(11),t2(11),t3(11),t4(11)I(7),J(7),K(7),t1(11),t2(11),t3(11),t4(11),t5(11)J(7),K(7),t1(11),t2(11),t3(11),t4(11),t5(11),t6(11)K(7),t7(8),t6(9),t1(11),t2(11),t3(11),t4(11),t5(11)t7(8),t6(9),t8(10),t1(11),t2(11),t3(11),t4(11),t5(11)()S(0)S(0),A(4)S(0),A(4),B(5)S(0),A(4),B(5),C(6)S(0),A(4),B(5),C(6),D(7)S(0),A(4),B(5),C(6),D(7),E(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7),I(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7),I(7),J(7)S(0),A(4),B(5),C(6),D(7),E(7),F(7),H(7),I(7),J(7),K(7)h2（n）不為0時，OPEN和CLOSED表的元素排列如下：S(7)C(8),A(9),B(9)J(8),A(9),B(9),K(9),I(10)t7(8),A(9),B(9),K(9),t6(9),I(10)()S(7)S(7),C(8)S(7),C(8),J(8)存在的問題:如果用擴展節(jié)點數(shù)作為評價搜索效率的準則，那么可以發(fā)現(xiàn)A算法第6步中，對CLOSED表中ml類節(jié)點要重新放回OPEN表中的操作，將引起多次擴展同一節(jié)點的可能.不良結(jié)果:即使問題所包含的節(jié)點數(shù)少，但重復(fù)擴展某些節(jié)點，也將導(dǎo)致搜索效率下降.

A*的不足及其改進:A*算法多次擴展同一節(jié)點的搜索圖例子OPEN表CLOSED表0.s(20)()1.A(12)B(13)C(14)D(15)s(20)2.B(13)C(14)D(15)t(29)s(20)A(12)3.A(11)C(14)D(15)t(29)s(20)B(13)4.C(14)D(15)t(28)s(20)B(13)A(11)

5.A(10)B(11)D(15)t(28)s(20)C(14)6.B(11)D(15)t(27)s(20)C(14)A(10)

7.A(9)D(15)t(27)s(20)C(14)B(11)8.D(15)t(26)s(20)C(14)

B(11)

A(9)9.A(8)B(9)C(10)

t(26)s(20)D(15)10.B(9)C(10)

t(25)s(20)D(15)

A(8)11.A(7)C(10)

t(25)s(20)D(15)B(9)12.C(10)

t(24)s(20)D(15)

B(9)

A(7)13.A(6)B(7)t(24)s(20)D(15)C(10)14.B(7)t(23)15.A(5)t(23)s(20)D(15)

C(10)

A(6)s(20)D(15)

C(10)

B(7)16.t(22)s(20)D(15)C(10)

B(7)

A(5)17.成功結(jié)束

問題:從CLOSED表看出，在修改ml類節(jié)點指針的過程中，節(jié)點A、B、C被重復(fù)擴展，次數(shù)分別為8、4、2，共擴展16次節(jié)點（步）.

原因:在前面的擴展中，并沒有找到從初始節(jié)點到當前節(jié)點的最短路徑.

解決的途徑:(1)對h加以限制:使得第一次擴展一個節(jié)點時，就找到了從s到該節(jié)點的最短路徑.(2)對算法加以改進:避免或減少節(jié)點的多次擴展.定義:一個啟發(fā)函數(shù)，如果對所有節(jié)點ni和nj（nj是ni的子節(jié)點），都有:h(ni)-h(nj)C(ni，nj)(節(jié)點間的估計值實際值）且h(ti)=0

或

h(ni)C(ni，nj)+h(nj)且，

h(ti)=0則稱啟發(fā)函數(shù)h滿足單調(diào)限制條件.

h(ni)ninjh(nj)c(ni,nj)(1)對h加以限制ti定理5若h(n)是單調(diào)的，則A*擴展了節(jié)點n之后，就已經(jīng)找到了到達節(jié)點n的最佳路徑.

即：當A*選n擴展時，有g(shù)(n)=g*(n).定理6若h(n)是單調(diào)的，則由A*所擴展的節(jié)點序列,其f值是非遞減的,即f(ni)≤f(nj)。效果:由于擴展節(jié)點后，即是最佳路徑，因此不必進行指針糾正操作，故改善了A*效率.h單調(diào)的性質(zhì)(2)對算法加以改進改進的理論基礎(chǔ)及應(yīng)用思路：推論1.1OPEN表上任一具有f(n)<f*(s)的節(jié)點定會被擴展.1)按f*(s)值可將OPEN表中的節(jié)點分為兩部分:一部分節(jié)點必須擴展(NEST={n|f(n)<f*(s)}).2)為避免重復(fù)節(jié)點的擴展,需保證h的單調(diào)性,而h≡0是單調(diào)的,故在NEST中可按f(n)=g(n)對節(jié)點進行擴展.推論1.2A*擴展的任一節(jié)點，定有f(n)≤f*(s).

盡管f*(s)未知,但通過近似(在擴展過的節(jié)點中找最大的f(n)→f*(s),找了一個下界)可得到NEST的一個子集.改進思路的圖示OPEN=(…………)f*(s)f<f*(s)的節(jié)點(NEST子集)f>=f*(s)的節(jié)點1)f*(s)?fm：到目前為止已擴展節(jié)點的最大

f值，用fm代替f*(s)2)NEST中的節(jié)點:按f(n)=g(n)進行排序具有修正過程的A*算法：OPEN:=(s)，f(s):=g(s)+h(s)=h(s)，fm:=0;LOOP：IFOPEN=（）THENEXIT（FAIL）；NEST：={ni|f（ni）＜fm}；*NEST給出了OPEN表中滿足f＜fm的節(jié)點集合。fm為處理過的節(jié)點中最大的f值*.(劃分OPEN表)

IFNEST≠

（）THENn：=ni（min（gi））ELSEn:=FIRST(OPEN)，fm=f（n）；*NEST不空時，取其中g(shù)(n)的最小者作為當前要擴展的節(jié)點，否則取OPEN的第一個為當前要擴展的節(jié)點*(保證搜索效率)4.~8.同過程A。OPEN表CLOSED表0.s(0+20)()1.A(11+1)B(9+4)C(6+8)D(1+14)s(0+20)2.A(7+1)B(5+4)C(2+8)s(0+20)D(1+14)3.A(5+1)B(3+4)s(0+20)D(1+14)C(2+8)

4.A(4+1)5.t(22+0)fm

成功結(jié)束02020202020s(0+20)D(1+14)C(2+8)B(3+4)

s(0+20)D(1+14)C(2+8)B(3+4)

A(4+1)

★★★★★★226)A*算法應(yīng)用舉例：1.八數(shù)碼問題1）如果定義評價函數(shù)為f(n)=d(n)+w(n)，h(n)=w(n)定義為“不在位”的將牌個數(shù);是否為A*算法？條件的判斷:盡管我們不能確切知道h*(n)，但根據(jù)“不在位”將牌個數(shù)的估計，就能得出至少需要移動w(n)步才能達到目標，顯然有h(n)=w(n)h*(n).28316475S（4）；g=0；h=428316475283147652831647528314765231847652831476528371465832147652318476523184765123847651238476512378465A（6）；g=1；h=5B（4）；g=1；h=3C（6）；g=1；h=5D（5）；g=2；h=3E（5）；g=2；h=3F（6）；g=2；h=4G（6）；g=3；h=3H（7）；g=3；h=4I（5）；g=3；h=2J（7）；g=3；h=4K（5）；g=4；h=1L（5）；g=5；h=0M（7）；g=5；h=22）定義f(n)=d(n)+p(n)，p(n)定義為每個將牌與其目標位置之間最短距離的總和.條件判斷:同樣,由于至少需要p(n)步才能達到目標，因此，也滿足h(n)h*(n).下圖給出了h(n)=p(n)的搜索圖，并標出了相應(yīng)的啟發(fā)函數(shù)值。由解路可給出g*（n）和h*（n）的值，在最佳路徑上的節(jié)點有f*=g*+h*=5.28316475S（5）；W=4；p=52831647528314765283164752831476523184765283147652318476523184765123847651238476512378465A（7）；w=5；p=6B（5）；w=3；p=4C（7）；w=5；p=6D（7）；w=3；p=5E（5）；w=3；p=3F（7）；w=4；p=5G（5）；w=2；p=2H（7）；w=4；p=4I（5）；w=1；p=1J（5）；w=0；p=0K（7）；w=2；p=2

對比小結(jié):

上表為應(yīng)用不同啟發(fā)函數(shù)，求最佳解時的情況.實驗現(xiàn)象:函數(shù)p（n）的搜索效果最好,w（n）次之,h(n)=0最差.結(jié)論:啟發(fā)式函數(shù)選取的好壞，直接影響搜索效果.2.M-C問題

（missionaryandcannibal）問題:有N個傳教士和N個野人來到河邊準備渡河，河岸有一條船，每次至多可供k人乘渡，問傳教士為了安全起見，應(yīng)如何規(guī)劃擺渡方案，使得任何時刻，河兩岸以及船上的野人數(shù)目總是不超過傳教士數(shù)目（當傳教士和野人共存時）.約束條件:在傳教士和野人從左岸全部擺渡到右岸的過程中，1)在共存的任何時候均滿足M≥C，2)在擺渡過程中,M+C≤k.設(shè)N=5，k=3，則該問題可用上圖表示，圖中L和R表示左岸和右岸，B=1或0分別表示有船或無船。約束條件是：兩岸或船上M≥C，且船的容量M+C≤3。綜合數(shù)據(jù)庫：用三元組表示，即（ML，CL，BL），其中，0≤ML，CL≤5，BL=0or1，問題被簡化為（5，5，1）→（0，0，0）規(guī)則集合：由兩種擺渡操作組成：Pmc（從左岸到右岸）和qmc（從右岸到左岸），每次擺渡操作，船上合理人數(shù)的組合數(shù)乘以2，就是規(guī)則數(shù).形式如：

if（ML，CL，BL=1）then（ML-1，CL，BL-1）；（P10）

if（ML，CL，BL=1）then（ML，CL-1，BL-1）；（P01）

if（ML，CL，BL=1）then（ML-1，CL-1，BL-1）；（P11）

if（ML，CL，BL=1）then（ML-2，CL，BL-1）；（P20）

…

…

（P30，P21，P02，P03）

if（ML，CL，BL=0）then（ML+1，CL，BL+1）；（q10）

if（ML，CL，BL=0）then（ML，CL+1，BL+1）；（q01）

if（ML，CL，BL=0）then（ML+1，CL+1，BL+1）；（q11）

if（ML，CL，BL=0）then（ML+2，CL，BL+1）；（q20）

…

…（q30，q21，q02，q03）控制策略：建立系統(tǒng)描述后，就要確定規(guī)則選取策略，以完成對狀態(tài)空間的搜索，求得一個擺渡操作序列。思路:利用M和C的線性組合，以及有船與否來作為啟發(fā)函數(shù)的基本分量。方法:1)h（n）=0;2)h（n）=M+C;3)h（n）=M+C-2B.圖3-21給出了三種啟發(fā)函數(shù)的搜索圖（假定為單位耗散）,下表為各自的搜索情況.h（n）=0的搜索圖即為該問題的狀態(tài)空間圖；h（n）=M+C不滿足h（n）≤h*（n）；h（n）=M+C-2B可滿足