人工智能課件-啟發(fā)式搜索問題-3

啟發(fā)式搜索算法前面我們講解了無信息搜索算法通過系統(tǒng)化地生成新狀態(tài)并且檢驗(yàn)它們是否為目標(biāo)狀態(tài)來尋找問題的解。但不幸的是，一般來說，問題的規(guī)模（問題所有可能出現(xiàn)的狀態(tài)數(shù)）是比較大的，就拿8數(shù)碼問題這樣一個并不太復(fù)雜的問題來說，其規(guī)模就達(dá)到9！/2＝181440個狀態(tài)。當(dāng)問題有解時，如何縮小查找范圍，快速有效地找到問題的解，甚至是問題的最優(yōu)解，正是搜索所要討論的問題。多數(shù)情況下前面描述的那些算法無效。從現(xiàn)在開始我們將向大家展示有信息的搜索策略----利用問題的特定知識能夠有效地找到解。

有信息搜索算法

啟發(fā)式搜索算法A最佳優(yōu)先搜索算法貪婪最佳優(yōu)先搜索算法A*算法局部搜索算法爬山法模擬退火算法局部定向算法遺傳算法啟發(fā)式搜索算法啟發(fā)式信息在問題求解中的應(yīng)用最早出現(xiàn)在1958年西蒙和紐厄爾的一篇早期論文中，但是短語“啟發(fā)式搜索”和估計(jì)到目標(biāo)距離的啟發(fā)函數(shù)出現(xiàn)的比較晚（紐厄爾和Ernst,1965;Lin,1965).隨后，1966年Doran和Miche對啟發(fā)式搜索應(yīng)用于許多問題進(jìn)行了廣泛的研究，尤其是對八數(shù)碼和十五數(shù)碼游戲。雖然Doran和Miche完成了在啟發(fā)式搜索中路徑長度和“外顯率”（路徑長度和已經(jīng)訪問過的節(jié)點(diǎn)總數(shù)的比率）的理論分析，但他們忽略了當(dāng)前路徑長度提供的信息；Hart，尼爾森和Raphael于1968年提出了A*算法，將當(dāng)前路徑長度與啟發(fā)式搜索相結(jié)合，后來Hart等人于1972年又做了一些修正；以后人們陸續(xù)對算法進(jìn)行改進(jìn)；1985年Dechter和Pearl論證了A*算法的最優(yōu)效率。迄今為止關(guān)于啟發(fā)式和啟發(fā)式搜索算法的最前面資料是Pearl于1984撰寫的教材《啟發(fā)式》，感興趣的同學(xué)可以參閱。搜索算法的最新結(jié)果通常出現(xiàn)在《人工智能》上。啟發(fā)式搜索是利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。這種利用啟發(fā)信息的搜索過程都稱為啟發(fā)式搜索方法。在研究啟發(fā)式搜索方法時，先說明一下啟發(fā)信息應(yīng)用，啟發(fā)能力度量及如何獲得啟發(fā)信息這幾個問題，然后再來討論算法及一些理論問題。

一般來說:啟發(fā)信息強(qiáng)，可以降低搜索的工作量，但可能導(dǎo)致找不到最優(yōu)解；啟發(fā)信息弱，一般會導(dǎo)致搜索的工作量加大，極端情況下演變?yōu)槊つ克阉鳎锌赡苷业阶顑?yōu)解。

我們希望，通過引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。啟發(fā)式搜索算法A這是一個重要而又困難的問題，從理論上要研究啟發(fā)信息和最佳路徑的關(guān)系，從實(shí)際上則要解決獲取啟發(fā)信息方法的問題。比較不同搜索方法的效果可用啟發(fā)能力的強(qiáng)弱來度量。在大多數(shù)實(shí)際問題中，人們感興趣的是使路徑的耗散值和求得路徑所需搜索的耗散值兩者的某種組合最小，更一般的情況是考慮搜索方法對求解所有可能遇見的問題，其平均的組合耗散值最小。如果搜索方法1的平均組合耗散值比方法2的平均組合耗散值低，則認(rèn)為方法1比方法2有更強(qiáng)的啟發(fā)能力。實(shí)際上很難給出一個計(jì)算平均組合耗散值的方法，因此啟發(fā)能力的度量也只能根據(jù)使用方法的實(shí)際經(jīng)驗(yàn)作出判斷，沒有必要去追求嚴(yán)格的比較結(jié)果。

啟發(fā)式搜索過程中，要對OPEN表進(jìn)行排序，這就需要有一種方法來計(jì)算待擴(kuò)展節(jié)點(diǎn)有希望通向目標(biāo)節(jié)點(diǎn)的不同程度，我們總是希望能找到最有希望通向目標(biāo)節(jié)點(diǎn)的待擴(kuò)展節(jié)點(diǎn)優(yōu)先擴(kuò)展。一種最常用的方法是定義一個評價函數(shù)f（Evaluationfunction）對各個子節(jié)點(diǎn)進(jìn)行計(jì)算，其目的就是用來估算出"有希望"的節(jié)點(diǎn)來。如何定義一個評價函數(shù)呢？通?？梢詤⒖嫉脑瓌t有：一個節(jié)點(diǎn)處在最佳路徑上的概率；求出任意一個節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)集之間的距離度量或差異度量；根據(jù)格局（博弈問題）或狀態(tài)的特點(diǎn)來打分。即根據(jù)問題的啟發(fā)信息，從概率角度、差異角度或記分法給出計(jì)算評價函數(shù)的方法。

啟發(fā)式搜索算法A，一般簡稱為A算法，是一種典型的啟發(fā)式搜索算法。思想：定義一個評價函數(shù)f，對當(dāng)前的搜索狀態(tài)進(jìn)行評估，找出一個最有希望的節(jié)點(diǎn)來擴(kuò)展。評價函數(shù)：f（n）＝g（n）＋h（n）

其中n是被評價的節(jié)點(diǎn)。

f（n）、g（n）和h（n）各自表述什么含義呢？我們先來定義下面幾個函數(shù)的含義，它們與f（n）、g（n）和h（n）的差別是都帶有一個"*"號。

g*(n)：表示從初始節(jié)點(diǎn)s到節(jié)點(diǎn)n的最短路徑的耗散值；

h*(n)：表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的最短路徑的耗散值；

f*(n)=g*(n)+h*(n)：表示從初始節(jié)點(diǎn)s經(jīng)過節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的最短路徑的耗散值。

而f（n）、g（n）和h（n）則分別表示是對f*（n）、g*（n）和h*（n）三個函數(shù)值的的估計(jì)值。是一種預(yù)測。A算法就是利用這種預(yù)測，來達(dá)到有效搜索的目的的。它每次按照f(n)值的大小對OPEN表中的元素進(jìn)行排序，f值小的節(jié)點(diǎn)放在前面，而f值大的節(jié)點(diǎn)則被放在OPEN表的后面，這樣每次擴(kuò)展節(jié)點(diǎn)時，都是選擇當(dāng)前f值最小的節(jié)點(diǎn)來優(yōu)先擴(kuò)展。

利用評價函數(shù)f（n）＝g（n）＋h（n）來排列OPEN表節(jié)點(diǎn)順序的搜索算法稱為算法A。

