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

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

有信息搜索算法

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

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

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

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

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

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

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

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)過(guò)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)g的最短路徑的耗散值。

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

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

過(guò)程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通過(guò)n到mi的耗散值，f（n，mi）是從s通過(guò)n、mi到目標(biāo)節(jié)點(diǎn)耗散值的估計(jì)?！DD（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）時(shí)，把ml重放回OPEN中，不必考慮修改到其子節(jié)點(diǎn)的指針。

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

⑧GOLOOP。A算法同樣由一般的圖搜索算法改變而成。在算法的第7步，按照f(shuō)值從小到大對(duì)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)是與問(wèn)題有關(guān)的，需要根據(jù)具體的問(wèn)題來(lái)定義。有了g(n)和h(n)的值，將他們加起來(lái)就得到f(n)的值了。請(qǐng)大家注意A算法的結(jié)束條件：當(dāng)從OPEN中取出第一節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則算法成功結(jié)束。而不是在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，只要目標(biāo)節(jié)點(diǎn)一出現(xiàn)就立即結(jié)束。我們?cè)诤竺鎸?huì)看到，正是由于有了這樣的結(jié)束判斷條件，才使得A算法有很好的性質(zhì)。

算法中f（n）規(guī)定為對(duì)從初始節(jié)點(diǎn)s出發(fā)，約束通過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)t，最小耗散值路徑的耗散值f*(n)的估計(jì)值，通常取正值。f（n）由兩個(gè)分量組成，其中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無(wú)通路時(shí)則k（ni，nj）無(wú)意義），則g*（n）＝k（s，n），h*（n）＝mink（n，ti），其中ti是目標(biāo)節(jié)點(diǎn)集，k（n，ti）就是從n到每一個(gè)目標(biāo)節(jié)點(diǎn)最小耗散值路徑的耗散值，h*（n）是其中最小值的那條路徑的耗散值，而具有h*（n）值的路徑是n到ti的最佳路徑。由此可得f*（n）＝g*（n）＋h*（n）就表示s→ti并約束通過(guò)節(jié)點(diǎn)n的最佳路徑的耗散值。

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

下面再以八數(shù)碼問(wèn)題為例說(shuō)明好的優(yōu)先搜索策略的應(yīng)用過(guò)程。設(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ù)碼游戲搜索樹(shù)，圖中括弧中的數(shù)字表示該節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f。算法每一循環(huán)結(jié)束時(shí)，其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ù)碼問(wèn)題的搜索圖。其中A、B、C等符號(hào)，只是為了標(biāo)記節(jié)點(diǎn)的名稱(chēng)，沒(méi)有特殊意義。這些符號(hào)旁邊括弧中的數(shù)字是該節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f。而圓圈中的值，則表示節(jié)點(diǎn)的擴(kuò)展順序。從圖中可以看出，在第二步選擇節(jié)點(diǎn)B擴(kuò)展之后，OPEN表中f值最小的節(jié)點(diǎn)有D和E兩個(gè)節(jié)點(diǎn)，他們的f值都是5。在出現(xiàn)相同的f值時(shí)，A算法并沒(méi)有規(guī)定首先擴(kuò)展哪個(gè)節(jié)點(diǎn)，可以任意選擇其中的一個(gè)節(jié)點(diǎn)首先擴(kuò)展。返回使用啟發(fā)函數(shù)的八數(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ù)碼問(wèn)題的搜索圖。其中A、B、C等符號(hào)，只是為了標(biāo)記節(jié)點(diǎn)的名稱(chēng)，沒(méi)有特殊意義。這些符號(hào)旁邊括弧中的數(shù)字是該節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f。而圓圈中的值，則表示節(jié)點(diǎn)的擴(kuò)展順序。從圖中可以看出，在第二步選擇節(jié)點(diǎn)B擴(kuò)展之后，OPEN表中f值最小的節(jié)點(diǎn)有D和E兩個(gè)節(jié)點(diǎn)，他們的f值都是5。在出現(xiàn)相同的f值時(shí)，A算法并沒(méi)有規(guī)定首先擴(kuò)展哪個(gè)節(jié)點(diǎn)，可以任意選擇其中的一個(gè)節(jié)點(diǎn)首先擴(kuò)展。

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

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

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

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

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

