本節書摘來自華章計算機《人工智能：計算agent基礎》一書中的第3章，第3.6節,作者：（加）david l.poole,alan k.mackworth 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
前面說的所有的算法都是無資訊的，并沒有考慮目标節點在哪裡。它們沒有使用任何指引它們該向哪去的資訊，除非它們無意中發現目标。關于哪些節點是最有希望節點的啟發資訊的一種形式叫做啟發函數h(n)，這個函數參數為節點n，傳回一個非負實數，即為節點n到目标節點的估計花費。如果h(n)的值小于或等于從n節點到目标節點最低花費路徑的實際花費，那麼就說啟發函數是“低估”的。
啟發函數是得出目标的搜尋方向的一種方式。它提供一個有資訊依據的方法來猜測節點的哪個鄰居将會通往目标節點。
啟發函數沒有什麼神奇可言。它隻能使用可容易地從節點上擷取的資訊。通常情況下，需要在以下兩個值之間做折中：擷取一個節點的啟發值所花費的工作量，以及一個節點的啟發值如何準确地衡量從該節點到目标的實際路徑花費。
得到啟發函數的一個标準方式是：解決一個更簡單點的問題，然後将簡化了的問題的實際花費作為原始問題的啟發函數。
【例3-12】 圖3-2中，從節點到目标位置的直線距離可以作為啟發函數。
下述執行個體中假設如下啟發函數：
h函數就是一個低估，因為h的值小于或等于從節點到目标的最低花費路徑的真實花費。對于o123來說，h的值就是真實花費值。對b1來說，則是很大的低估，看起來b1離目标很近，但其實隻能通過一條很長的路徑才能到達目标。而對于c1來說，這個h值則差之千裡，因為看起來它離目标節點很近，事實上沒有從該節點通往目标節點的路徑。
【例3-13】 在例3-2中的投遞機器人，狀态空間包含要運送的包裹。假定花費函數是機器人運送所有包裹走過的總距離。一個可能的啟發函數就是一個包裹到目的地的最大距離。如果機器人隻能攜帶一個包裹，那麼可能的啟發函數就是包裹經過的距離之和。如果機器人一次可以攜帶多個包裹，那麼這個啟發函數就不是真實花費的低估了。
h函數也可以擴充适用（非空）路徑。路徑的啟發值是路徑最後的節點的啟發值。即
h(〈no,…,nk〉)=h(nk)
啟發函數的一個簡單應用是在深度優先搜尋中為鄰居排序，這些節點被依次壓入堆棧來表示邊界，這樣鄰居被加入邊界，是以最先選擇的是最優鄰居，即所謂“啟發式深度優先”(heuristic depth-first search)算法。這種搜尋算法可以找到局部最優路徑，但是在搜尋另一條路徑之前，它會周遊所有已選路徑。盡管這個算法常用，但也受困于深度優先搜尋自身的問題。
啟發函數的另一種使用方式是：總是選擇邊界中具有最低啟發值的路徑，這叫做最優優先搜尋(best-first search)。這個方法通常不太有效，它會選擇看上去最有希望的路徑，因為他們離目标節點很近，但是路徑花費會不斷增加。
【例3-14】 如圖3-8所示，弧線的花費是它的長度。目标是找到從s到g的最短路徑。假定到節點g的歐幾裡得距離是啟發函數。啟發深度優先搜尋将會選擇位于s下面的節點，并永遠不會終止。相似地，因為位于s以下的所有節點看起來都不錯，最優優先搜尋将會在它們之間循環，而從不嘗試由s開始的其他可替換路徑。
3.6.1 a 搜尋
a 搜尋是最低花費優先搜尋和最優優先搜尋的結合，它在選擇路徑擴充時既要考慮路徑的花費也要考慮啟發資訊。對于邊界上的每一條路徑，a都會估計沿路徑從初始節點到目标節點的總路徑花費。它使用函數cost(p)（即已找到的路徑花費）和啟發函數h(p)（即從p的結尾到目标的估計花費）。
對于邊界上的任意路徑p，定義函數f(p)=cost(p)+h(p)，指沿着路徑p到目标節點的估計總花費。
如果n是路徑p的末節點，那麼可以描述為：
如果h(n)是從節點n到目标節點路徑花費的低估，那麼f(p)就是從初始節點經過p到目标節點路徑花費的低估。
是通過将邊界看做按照f(p)進行排序的優先級隊列來實作的。
【例3-15】 對例3-4運用a算法進行搜尋，并使用例3-12的啟發函數。在這個例子中，邊界上的路徑用路徑上最後一個節點來表示，下标是路徑的f值。初始邊界是：［o10321］，因為h(o103)=21，路徑花費是0。然後用鄰居替換，形成新的邊界：［b321,ts31,o10936］。
第一個元素代表路徑〈o103,b3〉，它的f的值為：f(〈o103,b3〉)=cost(〈o103,b3〉)+h(b3)=4+17=21。接着b3就被鄰居替換，邊界變為：［b121,b429,ts31,o10936］。
然後到b1的路徑被b1的鄰居替換，邊界變為：［c221,b429,b229,ts31,o10936］。
接下來，到c2的路徑被它的鄰居替換，邊界變為：［c121,b429,b229,c329,ts31,o10936］。
直到這個狀态，搜尋一直都在找看起來直接通往目标節點的路徑。下面，選擇c1被相鄰點替代，形成邊界：［b429,b229,c329,ts31,c335,o10936］。
直到這一步，到c3有兩條不同路徑。其中一條不經過c1，它的f值要比經過c1的另外一條路徑低。在後面，我們會考慮将其中一個路徑剪枝的情況。
這裡有兩條相同f值的路徑。算法沒有指定選擇哪條。假設下一步選擇了通往b4的路徑，并被它的相鄰點替換，形成邊界：［b229,c329,ts31,c335,o10936,o10942］。
然後選擇到b2的路徑并被鄰居替換，但這條路徑是空集，是以形成邊界：［c329,ts31,c335,b435,o10936,o10942］。
然後到c3的路徑被删除，它沒有鄰居，是以，新的邊界變為：［ts31,c335,b435,o10936,o10942］。
注意a算法是如何從一開始尋求多個不同路徑的。
最終會找到一個最低花費路徑。這個算法會強制嘗試很多不同的路徑，因為它們其中的一些路徑暫時看上去有最低花費。它仍然比最低花費優先和最優優先搜尋方法都要好。
【例3-16】 考慮圖3-8，對于其他的啟發方法，這是個有問題的圖。雖然由于啟發函數，起始情況從節點s向下搜尋，但最終路徑的花費變得非常大，是以它選擇了在實際最優路徑上的節點。
如果解存在，a總是能找到最優解，而且搜尋的第一條路徑就是最優的，這個性質叫做a的“可采納性”(admissibility)。它意味着：即使當搜尋空間是無限的，如果解存在，那麼就一定能找到解，而且找到的第一條路徑就是最優解，即從起始節點到目标節點的最低花費路徑。
命題3.1（a可采納性） 如果存在解，a總可以找一個解，并且找到的第一個解就是最優解，如果：
分支系數有限（每一個節點有有限個鄰居）；
弧線花費大于ε>0；
h(n)是從節點n到目标節點的最低花費路徑的最小實際花費值的下界。
證明：
a部分：可以找到解。如果弧線的花費都大于ε，ε>0，最終對于邊界中所有的路徑p，cost(p)會超過任何有限的數。是以，如果存在解，cost(p)會超過解的花費（搜尋樹的深度不會大于m/ε,這裡m是解的花費）。因為分支系數是有限的，在搜尋樹還沒擴充到這個規模之前，隻能擴充有限數目的節點，但是那時a算法已經找到了解路徑。
b部分：找到的第一條解路徑就是最優路徑。在最優解路徑中，任何一個節點的f值都小于或者等于最優解的f值。這是因為h是從一個節點到目标的實際花費的低估。是以，最優解路徑中任何一個節點的f值都小于任何非最優解的f值。是以，當一個節點存在于指向最優解的邊界中時，算法永遠不會選擇一個非最優的路徑（因為在每一步中，都會選擇f值最小的元素）。是以，在可能選擇一個非最優解之前，它肯定已經造訪了一個最優路徑上的所有的節點，包括每一個最優解。
應該注意到：a的可采納性不能保證每一個從邊界中選擇的中間節點位于從開始節點到目标節點的最優路徑中。可采納性使算法不必擔心環路問題，保證了第一個解是最優解。但當局部路徑最優時，它并不能保證算法不會改變主意。
看一下啟發函數是如何提高a算法的效率的，假設c是從起始節點到目标節點的最短路徑的花費。a具有可采納性的啟發資訊，91擴充集合{p:cost(p)+h(p)如果減少這些集合中第一部分的數量，提高h則會影響a的效率。
3.6.2 搜尋政策總結
https://yqfile.alicdn.com/03a29fc0a77273d15eb54a354718197585e8a4ee.png" >
圖3-9中的表格給出了各種搜尋政策的總結。
圖3-9 搜尋政策的總結
注：“終止否”意味着“如果圖（可能無窮大）中有一條到目标的路徑，該路徑上每個節點都有有限個數量的鄰居，且每條弧的花費都有正值下界，那麼這個方法能否保證搜尋終止？ ”。那些回答“yes”的搜尋政策的最壞情況下的時間複雜度與路徑長度呈指數形式增長。那些不能保證終止的算法有無限最壞情況的時間複雜度。“空間”指的是空間複雜度，它與路徑長度是“線性”或是“指數級”關系。
深度優先搜尋在空間上與造訪路徑的長度呈線性增長，但是即使有解存在，它也不能保證能找到解。寬度優先、最低花費優先以及a算法在時間和空間上都是呈指數增長，隻要解存在，即使圖是無限大的（隻要分支系數有界，弧線花費是正非平凡），它們都能保證找到解。
最低花費優先和a搜尋算法都能保證第一個找到的解是最低花費的解。