過程A①OPEN:＝（s），f（s）:＝g（s）+h（s）;

②LOOP：IFOPEN＝（

）THENEXIT（FAIL）；

③n:＝FIRST（OPEN）；

④IFGOAL（n）THENEXIT（SUCCESS）；

⑤REMOVE（n，OPEN），ADD（n，CLOSED）；

⑥EXPAND（n）→{mi}，計(jì)算f（n，mi）＝g（n，mi）+h（mi）；g（n，mi）是從s通過n到mi的耗散值，f（n，mi）是從s通過n、mi到目標(biāo)節(jié)點(diǎn)耗散值的估計(jì)。·ADD（mj，OPEN），標(biāo)記mj到n的指針?！Ff（n，mk）<f（mk）THENf（mk）:＝f（n，mk），標(biāo)記mk到n的指針；比較f（n，mk）和f（mk），f（mk）是擴(kuò)展n之前計(jì)算的耗散值。

·IFf（n，ml）<f（ml）THENf（m1）:＝f（n，m1），標(biāo)記ml到n的指針，ADD（ml，OPEN）；當(dāng)f（n，ml）<f（ml）時，把ml重放回OPEN中，不必考慮修改到其子節(jié)點(diǎn)的指針。

⑦OPEN中的節(jié)點(diǎn)按f值從小到大排序；

⑧GOLOOP。A算法同樣由一般的圖搜索算法改變而成。在算法的第7步，按照f值從小到大對OPEN表中的節(jié)點(diǎn)進(jìn)行排序，體現(xiàn)了A算法的含義。

算法要計(jì)算f(n)、g(n)和h(n)的值，g(n)根據(jù)已經(jīng)搜索的結(jié)果，按照從初始節(jié)點(diǎn)s到節(jié)點(diǎn)n的路徑，計(jì)算這條路徑的耗散值就可以了。而h(n)是與問題有關(guān)的，需要根據(jù)具體的問題來定義。有了g(n)和h(n)的值，將他們加起來就得到f(n)的值了。請大家注意A算法的結(jié)束條件：當(dāng)從OPEN中取出第一節(jié)點(diǎn)時，如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則算法成功結(jié)束。而不是在擴(kuò)展一個節(jié)點(diǎn)時，只要目標(biāo)節(jié)點(diǎn)一出現(xiàn)就立即結(jié)束。我們在后面將會看到，正是由于有了這樣的結(jié)束判斷條件，才使得A算法有很好的性質(zhì)。

算法中f（n）規(guī)定為對從初始節(jié)點(diǎn)s出發(fā)，約束通過節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)t，最小耗散值路徑的耗散值f*(n)的估計(jì)值，通常取正值。f（n）由兩個分量組成，其中g(shù)（n）是到目前為止，從s到n的一條最小耗散值路徑的耗散值，是作為從s到n最小耗散值路徑的耗散值g*(n)的估計(jì)值，h（n）是從n到目標(biāo)節(jié)點(diǎn)t，最小耗散值路徑的耗散值h*(n)的估計(jì)值。

設(shè)函數(shù)k（ni，nj）表示最小耗散路徑的實(shí)際耗散值（當(dāng)ni到nj無通路時則k（ni，nj）無意義），則g*（n）＝k（s，n），h*（n）＝mink（n，ti），其中ti是目標(biāo)節(jié)點(diǎn)集，k（n，ti）就是從n到每一個目標(biāo)節(jié)點(diǎn)最小耗散值路徑的耗散值，h*（n）是其中最小值的那條路徑的耗散值，而具有h*（n）值的路徑是n到ti的最佳路徑。由此可得f*（n）＝g*（n）＋h*（n）就表示s→ti并約束通過節(jié)點(diǎn)n的最佳路徑的耗散值。

當(dāng)n＝s時，f*（s）=h*（s）則表示s→ti無約束的最佳路徑的耗散值，這樣一來，所定義的f（n）=g（n）+h（n）就是對f*(n)的一個估計(jì)。g（n）的值實(shí)際上很容易從到目前為止的搜索樹上計(jì)算出來，不必專門定義計(jì)算公式，也就是根據(jù)搜索歷史情況對g*(n)作出估計(jì)，顯然有g(shù)(n)≥g*(n)。h(n)則依賴于啟發(fā)信息，通常稱為啟發(fā)函數(shù)，是要對未來擴(kuò)展的方向作出估計(jì)。算法A是按f(n)遞增的順序來排列OPEN表的節(jié)點(diǎn)，因而優(yōu)先擴(kuò)展f（n）值小的節(jié)點(diǎn)，體現(xiàn)了好的優(yōu)先搜索思想，所以算法A是一個好的優(yōu)先的搜索策略。

下面再以八數(shù)碼問題為例說明好的優(yōu)先搜索策略的應(yīng)用過程。設(shè)評價函數(shù)f(n)形式如下：

f(n)=d(n)+W(n)

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

算法執(zhí)行OPEN表CLOSED表初始化(s(4))()第1輪循環(huán)結(jié)束(B(4)A(6)C(6))(s(4))第2輪循環(huán)結(jié)束(D(5)E(5)A(6)C(6)F(6))(s(4)B(4))第3輪循環(huán)結(jié)束(E(5)A(6)C(6)F(6)G(6)H(7))(s(4)B(4)

D(5))第4輪循環(huán)結(jié)束(I(5)A(6)C(6)F(6)G(6)H(7)J(7))(s(4)B(4)

D(5)E(5))第5輪循環(huán)結(jié)束(K(5)A(6)C(6)F(6)G(6)H(7)J(7))(s(4)B(4)

D(5)E(5)

I(5))第6輪循環(huán)結(jié)束(L(5)A(6)C(6)F(6)G(6)H(7)J(7)M(7))(s(4)B(4)

D(5)E(5)

I(5)K(5))第7輪循環(huán)結(jié)束第4步成功退出根據(jù)目標(biāo)節(jié)點(diǎn)L返回到s的指針，可得解路徑S(4)，B(5)，E(5)，I(5)，K(5)，L(5)下圖給出的是使用A算法求解8數(shù)碼問題的搜索圖。其中A、B、C等符號，只是為了標(biāo)記節(jié)點(diǎn)的名稱，沒有特殊意義。這些符號旁邊括弧中的數(shù)字是該節(jié)點(diǎn)的評價函數(shù)值f。而圓圈中的值，則表示節(jié)點(diǎn)的擴(kuò)展順序。從圖中可以看出，在第二步選擇節(jié)點(diǎn)B擴(kuò)展之后，OPEN表中f值最小的節(jié)點(diǎn)有D和E兩個節(jié)點(diǎn)，他們的f值都是5。在出現(xiàn)相同的f值時，A算法并沒有規(guī)定首先擴(kuò)展哪個節(jié)點(diǎn)，可以任意選擇其中的一個節(jié)點(diǎn)首先擴(kuò)展。返回使用啟發(fā)函數(shù)的八數(shù)碼游戲的搜索樹根據(jù)目標(biāo)節(jié)點(diǎn)L返回到s的指針，可得解路徑S(4)，B(5)，E(5)，I(5)，K(5)，L(5)。上圖給出的是使用A算法求解8數(shù)碼問題的搜索圖。其中A、B、C等符號，只是為了標(biāo)記節(jié)點(diǎn)的名稱，沒有特殊意義。這些符號旁邊括弧中的數(shù)字是該節(jié)點(diǎn)的評價函數(shù)值f。而圓圈中的值，則表示節(jié)點(diǎn)的擴(kuò)展順序。從圖中可以看出，在第二步選擇節(jié)點(diǎn)B擴(kuò)展之后，OPEN表中f值最小的節(jié)點(diǎn)有D和E兩個節(jié)點(diǎn)，他們的f值都是5。在出現(xiàn)相同的f值時，A算法并沒有規(guī)定首先擴(kuò)展哪個節(jié)點(diǎn)，可以任意選擇其中的一個節(jié)點(diǎn)首先擴(kuò)展。