Iasi

Neamt

Iasi

Neamt

時(shí)間復(fù)雜性?

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

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

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

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

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

證明：設(shè)A搜索失敗，則算法在第2步結(jié)束，OPEN表變空，而CLOSED表中的節(jié)點(diǎn)是在結(jié)束之前被擴(kuò)展過(guò)的節(jié)點(diǎn)。由于圖有解，令（n0=s，n1，n2，…，nk=t）表示某一解路徑，我們從nk開(kāi)始逆向逐個(gè)檢查該序列的節(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已被處理過(guò)。若ni+1是目標(biāo)節(jié)點(diǎn)，則搜索成功，否則它被加入到CLOSED中，這兩種情況都與搜索失敗的假設(shè)矛盾，因此對(duì)有限圖不失敗則成功。[證畢]因?yàn)锳﹡是A的特例，因此它具有A的所有性質(zhì)。這樣對(duì)有限圖如果有解，則A﹡一定能在找到到達(dá)目標(biāo)的路徑結(jié)束，下面要證明即使是無(wú)限圖，A﹡也能找到最佳解結(jié)束。我們先證兩個(gè)引理：引理2.1：對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)點(diǎn)t的一條路徑，則A﹡不結(jié)束時(shí)，在OPEN中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f﹡(s)。在如下的證明中，隱含了兩個(gè)假設(shè)：（1）任何兩個(gè)節(jié)點(diǎn)之間的耗散值都大于某個(gè)給定的大于零的常量；（2）h(n)對(duì)于任何n來(lái)說(shuō)，都大于等于零。

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

，則

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

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

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

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

（2）設(shè)找到一個(gè)目標(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)

這時(shí)算法A*應(yīng)選n作為當(dāng)前節(jié)點(diǎn)擴(kuò)展，不可能選t，從而也不會(huì)去測(cè)試目標(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)中選擇一個(gè)節(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不會(huì)是目標(biāo)節(jié)點(diǎn)，且搜索沒(méi)有結(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*的過(guò)程中，如果選作擴(kuò)展的節(jié)點(diǎn)n，其評(píng)價(jià)函數(shù)值f(n)=f*(n)，則不會(huì)去擴(kuò)展多余的節(jié)點(diǎn)就可找到解。可以想象到f(n)越接近于f*(n)，擴(kuò)展的節(jié)點(diǎn)數(shù)就會(huì)越少，即啟發(fā)函數(shù)中，應(yīng)用的啟發(fā)信息（問(wèn)題知識(shí)）愈多，擴(kuò)展的節(jié)點(diǎn)數(shù)就越少。定理4：有兩個(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)至少和A2一樣多。

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

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

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

（1）對(duì)深度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，對(duì)所有路徑的端節(jié)點(diǎn)，定理結(jié)論都成立（歸納法假設(shè)）。

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

設(shè)A2搜索樹(shù)上有一個(gè)節(jié)點(diǎn)n（d(n)=k+1）被A2擴(kuò)展了，而對(duì)應(yīng)于A1搜索樹(shù)上的這個(gè)節(jié)點(diǎn)n，沒(méi)有被A1擴(kuò)展。根據(jù)歸納法假設(shè)條件，A1擴(kuò)展了n的父節(jié)點(diǎn)，n是在A1搜索樹(shù)上，因此A1結(jié)束時(shí)，n必定保留在其OPEN表上，n沒(méi)有被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時(shí)，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è)不成立。[證畢]由這個(gè)定理可知，使用啟發(fā)函數(shù)h(n)的A*算法，比不使用h(n)(h(n)≡0)的算法，求得最佳路徑時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)要少，下面的搜索圖例子可看出比較的結(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)都沒(méi)有被擴(kuò)展。當(dāng)然一般情況下，并不一定都能達(dá)到這種效果，主要在于獲取完備的啟發(fā)信息較為困難。啟發(fā)函數(shù)h(n)的效果比較

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

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

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

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

