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

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

回溯策略

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

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

一、回溯算法BACKTRACK

算法中用到的部分變量、常量、謂詞、函數(shù)：變量：DATA，RDATA：狀態(tài)變量RULES,PATH：表變量常量：NIL:空表----LISP語言中的常量，也可用（）謂詞：TERM(DATA):DATA滿足結束條件時，為真DEADEND(DATA):DATA不在解路上，為真（往下到達目標的可能性來定義這個謂詞：若從DATA當前狀態(tài)往下走到達目標的可能性很小時，則放棄這個狀態(tài)）NULL(X):表X為空表時，為真函數(shù)：APPRULES(DATA):將DATA所有可用規(guī)則進行排序所得到的表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é)點）

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

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

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

修改后的APPRULES(RULES):ifdiag（i，j）＜diag（i，k）,thenRij排在Rik前．ifdiag（i，j）=diag（i，k），then與以前相同Rij排在Pik之前j<k1/15/20238課堂練習：請用回溯搜索策略BACKTRACK求解四皇后問題，要求規(guī)則排序使用對角函數(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)的最長對角線的長度．1/15/20239三、BACKTRACK算法的修改與補充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一、相關概念有向圖：G=(P,A)，P:點集A:弧集弧:兩點間有方向的線。如果有一條弧從節(jié)點ni出發(fā)指向nj；則節(jié)點nj稱為節(jié)點ni的子節(jié)點，節(jié)點ni稱為節(jié)點nj的父親節(jié)點．對于產(chǎn)生式系統(tǒng)，節(jié)點：用狀態(tài)描述標記?。河靡?guī)則標記假定圖中的每一個節(jié)點只有有限個子節(jié)點。

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

1)

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

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

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

最佳解路徑：費用最小的解路徑。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明：設n是OPEN表中的任的一節(jié)點，d*(n)是隱含圖中從s到n的最短路徑的長度，e是圖中每條弧的最小費用。于是有g*(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é)點的d*值會不斷增大，因此f值也會不斷增大。

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

證明：設P：n0,n1,……,nk是一條最佳解路徑，其中，nk是目標點，n0=s.在A*結束之前，從左向右掃描序列P，n’是P中第一個在OPEN表中的節(jié)點(這樣的n’是存在的：因為開始n0在OPEN上，算法結束前，若擴展ni，則ni+1在OPEN上，此時不可能擴展到nk)。由A*的定義，有f(n’)=g(n’)+h(n’)A*算法的可采納性1/15/202333因為n’處在通往目標的最佳解路徑上，設(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’)而對最佳路上任意一點n，有：f*(n’)=f*(s)因此，f(n’)≤f*(s)證畢。A*算法的可采納性……定理2

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

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

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

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

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

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

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

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

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

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

1/15/202348由已知h(n)滿足單調限制，對任意i=0,…,k-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)單調限制的性質……定理7

1/15/202349因為t≤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的假設）單調限制的性質……定理7

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

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

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

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

f(n1)單調限制的性質……定理8

1/15/202353A*算法的總結與討論1.

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

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

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