思想:對每一個節(jié)點(diǎn)使用評估函數(shù)f(n)“最有希望”的（節(jié)點(diǎn)）評估擴(kuò)展最有希望的未擴(kuò)展節(jié)點(diǎn)執(zhí)行:

按照最有希望的降序排列邊緣中的節(jié)點(diǎn)特例:貪婪最佳優(yōu)先搜索A*

搜索最佳優(yōu)先搜索對羅馬尼亞城市圖中可以通過從Arad到Bucharest的直線距離來估計(jì)從Arad到Bucharest的最低耗散路徑的耗散值（使用按公里計(jì)算的步驟成本評估）評估函數(shù)f(n)=h(n)(heuristic)=從n

到目標(biāo)goal的成本評估例如,hSLD(n)=從n到

Bucharest的直線距離貪婪最佳優(yōu)先搜索擴(kuò)展似乎離目標(biāo)goal最近的節(jié)點(diǎn)。即只使用啟發(fā)函數(shù)h(n)來評價節(jié)點(diǎn)。貪婪最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索案例貪婪最佳優(yōu)先搜索案例貪婪最佳優(yōu)先搜索案例貪婪最佳優(yōu)先搜索案例貪婪最佳優(yōu)先搜索算法性能完備性?否–在循環(huán)中會陷入困境，例如

Iasi

Neamt

Iasi

Neamt

時間復(fù)雜性?

O(bm),但一個好的啟發(fā)函數(shù)heuristic能夠極大改善算法性能空間復(fù)雜性?

O(bm)–在內(nèi)存中要保存所有節(jié)點(diǎn)最優(yōu)性?否A*搜索當(dāng)在算法A的評估函數(shù)中，使用的啟發(fā)函數(shù)h(n)是處在h*(n)的下界范圍，即滿足h(n)≤h*(n)時，則把這個算法稱為算法A*（OptimalSearch）。當(dāng)問題有解時，A*算法一定能夠找到一條到達(dá)目標(biāo)節(jié)點(diǎn)的最佳路徑實(shí)際上。此時若gd，則算法等同于廣度優(yōu)先算法。A*算法，具有一些很好的性質(zhì)，比如可采納性等。

一般地說對任意一個圖，當(dāng)s到目標(biāo)節(jié)點(diǎn)有一條路徑存在時，如果搜索算法總是在找到一條從s到目標(biāo)節(jié)點(diǎn)的最佳路徑上結(jié)束，則稱該搜索算法是可采納的（Admissibility）。A﹡就具有可采納性。對于以下的定理、引理和推論，我們只要求掌握其結(jié)論和含義，不要求掌握其具體的證明過程。但是證明過程有助于你對算法的理解。以下定理的證明，正文部分是嚴(yán)格的，而解釋部分，則不是嚴(yán)格的證明，只是從直觀上，或者從思路上進(jìn)行說明。

在以下的定理證明過程中，要明確這樣幾個關(guān)系：

f*(s)=f*(t)=h*(s)，其中s是初始節(jié)點(diǎn)，t是目標(biāo)節(jié)點(diǎn)（有時也用g表示）。當(dāng)n是從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)t的最優(yōu)路徑上的節(jié)點(diǎn)時，f*(n)=f*(s)=f*(t)=h*(s)。下面來證明A﹡的可采納性及若干重要性質(zhì)。定理1：對有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。定理1的結(jié)論是顯然的。由于問題的狀態(tài)是有限的，那么A算法至少可以在有限的步數(shù)內(nèi)搜索完所有的可以從初始節(jié)點(diǎn)到達(dá)的節(jié)點(diǎn)，只要問題是有解的，則一定可以找到問題的解。

證明：設(shè)A搜索失敗，則算法在第2步結(jié)束，OPEN表變空，而CLOSED表中的節(jié)點(diǎn)是在結(jié)束之前被擴(kuò)展過的節(jié)點(diǎn)。由于圖有解，令（n0=s，n1，n2，…，nk=t）表示某一解路徑，我們從nk開始逆向逐個檢查該序列的節(jié)點(diǎn)，找到出現(xiàn)在CLOSED表中的節(jié)點(diǎn)ni，即ni

CLOSED，ni+1

CLOSED（ni一定能找到，因?yàn)閚0

CLOSED，nk

CLOSED）。由于ni在CLOSED中，必定在第6步被擴(kuò)展，且ni+1被加到OPEN中，因此在OPEN表空之前，ni+1已被處理過。若ni+1是目標(biāo)節(jié)點(diǎn)，則搜索成功，否則它被加入到CLOSED中，這兩種情況都與搜索失敗的假設(shè)矛盾，因此對有限圖不失敗則成功。[證畢]因?yàn)锳﹡是A的特例，因此它具有A的所有性質(zhì)。這樣對有限圖如果有解，則A﹡一定能在找到到達(dá)目標(biāo)的路徑結(jié)束，下面要證明即使是無限圖，A﹡也能找到最佳解結(jié)束。我們先證兩個引理：引理2.1：對無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)點(diǎn)t的一條路徑，則A﹡不結(jié)束時，在OPEN中即使最小的一個f值也將增到任意大，或有f(n)>f﹡(s)。在如下的證明中，隱含了兩個假設(shè)：（1）任何兩個節(jié)點(diǎn)之間的耗散值都大于某個給定的大于零的常量；（2）h(n)對于任何n來說，都大于等于零。

引理2.1的證明也比較好理解。由于當(dāng)問題有解存在時，從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑的耗散值總是一個有限的常量。那么在該解路徑上的任何一個節(jié)點(diǎn)n，由于f(n)=g(n)+h(n)，而g(n)是有限的，h(n)≤h*(n)也是有限的（因?yàn)閔*(n)有限），所以f(n)也是有限的。而對于一個無限圖來說，那些不在解路徑上的無限路徑，隨著搜索的進(jìn)行，其耗散值總會趨于無窮大，因此那些在解路徑上的節(jié)點(diǎn)的f值總會變得最小，總會有機(jī)會被排在OPEN表的第一個位置，從而被A*擴(kuò)展。而目標(biāo)節(jié)點(diǎn)也是解路徑上的一個節(jié)點(diǎn)，這樣它同樣會有機(jī)會被排在OPEN表的第一個位置，從而使得算法成功結(jié)束，找到問題的解路徑。證明：設(shè)d﹡(n)是A﹡生成的搜索樹中，從s到任一節(jié)點(diǎn)n最短路徑長度的值（設(shè)每個弧的長度均為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（設(shè)h(n)≥0）若A﹡不結(jié)束，d﹡(n)趨向于