定理5：若h(n)滿足單調(diào)限制條件，則A*擴(kuò)展了節(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的最佳路徑。即若A*選n來(lái)擴(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*算法時(shí)，在第6步可不必進(jìn)行節(jié)點(diǎn)的指針修正操作，因而改善了A*的效率。另一方面我們從上圖的例子看出，因h不滿足單調(diào)限制條件，在擴(kuò)展節(jié)點(diǎn)n時(shí)，有可能還沒(méi)有找到到達(dá)n的最佳路徑，因此該節(jié)點(diǎn)還會(huì)再次被放入OPEN中，從而造成了該節(jié)點(diǎn)被重復(fù)擴(kuò)展。

為了使A*算法少進(jìn)行重復(fù)擴(kuò)展，對(duì)A算法做如下的修改，稱(chēng)為修正過(guò)程A（修正的A算法）。在改進(jìn)A*算法的時(shí)候，一是要保持A*算法的可采納性，二是不能增加過(guò)多的計(jì)算工作量。由推論2.1我們知道，OPEN表上任一具有f(n)<f*(s)的節(jié)點(diǎn)n定會(huì)被擴(kuò)展。由推論3.1我們知道，A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)≤f*(s)。這兩個(gè)推論正是我們改進(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)組成，我們稱(chēng)其為NEST，其他的節(jié)點(diǎn)屬于另一個(gè)部分。

修正過(guò)程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不空時(shí)，取其中g(shù)最小者作為當(dāng)前節(jié)點(diǎn)，否則取OPEN的第一個(gè)當(dāng)前節(jié)點(diǎn)。

④－⑧同過(guò)程A

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

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

283167541238

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

羅馬尼亞城市搜索問(wèn)題羅馬尼亞城市搜索問(wèn)題羅馬尼亞城市搜索問(wèn)題羅馬尼亞城市搜索問(wèn)題羅馬尼亞城市搜索問(wèn)題羅馬尼亞城市搜索問(wèn)題迷宮問(wèn)題迷宮圖從入口到出口有若干條路，求從入口到出口最短路徑的走法。下圖為一個(gè)簡(jiǎn)單迷宮示意圖及其平面坐標(biāo)表示。以平面坐標(biāo)圖來(lái)表示迷宮的通路時(shí)，問(wèn)題的狀態(tài)以所處的坐標(biāo)位置來(lái)表示，即綜合數(shù)據(jù)庫(kù)定義為(x,y)，1x,yN(N為迷宮問(wèn)題的最大坐標(biāo)數(shù)），則迷宮問(wèn)題歸結(jié)為求（1，1）到（4，4）的最短路徑問(wèn)題。迷宮走法規(guī)定為向東、南、西和北前進(jìn)一步，由此可得規(guī)則集簡(jiǎn)化形式如下：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)對(duì)于這個(gè)簡(jiǎn)單例子，可給出狀態(tài)空間如下圖所示。出口入口(1,1)(4,4)入口出口迷宮問(wèn)題及其表示對(duì)于這個(gè)簡(jiǎn)單例子，可給出狀態(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)。由于該迷宮問(wèn)題所有路都是水平或垂直的，沒(méi)有斜路，因此，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值相等時(shí)，以深度優(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，有幾個(gè)節(jié)點(diǎn)的f值也是8，那么這幾個(gè)f值為8的節(jié)點(diǎn)，也有被擴(kuò)展的可能，就看他們?cè)贠PEN表中的具體排列次序了。這里假定了f值相等時(shí)，以深度優(yōu)先排序。A*算法的一個(gè)C++類(lèi)----CAStarCAStar是一個(gè)實(shí)現(xiàn)A*算法的C++類(lèi)的例子，它比一般的類(lèi)復(fù)雜一點(diǎn)，因?yàn)檫@個(gè)類(lèi)允許程序員提供他自己計(jì)算代價(jià)和有效性的函數(shù)，還有各種回調(diào)函數(shù)指針。這里只關(guān)注節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)和兩個(gè)重要的成員函數(shù)，這兩個(gè)成員函數(shù)LinkChild和UpdateParents含括了A*的大部分功能。首先來(lái)看節(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)成輔助一個(gè)成員變量初始化的袖珍類(lèi)。成員變量是顯然的：如f,g和h，以及表示位置信息的x,y變量，numchildren記錄子孫的個(gè)數(shù)，而number是對(duì)地圖上每個(gè)位置的唯一標(biāo)識(shí)符。接著有一個(gè)指向父節(jié)點(diǎn)的指針。而那個(gè)叫next的指針用在Open表和Closed表里（看成鏈表）。然后有一個(gè)子孫的指針數(shù)組。最后一個(gè)指針變量是無(wú)類(lèi)型的指針，程序員可以用它來(lái)給節(jié)點(diǎn)指定某些數(shù)據(jù)形式。CAStar::LinkChildLinkChild要傳入兩個(gè)指向_asNode結(jié)構(gòu)的指針。一個(gè)表示父節(jié)點(diǎn)(node)，另一個(gè)是只用x,y初始化的臨時(shí)節(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)用用戶(hù)自定義的代價(jià)函數(shù)udcost來(lái)計(jì)算g值。最后一行給節(jié)點(diǎn)產(chǎn)生一個(gè)唯一的標(biāo)識(shí)符。_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);}}//若回顧偽碼，會(huì)發(fā)現(xiàn)必須先檢測(cè)節(jié)點(diǎn)是否在Open表或Closed表中。CheckList要傳入一個(gè)指向表頭的指針和一個(gè)可供查找的唯一的標(biāo)識(shí)符。如果函數(shù)找到這個(gè)標(biāo)識(shí)符，則返回指向與這個(gè)標(biāo)識(shí)符關(guān)聯(lián)的指針。如果這個(gè)節(jié)點(diǎn)在Open表中，那將其加入node的子孫數(shù)組。接著檢測(cè)從新節(jié)點(diǎn)計(jì)算所得的g是否比check的g小。不要忘了雖然check和temp都對(duì)應(yīng)地圖上相同的位置，但它們的來(lái)路可以是完全不同的。如果這個(gè)節(jié)點(diǎn)在Closed表中，那將其加入node的子孫數(shù)組。通過(guò)類(lèi)似的步驟檢測(cè)g值大小。若不等式成立，那么必須對(duì)不只是當(dāng)前的父節(jié)點(diǎn)指針，還包括所有相連的節(jié)點(diǎn)更新f，g和h的值，而且很可能還有它們的父節(jié)點(diǎn)指針。我們會(huì)在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;}}最后，如果這個(gè)節(jié)點(diǎn)不在Open表或Closed表中，就新建一個(gè)節(jié)點(diǎn)。賦予f,g和h的值，然后更新其父節(jié)點(diǎn)的子孫數(shù)組前將它添加入Open表中。2CAStar:UpdateparentsUpdateparents用一個(gè)節(jié)點(diǎn)作為其單一的參數(shù)，在A*樹(shù)中傳遞更新信息。這部分實(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);}}這是算法的前半部分，可以清楚地看出這個(gè)算法要做什么。而問(wèn)題是為什么要做這些？這個(gè)節(jié)點(diǎn)的g值已經(jīng)在調(diào)用Update函數(shù)之前更新過(guò)，因此，檢查所有的子孫，最好再看看是否改進(jìn)g的值。由于必須傳遞變動(dòng)信息，所有更新過(guò)的節(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。再次地，如果我們要更新一個(gè)節(jié)點(diǎn)，必須將其放回棧中以繼續(xù)傳遞變動(dòng)信息。CAStar是可擴(kuò)展的，可以輕易地適應(yīng)任何具體應(yīng)用。CAStar的主要優(yōu)點(diǎn)是程序員可以提供代價(jià)和有效性的計(jì)算函數(shù)。這意味著CAStar可以時(shí)刻應(yīng)付任何2D地圖的問(wèn)題評(píng)價(jià)函數(shù)的啟發(fā)能力首先我們通過(guò)八數(shù)碼問(wèn)題為例說(shuō)明A算法的啟發(fā)能力與選擇啟發(fā)函數(shù)h(n)的關(guān)系。一般來(lái)說(shuō)啟發(fā)能力強(qiáng)，則搜索效率較高。有時(shí)選用不是h*(n)下界范圍的h(n)時(shí)，雖然會(huì)犧牲找到最佳解的性能，但可使啟發(fā)能力得到改善，從而有利于求解一些較難的問(wèn)題。

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

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

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

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

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

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

1．弱方法

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