，f值將增到任意大。

設(shè)M=f*(s)/e

，M是一個定數(shù)，所以搜索進(jìn)行到一定程度會有d﹡(n)>M，或d*(n)/M>1

，則

f(n)d*(n)e=d*(n)f*(s)/M=f*(s)d*(n)/M>f*(s)。

[證畢]該引理可以這樣來理解：如果問題從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)g的路徑存在時，則一定有一個最短路徑存在。在A*沒有結(jié)束之前，OPEN表中的節(jié)點(diǎn)不會為空。由于總是從OPEN表中取出節(jié)點(diǎn)來擴(kuò)展，所以最優(yōu)路徑肯定要通過OPEN表中的某個節(jié)點(diǎn)，設(shè)該節(jié)點(diǎn)為n。那么n有兩個特點(diǎn)，一是n是從s到g的最優(yōu)路徑上的節(jié)點(diǎn)，二是到目前為止已經(jīng)找到了從s到n的最優(yōu)路徑。第一點(diǎn)會比較容易接受，第二點(diǎn)是如何保證的呢？如果到目前為止找到的不是從s到n的最優(yōu)路徑，同樣的理由，在OPEN表中一定有一個節(jié)點(diǎn)--假定為n'--在從s到n的最優(yōu)路徑上，當(dāng)然他也一定在從s到g的最優(yōu)路徑上。用n'來代替n，重復(fù)下去，一直找到滿足以上兩個特點(diǎn)的n為止。當(dāng)然，我們不一定明確的知道到底OPEN表中的哪個節(jié)點(diǎn)滿足這樣的特點(diǎn)，但從以上的敘述可以知道，這樣的節(jié)點(diǎn)一定存在。這一點(diǎn)就足夠了。

對于具有這樣特點(diǎn)的n，由于以上所說的第一個特點(diǎn)有g(shù)(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)路徑上的節(jié)點(diǎn)n1和n2，都有f*(n1)=f*(n2)，而n和s都是最優(yōu)路徑上的節(jié)點(diǎn)。引理2.2得證。引理2.2：A*結(jié)束前，OPEN表中必存在f(n)≤f﹡(s)的節(jié)點(diǎn)（n是在最佳路徑上的節(jié)點(diǎn)）。

證明：設(shè)從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的一條最佳路徑序列為：

(n0=s，n1，…，nk=t),算法初始化時，s在OPEN中，由于A﹡沒有結(jié)束，在OPEN中存在最佳路徑上的節(jié)點(diǎn)。設(shè)OPEN表中的某節(jié)點(diǎn)n是處在最佳路徑序列中（至少有一個這樣的節(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)。[證畢]定理2：對無限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*也一定成功結(jié)束。有了以上兩個引理，定理2的證明就簡單了。值得說明的是，對于無限圖來說，當(dāng)問題有解時，從理論上來說，只有A*算法才能保證一定能找到問題的解，而A算法則不能保證。但是在實(shí)際應(yīng)用中，一般來說，A算法也總能找到解，除非你故意設(shè)計(jì)一個找不到解的f函數(shù)。證明：假定A*不結(jié)束，由引理2.1有f(n)＞f*(s)，或OPEN表中最小的一個f值也變成無界，這與引理2.2的結(jié)論矛盾，所以A*只能成功結(jié)束。[證畢]由于A*算法每次選擇f值最小的節(jié)點(diǎn)優(yōu)先擴(kuò)展，由定理2得知，只要問題有解，則A*算法總能找到一個解，這個解的耗散值要大于等于f*(s)（f*(s)是最優(yōu)路徑的耗散值），所以O(shè)PEN表中滿足條件f(n)＜f*(s)的任何節(jié)點(diǎn)n，肯定會在A*結(jié)束前被擴(kuò)展。推論2.1：OPEN表上任一具有f(n)＜f*(s)的節(jié)點(diǎn)n，最終都將被A*選作為擴(kuò)展的節(jié)點(diǎn)。定理3指出，當(dāng)問題有解時，A*算法不但一定能找到解，而且一定能找到最優(yōu)解，這一點(diǎn)稱為可采納性。定理3：若存在初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*必能找到最佳解結(jié)束。

其實(shí)從對引理2.2的證明注釋已經(jīng)清楚，在A*算法結(jié)束之前，在OPEN表中一定存在一個節(jié)點(diǎn)n，該節(jié)點(diǎn)在最優(yōu)路徑上，同時也找到了從s到n的最優(yōu)路徑。如果A*找到的不是最優(yōu)路徑的話，設(shè)其找到的路徑的耗散值為f(g)，由于f(n)≤f*(n)<f(g)，所以，這時在OPEN表中，應(yīng)該至少是n排在目標(biāo)g的前面，而按照A*算法，只有當(dāng)目標(biāo)節(jié)點(diǎn)排在OPEN表的第一位時，算法才結(jié)束，所以在A*結(jié)束時，找到的只能是最優(yōu)路徑。從這里也可以看出，在前面反復(fù)強(qiáng)調(diào)過的A算法（A*算法）的結(jié)束判斷條件，必須是當(dāng)目標(biāo)節(jié)點(diǎn)的f值在OPEN表中最小時才能結(jié)束，而不是目標(biāo)一出現(xiàn)就結(jié)束是多么的重要。只有這樣，才能保證A*算法的可采納性。證明：（1）由定理1、2知A*一定會找到一個目標(biāo)節(jié)點(diǎn)結(jié)束。

（2）設(shè)找到一個目標(biāo)節(jié)點(diǎn)t結(jié)束，而s到t不是一條最佳路徑，即：

f(t)=g(t)>f*(s)

而根據(jù)引理2.2知結(jié)束前OPEN表上有節(jié)點(diǎn)n，且處在最佳路徑上，并有f(n)≤f*(s)，所以

f(n)≤f*(s)<f(t)

這時算法A*應(yīng)選n作為當(dāng)前節(jié)點(diǎn)擴(kuò)展，不可能選t，從而也不會去測試目標(biāo)節(jié)點(diǎn)t，即這與假定A*選t結(jié)束矛盾，所以A*只能結(jié)束在最佳路徑上。[證畢]推論3.1：A*選作擴(kuò)展的任一節(jié)點(diǎn)n，有f(n)≤f*(s)。該推論可以直接從引理2.2推出。由引理2.2，在A*結(jié)束前，OPEN表中必有滿足條件f(n)≤f*(s)的節(jié)點(diǎn)存在，因此，A*必然從這些節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)擴(kuò)展，而不可能去選擇f(n)>f*(s)的節(jié)點(diǎn)擴(kuò)展，所以A*選作擴(kuò)展的任一節(jié)點(diǎn)n，必有f(n)≤f*(s)。證明：令n是由A*選作擴(kuò)展的任一節(jié)點(diǎn)，因此n不會是目標(biāo)節(jié)點(diǎn)，且搜索沒有結(jié)束，由引理2.2而知在OPEN中有滿足f(n)f*(s)的節(jié)點(diǎn)

。若n=s，則f(n)≤f*(s)，否則選n擴(kuò)展，必有f(n)<f*(s)

，所以f(n)≤f*(s)成立。[證畢]啟發(fā)函數(shù)與A*算法的關(guān)系

應(yīng)用A*的過程中，如果選作擴(kuò)展的節(jié)點(diǎn)n，其評價函數(shù)值f(n)=f*(n)，則不會去擴(kuò)展多余的節(jié)點(diǎn)就可找到解?？梢韵胂蟮絝(n)越接近于f*(n)，擴(kuò)展的節(jié)點(diǎn)數(shù)就會越少，即啟發(fā)函數(shù)中，應(yīng)用的啟發(fā)信息（問題知識）愈多，擴(kuò)展的節(jié)點(diǎn)數(shù)就越少。定理4：有兩個A*算法A1和A2，若A2比A1有較多的啟發(fā)信息（即對所有非目標(biāo)節(jié)點(diǎn)均有h2(n)>h1(n)），則在具有一條從s到t的隱含圖上，搜索結(jié)束時，由A2所擴(kuò)展的每一個節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點(diǎn)至少和A2一樣多。

在定理4中所說的"有兩個A*算法A1和A2"，指的是對于同一個問題，分別定義了兩個啟發(fā)函數(shù)h1和h2。這里要強(qiáng)調(diào)幾點(diǎn)：首先，這里的A1和A2都是A*的，也就是說定義的h1和h2都要滿足A*算法的條件。第二，只有當(dāng)對于任何一個節(jié)點(diǎn)n，都有h2(n)>h1(n)時，定理才能保證用A2搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)≤用A1搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)。而如果僅是h2(n)≥h1(n)時（比定理的條件多了一個"等于"，而不只是單純的"大于"），定理并不能保證用A2搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)≤用A1搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)。也就是說，如果僅是h2(n)≥h1(n)，有等于的情況出現(xiàn)，可能會有用A2搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)反而多于用A1搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)的情況。這種情況一般只會在有多個節(jié)點(diǎn)的f值相等時，才可能出現(xiàn)，這是由于A算法對于具有相等的f值的節(jié)點(diǎn)，并沒有規(guī)定其擴(kuò)展次序造成的。

一般來說，對于大多數(shù)實(shí)際問題，即便是h2(n)≥h1(n)時，用A2搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)也不會比用A1搜索所擴(kuò)展的節(jié)點(diǎn)數(shù)多。第三，這里所說的"擴(kuò)展的節(jié)點(diǎn)數(shù)"，是這樣來計(jì)算的，同一個節(jié)點(diǎn)不管它被擴(kuò)展多少次（在A算法的第六步，對于ml類節(jié)點(diǎn)，存在重新放回到OPEN表的可能，因此一個節(jié)點(diǎn)有可能被反復(fù)擴(kuò)展多次，在后面我們會看到這樣的例子），在計(jì)算"擴(kuò)展的節(jié)點(diǎn)數(shù)"時，都只計(jì)算一次，而不管它被重復(fù)擴(kuò)展了多少次。

該定理的意義在于，在使用A*算法求解問題時，定義的啟發(fā)函數(shù)h，在滿足A*的條件下，應(yīng)盡可能地大一些，使其接近于h*，這樣才能使得搜索的效率高。證明：使用數(shù)學(xué)歸納法，對節(jié)點(diǎn)的深度應(yīng)用歸納法。

（1）對深度d(n)=0的節(jié)點(diǎn)（即初始節(jié)點(diǎn)s），定理結(jié)論成立，即若s為目標(biāo)節(jié)點(diǎn)，則A1和A2都不擴(kuò)展s，否則A1和A2都擴(kuò)展了s（歸納法前提）。

（2）設(shè)深度d(n)≤k，對所有路徑的端節(jié)點(diǎn)，定理結(jié)論都成立（歸納法假設(shè)）。

（3）要證明d(n)＝k+1時，所有路徑的端節(jié)點(diǎn)，結(jié)論成立，我們用反證法證明。

設(shè)A2搜索樹上有一個節(jié)點(diǎn)n（d(n)=k+1）被A2擴(kuò)展了，而對應(yīng)于A1搜索樹上的這個節(jié)點(diǎn)n，沒有被A1擴(kuò)展。根據(jù)歸納法假設(shè)條件，A1擴(kuò)展了n的父節(jié)點(diǎn)，n是在A1搜索樹上，因此A1結(jié)束時，n必定保留在其OPEN表上，n沒有被A1選擇擴(kuò)展，有

f1(n)≥f*(s)，即g1(n)+h1(n)≥f*(s)

所以

h1(n)≥f*(s)-g1(n)（1）

另一方面A2擴(kuò)展了n，有

f2(n)≤f*(s)，即g2(n)+h2(n)≤f*(s)

所以

h2(n)≤f*(s)-g2(n)（2）

由于d=k時，A2擴(kuò)展的節(jié)點(diǎn)，A1也一定擴(kuò)展，故有

g1(n)≤g2(n)（因A1擴(kuò)展的節(jié)點(diǎn)數(shù)可能較多）

所以

h1(n)≥f*(s)-g1(n)≥f*(s)-g2(n)（3）

比較式（2）、（3）可得：至少在節(jié)點(diǎn)n上有h1(n)≥h2(n)，這與定理的前提條件矛盾，因此存在節(jié)點(diǎn)n的假設(shè)不成立。[證畢]由這個定理可知，使用啟發(fā)函數(shù)h(n)的A*算法，比不使用h(n)(h(n)≡0)的算法，求得最佳路徑時擴(kuò)展的節(jié)點(diǎn)數(shù)要少，下面的搜索圖例子可看出比較的結(jié)果。當(dāng)h≡0時，求得最佳解路（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ò)展。當(dāng)然一般情況下，并不一定都能達(dá)到這種效果，主要在于獲取完備的啟發(fā)信息較為困難。啟發(fā)函數(shù)h(n)的效果比較

A*算法的改進(jìn)

在A算法的第六步，對于ml類節(jié)點(diǎn)，存在重新放回到OPEN表的可能，因此一個節(jié)點(diǎn)有可能被反復(fù)擴(kuò)展多次。因此單純用"擴(kuò)展的節(jié)點(diǎn)數(shù)"并不能客觀地來評判搜索算法的好壞。因?yàn)榧幢闶菙U(kuò)展的節(jié)點(diǎn)數(shù)比較少，但如果很多節(jié)點(diǎn)被多次重復(fù)擴(kuò)展的話，搜索效率同樣是很低的。前面討論了啟發(fā)函數(shù)對擴(kuò)展節(jié)點(diǎn)數(shù)所起的作用。如果用擴(kuò)展節(jié)點(diǎn)數(shù)作為評價搜索效率的準(zhǔn)則，那么可以發(fā)現(xiàn)A算法第6步中，對m1類節(jié)點(diǎn)要重新放回OPEN表中的操作，將引起多次擴(kuò)展同一個節(jié)點(diǎn)的可能，因而即使擴(kuò)展的節(jié)點(diǎn)數(shù)少，但重復(fù)擴(kuò)展某些節(jié)點(diǎn)，也將導(dǎo)致搜索效率下降。下圖給出同一節(jié)點(diǎn)多次擴(kuò)展的例子，并列出了調(diào)用算法A*過程時OPEN和CLOSED表的狀態(tài)。從CLOSED表可以看出，在修改m1類節(jié)點(diǎn)指針過程中，節(jié)點(diǎn)A、B、C重復(fù)擴(kuò)展，次數(shù)分別為8、4、2，總共擴(kuò)展16次節(jié)點(diǎn)。A*算法多次擴(kuò)展同一節(jié)點(diǎn)搜索圖例子

通過這個例子使我們看到確實(shí)有重復(fù)擴(kuò)展節(jié)點(diǎn)的想象存在。為什么會有重復(fù)擴(kuò)展一個節(jié)點(diǎn)的現(xiàn)象發(fā)生呢？主要就是因?yàn)樵跀U(kuò)展一個節(jié)點(diǎn)時，A*并不能保證此時就已經(jīng)找到了從初始節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)n的最短路徑，使得算法在第六步，有可能將其重新放回到OPEN表中，而放入OPEN表以后，該節(jié)點(diǎn)就有可能被再次擴(kuò)展。

有沒有辦法避免或者減少重復(fù)擴(kuò)展節(jié)點(diǎn)的情況發(fā)生呢？答案是肯定的。主要途徑有兩個，一個是對啟發(fā)函數(shù)h進(jìn)一步加上限制，使得A*算法在擴(kuò)展一個節(jié)點(diǎn)n時，就已經(jīng)找到了從初始節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)n的最短路徑，這樣就避免了將n重新放回到OPEN表中的可能，從而避免了重復(fù)擴(kuò)展節(jié)點(diǎn)現(xiàn)象的發(fā)生。另一個是還是使用原來的A*對啟發(fā)函數(shù)h的限制條件，但改變算法本身，使之減少重復(fù)擴(kuò)展節(jié)點(diǎn)現(xiàn)象。但這種對算法的改變要堅(jiān)持兩點(diǎn)，一是要保持A*算法的可采納性，不能因?yàn)闇p少了重復(fù)擴(kuò)展節(jié)點(diǎn)，而失去可采納性；二是不能增加過多的計(jì)算工作量，不然重復(fù)擴(kuò)展節(jié)點(diǎn)問題解決了，但增加了計(jì)算工作量，沒有達(dá)到提高搜索效率的目的。

定理5：若h(n)滿足單調(diào)限制條件，則A*擴(kuò)展了節(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的最佳路徑。即若A*選n來擴(kuò)展，在單調(diào)限制條件下有g(shù)(n)=g*(n)。定理6：若h(n)滿足單調(diào)限制，則由A*所擴(kuò)展的節(jié)點(diǎn)序列，其f值是非遞減的，即f(ni)≤f(nj)。根據(jù)定理5，在應(yīng)用A*算法時，在第6步可不必進(jìn)行節(jié)點(diǎn)的指針修正操作，因而改善了A*的效率。另一方面我們從上圖的例子看出，因h不滿足單調(diào)限制條件，在擴(kuò)展節(jié)點(diǎn)n時，有可能還沒有找到到達(dá)n的最佳路徑，因此該節(jié)點(diǎn)還會再次被放入OPEN中，從而造成了該節(jié)點(diǎn)被重復(fù)擴(kuò)展。

為了使A*算法少進(jìn)行重復(fù)擴(kuò)展，對A算法做如下的修改，稱為修正過程A（修正的A算法）。在改進(jìn)A*算法的時候，一是要保持A*算法的可采納性，二是不能增加過多的計(jì)算工作量。由推論2.1我們知道，OPEN表上任一具有f(n)<f*(s)的節(jié)點(diǎn)n定會被擴(kuò)展。由推論3.1我們知道，A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)≤f*(s)。這兩個推論正是我們改進(jìn)A*算法的理論基礎(chǔ)。算法改進(jìn)的基本思路是：我們?nèi)韵馎*算法那樣，按照節(jié)點(diǎn)的f值從小到大排序OPEN表中的節(jié)點(diǎn)，我們以f*(s)為界將OPEN表劃分為兩部分，一部分由那些f值小于f*(s)的節(jié)點(diǎn)組成，我們稱其為NEST，其他的節(jié)點(diǎ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é)點(diǎn)集合。

IFNEST≠{}THENn:＝n(mingi)，即NEST在g最小的節(jié)點(diǎn)

ELSEn:＝FIRST（OPEN），fm:=f(n)；NEST不空時，取其中g(shù)最小者作為當(dāng)前節(jié)點(diǎn)，否則取OPEN的第一個當(dāng)前節(jié)點(diǎn)。

④－⑧同過程A

現(xiàn)在看一下用修正A*搜索圖

算法的理論意義在于給出了求解最佳解的條件h(n)≤h*(n)。對給定的問題，函數(shù)h*(n)（n是變量）在問題有解的條件下客觀上是存在的，但在問題求解過程中不可能明確知道，因此對實(shí)際問題，能不能使所定義的啟發(fā)函數(shù)滿足下界范圍條件？如果困難很大，那么算法的實(shí)際應(yīng)用就會受到限制。下面將通過幾個應(yīng)用實(shí)例來說明這個問題。A*算法應(yīng)用舉例

283167541238

7654初始狀態(tài)目標(biāo)狀態(tài)下面給出該八數(shù)碼問題取不同啟發(fā)函數(shù)，應(yīng)用A*算法求得最佳解時所擴(kuò)展和生成的節(jié)點(diǎn)數(shù)。

羅馬尼亞城市搜索問題羅馬尼亞城市搜索問題羅馬尼亞城市搜索問題羅馬尼亞城市搜索問題羅馬尼亞城市搜索問題羅馬尼亞城市搜索問題迷宮問題迷宮圖從入口到出口有若干條路，求從入口到出口最短路徑的走法。下圖為一個簡單迷宮示意圖及其平面坐標(biāo)表示。以平面坐標(biāo)圖來表示迷宮的通路時，問題的狀態(tài)以所處的坐標(biāo)位置來表示，即綜合數(shù)據(jù)庫定義為(x,y)，1x,yN(N為迷宮問題的最大坐標(biāo)數(shù)），則迷宮問題歸結(jié)為求（1，1）到（4，4）的最短路徑問題。迷宮走法規(guī)定為向東、南、西和北前進(jìn)一步，由此可得規(guī)則集簡化形式如下：R1:if(x,y)then(x+1,y)R2:if(x,y)then(x,y-1)R3:if(x,y)then(x-1,y)R4:if(x,y)then(x,y+1)對于這個簡單例子，可給出狀態(tài)空間如下圖所示。出口入口(1,1)(4,4)入口出口迷宮問題及其表示對于這個簡單例子，可給出狀態(tài)空間如下圖所示。為求得最佳路徑，可使用A*算法。假定搜索一步取單位耗散，則可定義：h(n)=|xG-xn|+|yG-yn|其中(xG,yG)為目標(biāo)點(diǎn)坐標(biāo)，(xn,yn)為節(jié)點(diǎn)n的坐標(biāo)。由于該迷宮問題所有路都是水平或垂直的，沒有斜路，因此，h(n)＝|xG-xn|+|yG-yn|顯然可以滿足A*的條件。即h(n)h*(n)。取g(n)＝d(n)，有f(n)＝d(n)+h(n)。再設(shè)當(dāng)不同節(jié)點(diǎn)的f值相等時，以深度優(yōu)先排序，則搜索圖如下圖所示。最短路徑為（（1，1），(1,2),(1,3),（2，3），（2，4），（3，4），（3，3），（4，3），（4，4））。在該搜索圖中，目標(biāo)節(jié)點(diǎn)的f是8，有幾個節(jié)點(diǎn)的f值也是8，那么這幾個f值為8的節(jié)點(diǎn)，也有被擴(kuò)展的可能，就看他們在OPEN表中的具體排列次序了。這里假定了f值相等時，以深度優(yōu)先排序。A*算法的一個C++類----CAStarCAStar是一個實(shí)現(xiàn)A*算法的C++類的例子，它比一般的類復(fù)雜一點(diǎn)，因?yàn)檫@個類允許程序員提供他自己計(jì)算代價和有效性的函數(shù)，還有各種回調(diào)函數(shù)指針。這里只關(guān)注節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)和兩個重要的成員函數(shù)，這兩個成員函數(shù)LinkChild和UpdateParents含括了A*的大部分功能。首先來看節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：Class_asnode{Public_asNode(int,int);intf,g,h;intx,y;intnumchildren;intnumber;_asNode*parent;_asNode*next;_asNode*children[8];Void*dataptr;};節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)被當(dāng)成輔助一個成員變量初始化的袖珍類。成員變量是顯然的：如f,g和h，以及表示位置信息的x,y變量，numchildren記錄子孫的個數(shù)，而number是對地圖上每個位置的唯一標(biāo)識符。接著有一個指向父節(jié)點(diǎn)的指針。而那個叫next的指針用在Open表和Closed表里（看成鏈表）。然后有一個子孫的指針數(shù)組。最后一個指針變量是無類型的指針，程序員可以用它來給節(jié)點(diǎn)指定某些數(shù)據(jù)形式。CAStar::LinkChildLinkChild要傳入兩個指向_asNode結(jié)構(gòu)的指針。一個表示父節(jié)點(diǎn)(node)，另一個是只用x,y初始化的臨時節(jié)點(diǎn)(temp)。LinkChild實(shí)現(xiàn)了A*算法分解偽碼步驟6中的（1）和（2）。VoidCAStar::LinkChild（_asNode*node,_asNode*temp){intx=tempx;inty=tempy;intg=node+udFunc(udCost,node,temp,0,m_pCBData);intnum=Coord2Num(x,y);//首先，從temp中得到坐標(biāo)信息，注意我們是從父節(jié)點(diǎn)的g值和調(diào)用用戶自定義的代價函數(shù)udcost來計(jì)算g值。最后一行給節(jié)點(diǎn)產(chǎn)生一個唯一的標(biāo)識符。_asNode*check=NULL;If(check=CheckList(m_pOpen,num)){Nodechildren[nodenumchildren++]=check;If(g<checkg){checkparent=node;checkg=g;Checkf=g+checkh;}}elseif(check=CheckList(m_pClosed,num)){Nodechildren[nodenumchildren++]=check;If(g<checkg){checkparent=node;checkg=g;checkf=g+checkh;Updateparents(check);}}//若回顧偽碼，會發(fā)現(xiàn)必須先檢測節(jié)點(diǎn)是否在Open表或Closed表中。CheckList要傳入一個指向表頭的指針和一個可供查找的唯一的標(biāo)識符。如果函數(shù)找到這個標(biāo)識符，則返回指向與這個標(biāo)識符關(guān)聯(lián)的指針。如果這個節(jié)點(diǎn)在Open表中，那將其加入node的子孫數(shù)組。接著檢測從新節(jié)點(diǎn)計(jì)算所得的g是否比check的g小。不要忘了雖然check和temp都對應(yīng)地圖上相同的位置，但它們的來路可以是完全不同的。如果這個節(jié)點(diǎn)在Closed表中，那將其加入node的子孫數(shù)組。通過類似的步驟檢測g值大小。若不等式成立，那么必須對不只是當(dāng)前的父節(jié)點(diǎn)指針，還包括所有相連的節(jié)點(diǎn)更新f，g和h的值，而且很可能還有它們的父節(jié)點(diǎn)指針。我們會在LinkChild函數(shù)之后學(xué)習(xí)處理這些操作的函數(shù)。else{_asNode*newnode=new-asNode(x,y);newnodeparent=node;newnodeg=g;newnodeh=abs(x-m_iDX)+abs(y-m_iDY);newnodef=newnodeg+newnodeh;newnodenumber=Coord2Num(x,y);AddToOpen(newnode);Nodechildren[nodenumchildren++]=newnode;}}最后，如果這個節(jié)點(diǎn)不在Open表或Closed表中，就新建一個節(jié)點(diǎn)。賦予f,g和h的值，然后更新其父節(jié)點(diǎn)的子孫數(shù)組前將它添加入Open表中。2CAStar:UpdateparentsUpdateparents用一個節(jié)點(diǎn)作為其單一的參數(shù)，在A*樹中傳遞更新信息。這部分實(shí)現(xiàn)了A*算法的步驟6中的情況2。VoidCAStar::Updateparents(_asNode*node){intg=nodeg,c=nodenumchildren;_asNode*kid=NULL;for(inti=0;i<c;i++){kid=nodechildren[i];if(g+1<kidg){kidg=g+1;kidf=kidg+kidh;kidparent=node;push(kid);}}這是算法的前半部分，可以清楚地看出這個算法要做什么。而問題是為什么要做這些？這個節(jié)點(diǎn)的g值已經(jīng)在調(diào)用Update函數(shù)之前更新過，因此，檢查所有的子孫，最好再看看是否改進(jìn)g的值。由于必須傳遞變動信息，所有更新過的節(jié)點(diǎn)將放在棧里等待算法的下半部分再次調(diào)出。_asNode*parent;While(m_pStack){parent=Pop();c=parent

numchildren;for(inti=0;i<c;i++){kid=parentchildren[i];if(parent-->g+1<kidg){kidg=parentg+;

udFunc(udCost,parent,kid,0,m_pCBDate);kidf=kidg+kidh;kidparent=parent;push(kid);}}}算法的后半部分基本上和前半部分一樣，但用棧中彈出的節(jié)點(diǎn)代替了node。再次地，如果我們要更新一個節(jié)點(diǎn)，必須將其放回棧中以繼續(xù)傳遞變動信息。CAStar是可擴(kuò)展的，可以輕易地適應(yīng)任何具體應(yīng)用。CAStar的主要優(yōu)點(diǎn)是程序員可以提供代價和有效性的計(jì)算函數(shù)。這意味著CAStar可以時刻應(yīng)付任何2D地圖的問題評價函數(shù)的啟發(fā)能力首先我們通過八數(shù)碼問題為例說明A算法的啟發(fā)能力與選擇啟發(fā)函數(shù)h(n)的關(guān)系。一般來說啟發(fā)能力強(qiáng)，則搜索效率較高。有時選用不是h*(n)下界范圍的h(n)時，雖然會犧牲找到最佳解的性能，但可使啟發(fā)能力得到改善，從而有利于求解一些較難的問題。

求解這個八數(shù)碼問題，使用啟發(fā)函數(shù)h(n)＝P(n)時，仍不能估計(jì)出交換相鄰兩個將牌位置難易程序的影響，為此可再引入S(n)分量。S(n)是對節(jié)點(diǎn)n中將牌排列順序的計(jì)分值，規(guī)定對非中心位置的將牌，順某一方向檢查，若某一將牌后面跟的后繼者和目標(biāo)狀態(tài)相應(yīng)將牌的順序相比不一致時，則該將牌估分取2，一致時則估分取0；對中心位置有將牌時估分取1，無將牌時估分值取0；所有非中心位置每個將牌估分總和加上中心位置的估分值定義為S(n)。依據(jù)這些啟發(fā)信息，取h(n)＝P(n)+3S(n)時，就是用f(n)＝g(n)+P(n)+3S(n)來估計(jì)最佳路徑的耗散值。f(n)值小的節(jié)點(diǎn)，確能反映該節(jié)點(diǎn)愈有希望處于到達(dá)目標(biāo)節(jié)點(diǎn)的最佳路徑上。圖2.18給出了該問題的搜索樹，圖中給出各節(jié)點(diǎn)的f值，圓圈中的數(shù)字表示擴(kuò)展順序。由圖看出h(n)函數(shù)不滿足下界范圍，但在該問題中，剛好找到了最小長度（18步）的解路徑。該例子給了一個不滿足A*條件的h函數(shù)。從圖上可以看出，啟發(fā)效果非常的好，對于需要18步才能完成的8數(shù)碼問題，幾乎沒有擴(kuò)展什么多余的節(jié)點(diǎn)，就找到了解路徑。這里所用的方法一是組合兩個不同的啟發(fā)函數(shù)；二是采取加權(quán)的方法（這里對S(n)加權(quán)為3），來加大S(n)的作用。這樣得到的啟發(fā)函數(shù)由于不滿足A*條件，因此不能保證找到問題的最佳解，但往往可以提高搜索效率，加快找到解的速度。由于這樣的啟發(fā)函數(shù)還是反映了被評估節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑耗散值的多少，算法雖然不能一定找到最優(yōu)解，但一般來說，找到的也是一個可以被接受的滿意解。很多情況下，滿意解就足夠了，最優(yōu)解并沒有什么特殊的意義，二者可能相差很少，但卻使得問題簡單了很多。值得指出的是，該例子所得到的解，剛好是一個最優(yōu)解。

還有一個決定搜索算法啟發(fā)能力的因素是涉及到計(jì)算啟發(fā)函數(shù)的工作量，從被擴(kuò)展的節(jié)點(diǎn)數(shù)最少的角度看，h≡h*最優(yōu)，但這可能導(dǎo)致繁重的計(jì)算工作量。有時候一個不是h*下界范圍的h函數(shù)可能比起下界范圍的h函數(shù)更容易計(jì)算，而且被擴(kuò)展節(jié)點(diǎn)的總數(shù)可以減少，使啟發(fā)能力加倍得到改善，雖然犧牲了可采納性，但從啟發(fā)能力的角度看仍是可取的。

在某些情況下，要改變啟發(fā)能力，可以通過對h函數(shù)乘以加權(quán)系數(shù)的簡單方法實(shí)現(xiàn)。當(dāng)加權(quán)系數(shù)很大時，g分量的作用相對減弱，因而可略去不計(jì)，這相當(dāng)于在搜索期間任何階段上，我們不在乎到目前為止所得到的路徑耗散值，而只關(guān)心找到目標(biāo)節(jié)點(diǎn)所需的剩余工作量，即可以使用f≡h作為評價函數(shù)來對OPEN表上的節(jié)點(diǎn)排序。但是另一方面為了保證最終能找到通向目標(biāo)節(jié)點(diǎn)的路徑，即便并不要求尋找一條最小耗散的路徑，也還是應(yīng)當(dāng)考慮g的作用。特別是當(dāng)h不是一個理想的估計(jì)時，在f中把g考慮進(jìn)去就是在搜索中添加一個寬度優(yōu)先分量，從而保證了隱含圖中不會有某些部分不被搜索到。而只擴(kuò)展h值最小的節(jié)點(diǎn)，則會引起搜索過程擴(kuò)展了一些靠不住的節(jié)點(diǎn)。

評價函數(shù)中，g和h相對比例可通過選擇f＝g+wh中w的大小加以控制。w是一個正數(shù)，很大的w值則會過份強(qiáng)調(diào)啟發(fā)分量，而過小的w值則突出寬度優(yōu)先的特征。經(jīng)驗(yàn)證明使w值隨搜索樹中節(jié)點(diǎn)深度成反比變化，可提高搜索效率。即在深度淺的地方，搜索主要依賴于啟發(fā)分量；而較深的地方，搜索逐漸變成寬度優(yōu)先，以保證到達(dá)目標(biāo)的某一條路徑最終被找到。

總結(jié)以上討論，得出影響算法A啟發(fā)能力的三個重要因素是：

（1）路徑的耗散值；(2)求解路徑時所擴(kuò)展的節(jié)點(diǎn)數(shù)；(3）計(jì)算h所需的工作量。因此選擇h函數(shù)時，應(yīng)綜合考慮這些因素以便使啟發(fā)能力最大。右邊內(nèi)容作為本部分內(nèi)容的補(bǔ)充，了解一下就可以了，如果想詳細(xì)了解，可以看有關(guān)的書籍，不在本書的討論范圍內(nèi)。

1．弱方法

人工智能范疇的一些問題都比較復(fù)雜，一般無法用直接求解的方法找到解答，因此通常都要藉助于搜索技術(shù)。前面幾節(jié)討論的搜索方法，其描述均與問題領(lǐng)域無關(guān)，如果把這些方法應(yīng)用于特定問題的領(lǐng)域時，其效率依賴于該領(lǐng)域知識應(yīng)用的情況，從我們舉過的幾個例子就可說明這個問題。但由于這些方法難于克服搜索過程的組合爆炸問題，因此在人工智能領(lǐng)域中，把這些方法統(tǒng)稱為“弱方法”。這些搜索方法可用來求解不存在確定求解算法的某一類問題，或者雖然有某種求解算法，但復(fù)雜性很高，有不少均屬NP－完全類的問題。為避免求解過程的組合爆炸，在搜索算法中引入啟發(fā)性信息，多數(shù)情況能以較少的代價找到解，但并不能保證任何情況下都能獲得解，這就是所謂”弱方法“的含義。當(dāng)然如果引入強(qiáng)有力的啟發(fā)信息，則求解過程就能顯示出"強(qiáng)"的作