最優(yōu)化設計：第9章 啟發(fā)式搜索方法課件

第三篇 智能優(yōu)化方法

第三篇 智能優(yōu)化方法1第9章啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題求解程序的搜索器而被開發(fā)出來的。在多數情況下，待解問題可以用狀態(tài)空間加以表達，并用狀態(tài)空間或圖搜索算法求解。寬度優(yōu)先和深度優(yōu)先等圖搜索算法應用范圍有限。不過，與待解問題相關的（啟發(fā)）信息一般來說是可獲取并運用于搜索過程。這使得最佳優(yōu)先算法通常會有較好的表現。第9章啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題求2第9章啟發(fā)式搜索方法(續(xù))A*算法適于求解狀態(tài)空間中從起始節(jié)點到終止節(jié)點的最小代價路徑。它依據代價函數來選擇下一個被搜索或擴展的節(jié)點。代價函數計算出從起始節(jié)點到當前節(jié)點路徑的代價，并用啟發(fā)知識估計出到終止節(jié)點的余下路徑的代價。在滿足“可容性”的條件下，如果存在最小代價路徑，A*一定可以找到。第9章啟發(fā)式搜索方法(續(xù))A*算法適于求解狀態(tài)空間中從起3第10章霍普費爾德神經網絡

自從霍普費爾德(Hopfield)揭示了他所提出的計算網絡的運算能力以來，大量的工作被投人霍普費爾德神經網絡（簡稱霍氏網）的分析和應用。雖然最初的網絡結構有它的弱點，霍普費爾德開創(chuàng)性的成果仍舊在某種程度上打通了一條神經網絡的復興之路?；羰暇W的收斂性和穩(wěn)定性已經被證明。第10章霍普費爾德神經網絡自從霍普費爾德(Hopfi4第10章霍普費爾德神經網絡（續(xù)）加以適當改進后，霍氏網可用于求解旅行商問題等許多有約束條件的最優(yōu)化問題。將一個有約束條件的最優(yōu)化問題抽象為可由霍氏網解決的形式，需要：(1)將代價函數和約束條件轉換為霍普費爾德能量函數；(2)確定拉格朗日(Lagrange）參數。上述步驟往往是成功應用霍氏網的關鍵。第10章霍普費爾德神經網絡（續(xù)）加以適當改進后，霍氏網可5第11章模擬退火與均場退火模擬退火算法模仿了液體結晶的過程：在高溫下，粒子能量較高，可以自由運動和重新排序；隨著溫度的下降，粒子能量減弱，運動減少和粒子最終進人平衡態(tài)，固化為具有最小能量的晶體的特點。它有兩個主要操作：一個是熱靜力學操作，用于安排降溫過程；另一個是隨機張弛操作，用于搜索在特定溫度下的平衡態(tài)。模擬退火算法長處在于它具有跳離局部最優(yōu)解的能力。第11章模擬退火與均場退火模擬退火算法模仿了液體結晶的過6第11章模擬退火與均場退火（續(xù)）在給定溫度下，模擬退火算法不但進行局部搜索，而且可以在一定概率下“爬山”到代價更高的解答以防止搜索進程陷人局部最小解。應用模擬退火算法以及各種不同的統(tǒng)計特性于霍氏網，可以得到波爾茲曼、高斯、柯西等隨機機。類似于霍氏網的是，能量函數的拉格朗日參數對隨機機的性能有重要影響。第11章模擬退火與均場退火（續(xù)）在給定溫度下，模擬退火算7第11章模擬退火與均場退火（續(xù)）為了能以比隨機機中的隨機張弛操作更快的速度達到熱平衡態(tài)，神經元的值可以由它們的平均值來加以近似。這時，在每一溫度下，對神經元施加的是一個確定性的而不是隨機性的操作。與隨機機相比，這一網絡只需較少的迭代次數便可在每一溫度下達到熱平衡態(tài)。在退火過程中，這一近似方法被稱為均場退火。它在性能和計算復雜度二者之間作了一個很好的折衷。第11章模擬退火與均場退火（續(xù)）為了能以比隨機機中的隨機8第12章遺傳算法

遺傳算法是一種模擬自然選擇和遺傳的隨機搜索算法。它由賀蘭德（Holland）提出，最初用于研究自然系統(tǒng)的適應過程和設計具有自適應性能的軟件。遺傳算法的基本形式要求有一個染色體表示用來對參數空間編碼、一個適度函數用于估價所有的染色體、一組遺傳操作用于產生新的染色體和一組概率用于控制遺傳操作。遺傳算法已被非常成功地應用于解決許多最優(yōu)化問題并越來越流行。

第12章遺傳算法遺傳算法是一種模擬自然選擇和遺傳的隨機9第9章啟發(fā)式搜索方法

圖搜索算法啟發(fā)式搜索算法A*算法第9章啟發(fā)式搜索方法圖搜索算法10內容提要AI中問題求解的兩種基本方法：狀態(tài)空間法問題歸約法狀態(tài)空間的搜索方式：盲目搜索啟發(fā)式搜索與或圖的搜索方式：盲目搜索啟發(fā)式搜索博弈樹的啟發(fā)式搜索內容提要AI中問題求解的兩種基本方法：11搜索的基本概念

搜索的含義知識是解決問題的基礎，解決問題的方法一種就是算法，但對很多問題沒有有效的算法（或無現成算法），這時就可利用最一般方法即搜索來解決。根據問題的實際情況，按照一定的策略或規(guī)則，從知識庫中尋找可利用的知識，從而構造出一條使問題獲得解決的推理路線的過程，就稱為搜索。搜索包含兩層含義：一是要找到從初始事實到問題最終答案的一條推理路線，另一是找到的這條路線是時間和空間復雜度最小的求解路線。搜索的基本概念搜索的含義12搜索的類型根據搜索過程否使用啟發(fā)式信息可分為：1）盲目搜索

盲目搜索又稱無信息搜索，即在搜索過程中，只按預先規(guī)定的搜索控制策略（線路）進行搜索，而沒有任何中間信息來改變這些控制策略。即問題本身的特性對搜索控制策略沒有任何影響，這就使搜索帶有盲目性，效率不高。只用于解決比較簡單的問題。搜索的類型根據搜索過程否使用啟發(fā)式信息可分為：13搜索的類型（續(xù)）2）啟發(fā)式搜索啟發(fā)式搜索又稱有信息搜索，指搜索求解過程中，根據問題本身的特性或搜索過程中產生的一些信息來不斷改變或調整搜索的方向，使搜索朝著最有希望的方向前進，加速問題的求解，并找到最優(yōu)解。求解的效率更高，更易于求解復雜的問題。在搜索中利用知識，盡可能有效地找到問題的解。搜索的類型（續(xù)）2）啟發(fā)式搜索14圖搜索策略搜索法求解問題的基本思想:首先將問題的初始狀態(tài)(即狀態(tài)空間圖中的初始節(jié)點)當做當前狀態(tài)，選擇一適當的算符作用于當前狀態(tài)，生成一組后繼狀態(tài)（或稱后繼節(jié)點），然后檢查這組后繼狀態(tài)中有沒有目標狀態(tài)。如果有，則說明搜索成功，從初始狀態(tài)到目標狀態(tài)的一系列算符即是問題的解；若沒有，則按某種控制策略從已生成的狀態(tài)中再選一個狀態(tài)作為當前狀態(tài)，重復上述過程，直到目標狀態(tài)出現或不再有可供操作的狀態(tài)及算符為止。圖搜索策略搜索法求解問題的基本思想:15兩種基本狀態(tài)空間搜索(a)廣度優(yōu)先

如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。寬度優(yōu)先搜索又稱廣度優(yōu)先搜索，是一種盲目搜索策略。其基本思想是：從初始節(jié)點開始，逐層對節(jié)點進行依次擴展，并考慮它是否為目標節(jié)點，在對下層節(jié)點進行擴展（或搜索）前，必須完成對當前層的所有節(jié)點的擴展（或搜索）兩種基本狀態(tài)空間搜索(a)廣度優(yōu)先如果搜索16兩種基本狀態(tài)空間搜索(b)深度優(yōu)先深度優(yōu)先搜索也是一種盲目搜索策略，其基本思想是：首先擴展最新產生的（即最深）節(jié)點，即從初始節(jié)點S開始，在其后繼節(jié)點中選擇一個節(jié)點，對其進行考察，若它不是目標節(jié)點，則對該節(jié)點進行擴展，并再從它的后繼節(jié)點中選擇一個節(jié)點進行考察。依次類推，一直搜索下去，當到達某個既非目標節(jié)點又無法繼續(xù)擴展的節(jié)點時，才選擇其兄弟節(jié)點進行考察。深度界限兩種基本狀態(tài)空間搜索(b)深度優(yōu)先深度優(yōu)17深度優(yōu)先搜索（深度限制=2)深度優(yōu)先搜索（深度限制=2)18例2九宮重排問題83647■5初始狀態(tài)1238■4765目標狀態(tài)深度和寬度優(yōu)先法應用示例二例2九宮重排問題83初始狀態(tài)121923184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目標深度優(yōu)先法應用示例232328322023184765

231847652831476523184765283147652831647528314765283164752831647528371465

832147652814376528314576123784651238476512567312384765目標8234187654寬度優(yōu)先法應用示例23232832219.1 圖搜索算法圖是構造搜索空間、開展搜索過程的便利工具。定義9.1圖G=(v,E)是一個二元組，其中v={v1,v2,...,vn}是節(jié)點的有限集，E={(vi,vj)vv}是連結v中節(jié)點的連線集。

一個圖可為有向圖亦可為無向圖。有向圖的連線是有方向性的，因而從vi到vj的連線(vi,vj)與從vj到vi的連線（vj,vi)是不同的。但在無向圖中，連線（vi,vj）與（vj,vi）是相同的。圖9.1.1是有向圖G=({v1,v2,v3,v4,v5},{(v1

v2),(v1,v4),(v2,v5),(v3,v2),(v3,v4),(v4,v3)}的圖示。

9.1 圖搜索算法圖是構造搜索空間、開展搜索過程的便利工具22有向圖示例，節(jié)點定義9.2 在有向圖G=(v,E)中，若vi,vj

v且(vi,vj)E，亦即存在連線(vi,vj)，則節(jié)點vj是節(jié)點vi的子節(jié)點或稱后輩節(jié)點。同樣，vi是

vj的父節(jié)點或稱前輩節(jié)點。

有向圖示例，節(jié)點23有向圖和無向圖（a）有向圖 （b）無向圖圖9-2有向圖示與無向圖

有向圖和無向圖（a）有向圖 （b）無向圖24樹（圖）T樹（圖）T是一類除根節(jié)點外的每個節(jié)點都有且只有一個父節(jié)點的圖，如圖9-3所示的有向圖就是一個樹。x2是x5的父節(jié)點，x5是x2的子節(jié)點。沒有父節(jié)點的節(jié)點稱為根節(jié)點，如圖9-3中的x1點；沒有子節(jié)點的節(jié)點稱為葉節(jié)點，如圖9-3中的x4、x5、x7和x8。樹（圖）T樹（圖）T是一類除根節(jié)點外的每個節(jié)點都有且只有一個25樹定義9.3 樹是一類除根節(jié)點外的每個節(jié)點都只有一個父節(jié)點的圖。如果從圖9.1.1所示有向圖中去掉兩根連線(v3,v2),(v3,v4),，則所余下的就是一個樹。在搜索過程中，樹被用來記錄已展開的路徑。多數情況下，有待考察的圖是一個有向圖，通常還有唯一的一個起始節(jié)點。搜索過程不斷生成后輩節(jié)點并把它們加入圖中。這一過程被稱為節(jié)點展開。搜索持續(xù)進行，直到它找到屬于終止節(jié)點集的任一節(jié)點。樹定義9.3 樹是一類除根節(jié)點外的每個節(jié)點都只有一個父節(jié)點26回溯以圖的形式記錄搜索過程的一個重要原因是為了便于回溯?；厮菔沟盟阉鬟^程得以廢棄任何失敗的路徑；回溯可以使搜索過程得以放棄較差或錯誤的搜索路徑，返回某一搜索過的節(jié)點，從而重新開拓一條新的路徑。

回溯以圖的形式記錄搜索過程的一個重要原因是為了便于回溯。回溯27圖轉化成樹

(a)有向圖 (b)樹圖轉化成樹(a)有向圖 (28路徑代價一個路徑是否有助于求解通常決定于代價函數。它對一個節(jié)點的評價基于至今已經花費的代價和其通往目標節(jié)點的可能性。代價函數可與圖中的連線一起被用來表達搜索過程中從一個節(jié)點到另一個節(jié)點的代價。

定義9.4 cost(vi,vj）是節(jié)點vi與節(jié)點vj

間連線的代價。定義9.5節(jié)點序列vlv2...vk是從節(jié)點v1到節(jié)點vk的長度為k的路徑。其中對于j=1,...,k-1，有vj+1為vj的子節(jié)點。

路徑代價一個路徑是否有助于求解通常決定于代價函數。它對一個節(jié)29代價函數一條路徑的代價就是從起始節(jié)點經由如下公式列出的中間節(jié)點到達目標節(jié)點的路徑上所有連線代價之和，即

要評價節(jié)點n，可以建立一個代價函數f(n)，并使其包含兩個組成部分：其一是從起始節(jié)點到n的實際代價；其二是從n到終止節(jié)點的代價估值。下面給出的基于f(n)的圖搜索過程Graph-Search試圖找到一個從起始節(jié)點到終止節(jié)點的最小代價路徑。

代價函數一條路徑的代價就是從起始節(jié)點經由如下公式列出的中間節(jié)30圖搜索步驟在表9-1中給出幾種不同的搜索算法。可以簡單劃分為無信息任意路徑算法（包括前面提到的深度優(yōu)先和廣度優(yōu)先搜索）、有信息任意路徑算法、無信息優(yōu)化算法和有信息優(yōu)化算法。表9-1幾種不同的搜索算法序號名稱分類操作1深度優(yōu)先無信息任意路徑算法對整個樹全面搜索直至達到目標節(jié)點2廣度優(yōu)先3最好優(yōu)先有信息任意路徑算法利用最好狀態(tài)方法啟發(fā)式搜索估計到目標節(jié)點的距離4均勻價值法無信息優(yōu)化算法利用路徑測算尋找最短路徑5A*算法有信息優(yōu)化算法利用路徑和啟發(fā)式函數尋找最短路徑圖搜索步驟在表9-1中給出幾種不同的搜索算法?？梢院唵蝿澐譃?1Graph-Search算法

輸入：起始節(jié)點和一組終止節(jié)點{ti}。輸出：圖G和樹T。(1)初始化。以起始節(jié)點s：構造圖G和集合OPEN（未擴展的節(jié)點，或待展開的節(jié)點），G{s}，OPEN{s}，且令集合CLOSED（已經擴展或已經展開的節(jié)點），其初始化為空集。(2) LOOP:若OPEN為空集，算法以失敗結束。(3)從OPEN中取出第一個節(jié)點n，并使OPENOPEN-{n},CLOSEDCLOSED{n}，即把第一個節(jié)點從OPEN中移出放進CLOSED表中。Graph-Search算法輸入：起始節(jié)點和一組終止節(jié)點{32Graph-Search算法（續(xù)）(4)若n{ti}為目標節(jié)點，算法以成功結束，此解是沿著指針從n到s這條路徑而得到的。(5) 展開節(jié)點n，并令M為n的子節(jié)點且不是其前輩節(jié)點的節(jié)點集。將M的這些成員作為n的后繼節(jié)點加入圖G中。(6) 將M中既不在OPEN中也不在CLOSED中的節(jié)點（即那些未曾在G中出現過的節(jié)點）放入OPEN。(7) 給每個M中既不在OPEN中也不在CLOSED中的節(jié)點設置一個指向其父節(jié)點的逆向指針。Graph-Search算法（續(xù)）(4)若n{ti}33Graph-Search算法（續(xù)）(8) 調整M中那些同時也在OPEN或CLOSED中的節(jié)點的逆向指針。(9) 調整M和CLOSED中每個節(jié)點的后繼節(jié)點的逆向指針。(10)依據評價函數值（探試值）重新安排OPEN中的節(jié)點。(11)回到LOOP。CLOSED存放已擴展節(jié)點；OPEN存放未擴展節(jié)點，待擴展節(jié)點Graph-Search算法（續(xù)）(8) 調整M中那些同時34一般搜索過程框圖一般搜索過程框圖35Graph-Search算法（續(xù)）上述算法中所用的逆向指針就構成了解樹T，而回溯則是通過將節(jié)點分別放入OPEN和CLOSED兩集合中而實現的。如果一個節(jié)點尚未被展開，亦即它的子節(jié)點還未被生成，則將它放入OPEN；否則，一個已被展開的節(jié)點將被放入CLOSED。圖9-6示范出一個執(zhí)行Graph-Search算法歷經3次循環(huán)的例子。

Graph-Search算法（續(xù)）上述算法中所用的逆向指針36搜索圖圖9-6搜索圖算例搜索圖圖9-6搜索圖算例37Graph-Search算法（續(xù)）循環(huán)1

步驟(1)：最初OPEN={s}，CLOSED為空集。見圖9-6(a)。

步驟(3)：s被展開，OPEN為空集，CLOSED={s}。

步驟(5)：假定展開s生成3個子節(jié)點，M={a,b,c}。見圖9-6(b)。

步驟(6)：OPEN={a,b,c}。

步驟(7)：設置逆向指針。見圖9-6(c)Graph-Search算法（續(xù)）循環(huán)1步驟(1)：38Graph-Search算法（續(xù)）循環(huán)2步驟(3)：假定a被選來擴展;OPEN={b,c},CLOSED={s,a}。

步驟(5)：假定擴展a生成三個子節(jié)點，M={b,d,e}，見圖9.1.3(d)。步驟(6)：OPEN={b,c,d,e}。

步驟(7)：設置逆向指針。見圖9.1.3(e)。注意b在此之前已有逆向指針指向，這種情況下不作調整。

Graph-Search算法（續(xù)）循環(huán)2步驟(3)：假定39Graph-Search算法（續(xù)）循環(huán)3步驟(3)：假定b被選來擴展,OPEN={c,d,e}，CLOSED={s,a,b}。

步驟(5)：假定擴展b生成一個子節(jié)點，M={e}。見圖9.1.3(f）。

步驟(6)：OPEN={c,d,e}。

步驟(7)：設置逆向指針。見圖9.1.3(g).注意e在此之前已有反向指針指向a，這種情況下要調整為指向b。

Graph-Search算法（續(xù)）循環(huán)3步驟(3)：假定40啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題求解程序的搜索器而被開發(fā)出來的。在多數情況下，待解問題可以用狀態(tài)空間加以表達，并用狀態(tài)空間或圖搜索算法求解。

寬度優(yōu)先和深度優(yōu)先等圖搜索算法的應用范圍有限。不過，與待解問題相關的（啟發(fā)）信息一般來說是可獲取并運用于搜索過程。

啟發(fā)式搜索要用到問題自身的某些特性信息，以指導搜索朝著有希望的方向前進。避免了盲目搜索，搜索效率高。啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題41啟發(fā)式搜索方法啟發(fā)式搜索方法依靠任務無關信息來簡化搜索進程。在很多情況下，問題求解可視為系統(tǒng)化地構造或查找解答的過程。因此，在人工智能領域中，開發(fā)出了用于計算機問題求解的各種不同搜索算法。盡管在某些情況下并非十分有效，迷宮、定理證明、國際象棋等問題都可以由計算機程序給出解答。一般來說，搜索過程包括檢查搜索空間、估價可能有解的各種不同路徑、記錄已經搜索到的各個路徑。

啟發(fā)式搜索方法啟發(fā)式搜索方法依靠任務無關信息來簡化搜索進程。42啟發(fā)式搜索方法為簡化搜索并減少搜索過程中時有出現的大量可選路徑，從與待解問題有關的信息中所得到的啟發(fā)知識或“經驗法則”可用來確定搜索的方向。精心選擇的啟發(fā)信息可在很大程度上加大找出解答的機會，且在同時減少求解所需的時間。這一章統(tǒng)觀啟發(fā)式搜索方法并著重介紹A*算法。

啟發(fā)式搜索方法為簡化搜索并減少搜索過程中時有出現的大量可選路439.2 啟發(fā)函數

啟發(fā)式方法，或更一般地，經驗規(guī)則，是指引搜索方向以有效求取到達目標節(jié)點路徑的原則或規(guī)則。一般來說，所用的啟發(fā)知識在很大程度上取決于待解問題和節(jié)點表示。例如，可用于求解前述s數碼問題的一個很好的啟發(fā)信息就是不在最終位置上的離家將牌個數，記為Misplaced(n).對于圖9.1所示初始將牌布局，將牌4,5,6離家，因而Misplaced(n)=3。8數碼問題

9.2 啟發(fā)函數啟發(fā)式方法，或更一般地，經驗規(guī)則，是指引搜449.2 啟發(fā)函數（續(xù)）在圖搜索中，啟發(fā)知識的數值表示為從當前節(jié)點到目標節(jié)點的代價。它構成了如下代價函數的一部分：f(n)=g(n)+h(n) (9.2.1）其中，g(n)是從起始節(jié)點到當前節(jié)點n代價的最小估值，h(n)為從當前節(jié)點n到終止節(jié)點代價的估值。顯然，g(n)可用至今已被展開的從起始節(jié)點到當前節(jié)點元的所用路徑中的最小代價來近似。9.2 啟發(fā)函數（續(xù)）在圖搜索中，啟發(fā)知識的數值表示為從當459.2 啟發(fā)函數（續(xù)）然而，從n到任一目標節(jié)點的路徑都是未知的。為此，無法精確確定h(n)而只能對其加以估算。在此規(guī)定目標節(jié)點的啟發(fā)函數值為零，即對于n{ti}，h(n)=0。在無法獲取啟發(fā)知識亦即對于所有節(jié)點n都有著h(n)=0的情況下，啟發(fā)式搜索退化為寬度優(yōu)先搜索。

當其啟發(fā)函數具有f(n)=g(n)+h(n)這一特殊形式時Graph-Search算法成為A算法。

9.2 啟發(fā)函數（續(xù)）然而，從n到任一目標節(jié)點的路徑468數碼問題

布局n1

n2終止返回8數碼問題479.2 啟發(fā)函數（續(xù)）A算法輸入：起始節(jié)點s和一組終止節(jié)點{ti}。輸出：圖G和樹T。(1) 初始化。以起始節(jié)點s構造圖G和集合OPEN，G{s}，OPEN{s}，且令集合CLOSE為空集。(2) LOOP：若OPEN為空集，算法以失敗結束。(3) 從OPEN中取出具有最小f(n)值的節(jié)點n，并使OPENOPEN－{n},CLOSEDCLOSED{n}。(4) 若n任{ti}，算法以成功結束。(5) 展開n且令M為n的子節(jié)點且不為其前輩節(jié)點的節(jié)點集。將M加入G。9.2 啟發(fā)函數（續(xù)）A算法輸入：起始節(jié)點s和一489.2 啟發(fā)函數（續(xù)）A算法續(xù)

(6) 對每一個節(jié)點mM：①如果mOPEN且mCLOSED，將m放入OPEN。估計h(m)并計算f(m)=g(m)+h(m)，其中g(m)=g(n)+cost(n,m)。②如果mOPEN或mCLOSED，將其逆向指針調整到給出最小g(m)值的路徑。③如果m的逆向指針被調整且m在CLOSED中，將其重新加入OPEN。(7) 回到LOOP9.2 啟發(fā)函數（續(xù)）A算法續(xù)(6) 對每一個節(jié)499.2 啟發(fā)函數（續(xù)）A算法續(xù)

函數g(n)，h(n)和f(n)在最小代價路徑上的值可基于下列定義得到。定義9.6g*(n)是從s到n的所有路徑中的最小代價。定義9.7h*(n)是從n到一個目標節(jié)點的所有路徑中的最小代價。由g*(n)和h*(n)的定義可得f*(n)=g*(n)+h*(n) (9.2.2)其中f*(n)是從起始節(jié)點經過節(jié)點n到達一個目標節(jié)點的所有路徑中的最小代價。

9.2 啟發(fā)函數（續(xù)）A算法續(xù)函數g(n)，h(n509.2 啟發(fā)函數（續(xù)）A算法續(xù)下面用圖9.2.1給出的實例示范g*和h*的計算方法。

9.2 啟發(fā)函數（續(xù)）A算法續(xù)下面用圖9.2.1給出的實519.2 啟發(fā)函數（續(xù)）A算法續(xù)有向圖G=(v,E)中，v={a,b,c,d,e,i,j,k,l}E={(s,a),(s,b),(s,c),(a,d),(b,d),(b,e),(c,e),(d,i),(d,j),(d,k),(e,j),(e,k),(e,i)}連線的代價由函數cost給出，且起始節(jié)點為s，目標節(jié)點為{j,k}。計算g*，h*和f*的過程可歸納如下：(1)從起始節(jié)點開始計算g*。顯然，g*(s)=0。(2）對其它任一節(jié)點n，計算從s到n的每條路徑的代價，而g*(n)是其中的最小值。①從s到a只有一條路徑，所以g*(a)=g(s-a)=cost(s,a)=19.2 啟發(fā)函數（續(xù)）A算法續(xù)有向圖G=(v,E)中529.2 啟發(fā)函數（續(xù)）A算法續(xù)

②從s到d存在兩條路徑，即sad和sbd。g(sad)=cost(s,a)+cost(a,d)=1+4=5而g(sad)=cost(s,b)+cost(b,d)=2+2=4，所以g*(d)=min{5,4}=4。 ③從s到j存在4條路徑，它們的代價分別為g(sadj)=1+4+3=8g(sbdj)=2+2+3=7g(sbej)=2+1+1=4g(scej)=3+3+1=7因此，g*(j)=min{8,7,4,7}=49.2 啟發(fā)函數（續(xù)）A算法續(xù)②從s到d存在兩條路539.2 啟發(fā)函數（續(xù)）A算法續(xù)(3)從目標節(jié)點開始計算h*，可得h*(j)=h*(k)=0(4) 對其它任一節(jié)點n，計算從n到j或k的每條路徑的代價，而h*(n)是其中的最小值。例如，由b通往終止節(jié)點的路徑及其代價可為①bdj，h(bdj)=cost(b,d）+cost(d,j)=2+3=5；②bdk，h(bdk)=cost(b,d)+cost(d,k)=2+1=3；③bej，h(bej)=cost(b,e)+cost(e,j)=1+1=2；④bek，h(bek)=cost(b,e)+cost(e,k)=1+3=4。因此，h*(d)=min{5,3,2,4}=2

一旦得到g*(n)和h*(n)，f*(n)可由f*(n)=g*(n)+h*(n)求得。

9.2 啟發(fā)函數（續(xù)）A算法續(xù)(3)從目標節(jié)點開始計549.2 啟發(fā)函數（續(xù)）A算法續(xù)對于圖9.7所示有向圖，sbej是從s到目標節(jié)點之一j的最小代價路徑，且代價為4。值得注意的是，在最小代價路徑上的每個節(jié)點的f*值都等于最小代價。當然，在實際求解過程中，圖的結構在展開它之前是未知的。因此，g*只能基于至今已被展開的路徑計算，而h*則根本無法得知。

9.2 啟發(fā)函數（續(xù)）A算法續(xù)對于圖9.7所示有向圖55A*算法

A*算法適于求解狀態(tài)空間中從起始節(jié)點到終止節(jié)點的最小代價路徑。它依據代價函數來選擇下一個被搜索或擴展的節(jié)點。代價函數計算出從起始節(jié)點到當前節(jié)點路徑的代價，并用啟發(fā)知識估計出到終止節(jié)點的余下路徑的代價。在滿足“可容性”的條件下，如果存在最小代價路徑，A*一定可以找到。A*算法A*算法適于求解狀態(tài)空間中從56例：5城市旅行商問題例：5城市旅行商問題579.3 A*搜索算法

定義9.8 A*算法在啟發(fā)函數h(n)滿足h(n)h*(n)，對所有節(jié)點n 的條件下被稱為A*算法。這也就是說A*算法的啟發(fā)函數值永遠低估了實際最小代價。A*算法的重要意義在于，當A*算法結束時，它一定已經找到了一條從起始節(jié)點到目標節(jié)點的最小代價路徑。結論9.1若存在從起始節(jié)點到目標節(jié)點的路徑，A*算法一定會終止。結論9.2 A*算法是可容（許）的。也就是說，如果存在一條從起始節(jié)點到目標節(jié)點的路徑,A*算法以發(fā)現最優(yōu)解而終止。9.3 A*搜索算法定義9.8 A*算法在啟發(fā)函數h589.3 A*搜索算法（續(xù)）

結論9.1表明，如果存在從起始節(jié)點到目標節(jié)點的解答路徑，A*算法一定能找到它。結論9.2更進一步指出，A*算法找到的解答路徑一定具有從起始節(jié)點到目標節(jié)點的最小代價。作為一個例子，在這里用A*算法解決以圖9.3.1中起始節(jié)點s和終止節(jié)點g所給出的8數碼問題。圖9.3.18數碼問題的起始布局和目標布局

9.3 A*搜索算法（續(xù)）結論9.1表明，如果存在從起始節(jié)599.3 A*搜索算法（續(xù)）

在從一個布局轉換為另一個布局時，付出的代價是一步移動。要找出的是從s到g的最少移動步數走法。正如在前一節(jié)中所討論過的，以Misplaced(n)亦即不在目標布局給出的位置上的離家將牌數為啟發(fā)函數。圖9.3.2示出了A*算法展開的節(jié)點及相應的f(n)計算值。在展開了6個節(jié)點后，到達終止節(jié)點。9.3 A*搜索算法（續(xù)）在從一個布局轉換為另一個布局時，60[九宮重排問題]83647■5初始狀態(tài)1238■4765目標狀態(tài)成本函數：

C(X)：從初始格局經過X結點的格局到達目標格局所需的棋步。成本估計函數：

?(X)=?(X)+h(X)其中，?(X)：表示結點X的成本的估計值；h(X)：結點X的格局與目標格局相比，位置不符合的將牌數目；

?(X)：根(起始結點)至X的路徑長度。應用舉例一[九宮重排問題]83初始狀態(tài)123612831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■65■2318476523■184765123■847651238■4765123784■650+41+51+31+52+32+32+43+3

3+43+2

3+44+15+05+2目標使用?(X)=?(X)+h(X)的啟發(fā)搜索2832832629.3 A*搜索算法（續(xù)）

雖然A*算法保證可以發(fā)現最優(yōu)解，但它的性能與啟發(fā)函數的選擇有很大關系。如果啟發(fā)函數嚴重低估實際的h*，算法退化為寬度優(yōu)先搜索。如果問題規(guī)模較大，對用于保存搜索圖和解樹的資源要求也就相當高。

9.3 A*搜索算法（續(xù)）63最優(yōu)化設計：第9章啟發(fā)式搜索方法課件64最優(yōu)化設計：第9章啟發(fā)式搜索方法課件65最優(yōu)化設計：第9章啟發(fā)式搜索方法課件66最優(yōu)化設計：第9章啟發(fā)式搜索方法課件67最優(yōu)化設計：第9章啟發(fā)式搜索方法課件68最優(yōu)化設計：第9章啟發(fā)式搜索方法課件69致謝部分圖片來源于：華南師范大學計算機系陳衛(wèi)東老師2003年10月的AI搜索策略課件，在此表示忠心感謝！致謝部分圖片來源于：70第三篇 智能優(yōu)化方法

第三篇 智能優(yōu)化方法71第9章啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題求解程序的搜索器而被開發(fā)出來的。在多數情況下，待解問題可以用狀態(tài)空間加以表達，并用狀態(tài)空間或圖搜索算法求解。寬度優(yōu)先和深度優(yōu)先等圖搜索算法應用范圍有限。不過，與待解問題相關的（啟發(fā)）信息一般來說是可獲取并運用于搜索過程。這使得最佳優(yōu)先算法通常會有較好的表現。第9章啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題求72第9章啟發(fā)式搜索方法(續(xù))A*算法適于求解狀態(tài)空間中從起始節(jié)點到終止節(jié)點的最小代價路徑。它依據代價函數來選擇下一個被搜索或擴展的節(jié)點。代價函數計算出從起始節(jié)點到當前節(jié)點路徑的代價，并用啟發(fā)知識估計出到終止節(jié)點的余下路徑的代價。在滿足“可容性”的條件下，如果存在最小代價路徑，A*一定可以找到。第9章啟發(fā)式搜索方法(續(xù))A*算法適于求解狀態(tài)空間中從起73第10章霍普費爾德神經網絡

自從霍普費爾德(Hopfield)揭示了他所提出的計算網絡的運算能力以來，大量的工作被投人霍普費爾德神經網絡（簡稱霍氏網）的分析和應用。雖然最初的網絡結構有它的弱點，霍普費爾德開創(chuàng)性的成果仍舊在某種程度上打通了一條神經網絡的復興之路?；羰暇W的收斂性和穩(wěn)定性已經被證明。第10章霍普費爾德神經網絡自從霍普費爾德(Hopfi74第10章霍普費爾德神經網絡（續(xù)）加以適當改進后，霍氏網可用于求解旅行商問題等許多有約束條件的最優(yōu)化問題。將一個有約束條件的最優(yōu)化問題抽象為可由霍氏網解決的形式，需要：(1)將代價函數和約束條件轉換為霍普費爾德能量函數；(2)確定拉格朗日(Lagrange）參數。上述步驟往往是成功應用霍氏網的關鍵。第10章霍普費爾德神經網絡（續(xù)）加以適當改進后，霍氏網可75第11章模擬退火與均場退火模擬退火算法模仿了液體結晶的過程：在高溫下，粒子能量較高，可以自由運動和重新排序；隨著溫度的下降，粒子能量減弱，運動減少和粒子最終進人平衡態(tài)，固化為具有最小能量的晶體的特點。它有兩個主要操作：一個是熱靜力學操作，用于安排降溫過程；另一個是隨機張弛操作，用于搜索在特定溫度下的平衡態(tài)。模擬退火算法長處在于它具有跳離局部最優(yōu)解的能力。第11章模擬退火與均場退火模擬退火算法模仿了液體結晶的過76第11章模擬退火與均場退火（續(xù)）在給定溫度下，模擬退火算法不但進行局部搜索，而且可以在一定概率下“爬山”到代價更高的解答以防止搜索進程陷人局部最小解。應用模擬退火算法以及各種不同的統(tǒng)計特性于霍氏網，可以得到波爾茲曼、高斯、柯西等隨機機。類似于霍氏網的是，能量函數的拉格朗日參數對隨機機的性能有重要影響。第11章模擬退火與均場退火（續(xù)）在給定溫度下，模擬退火算77第11章模擬退火與均場退火（續(xù)）為了能以比隨機機中的隨機張弛操作更快的速度達到熱平衡態(tài)，神經元的值可以由它們的平均值來加以近似。這時，在每一溫度下，對神經元施加的是一個確定性的而不是隨機性的操作。與隨機機相比，這一網絡只需較少的迭代次數便可在每一溫度下達到熱平衡態(tài)。在退火過程中，這一近似方法被稱為均場退火。它在性能和計算復雜度二者之間作了一個很好的折衷。第11章模擬退火與均場退火（續(xù)）為了能以比隨機機中的隨機78第12章遺傳算法

遺傳算法是一種模擬自然選擇和遺傳的隨機搜索算法。它由賀蘭德（Holland）提出，最初用于研究自然系統(tǒng)的適應過程和設計具有自適應性能的軟件。遺傳算法的基本形式要求有一個染色體表示用來對參數空間編碼、一個適度函數用于估價所有的染色體、一組遺傳操作用于產生新的染色體和一組概率用于控制遺傳操作。遺傳算法已被非常成功地應用于解決許多最優(yōu)化問題并越來越流行。

第12章遺傳算法遺傳算法是一種模擬自然選擇和遺傳的隨機79第9章啟發(fā)式搜索方法

圖搜索算法啟發(fā)式搜索算法A*算法第9章啟發(fā)式搜索方法圖搜索算法80內容提要AI中問題求解的兩種基本方法：狀態(tài)空間法問題歸約法狀態(tài)空間的搜索方式：盲目搜索啟發(fā)式搜索與或圖的搜索方式：盲目搜索啟發(fā)式搜索博弈樹的啟發(fā)式搜索內容提要AI中問題求解的兩種基本方法：81搜索的基本概念

搜索的含義知識是解決問題的基礎，解決問題的方法一種就是算法，但對很多問題沒有有效的算法（或無現成算法），這時就可利用最一般方法即搜索來解決。根據問題的實際情況，按照一定的策略或規(guī)則，從知識庫中尋找可利用的知識，從而構造出一條使問題獲得解決的推理路線的過程，就稱為搜索。搜索包含兩層含義：一是要找到從初始事實到問題最終答案的一條推理路線，另一是找到的這條路線是時間和空間復雜度最小的求解路線。搜索的基本概念搜索的含義82搜索的類型根據搜索過程否使用啟發(fā)式信息可分為：1）盲目搜索

盲目搜索又稱無信息搜索，即在搜索過程中，只按預先規(guī)定的搜索控制策略（線路）進行搜索，而沒有任何中間信息來改變這些控制策略。即問題本身的特性對搜索控制策略沒有任何影響，這就使搜索帶有盲目性，效率不高。只用于解決比較簡單的問題。搜索的類型根據搜索過程否使用啟發(fā)式信息可分為：83搜索的類型（續(xù)）2）啟發(fā)式搜索啟發(fā)式搜索又稱有信息搜索，指搜索求解過程中，根據問題本身的特性或搜索過程中產生的一些信息來不斷改變或調整搜索的方向，使搜索朝著最有希望的方向前進，加速問題的求解，并找到最優(yōu)解。求解的效率更高，更易于求解復雜的問題。在搜索中利用知識，盡可能有效地找到問題的解。搜索的類型（續(xù)）2）啟發(fā)式搜索84圖搜索策略搜索法求解問題的基本思想:首先將問題的初始狀態(tài)(即狀態(tài)空間圖中的初始節(jié)點)當做當前狀態(tài)，選擇一適當的算符作用于當前狀態(tài)，生成一組后繼狀態(tài)（或稱后繼節(jié)點），然后檢查這組后繼狀態(tài)中有沒有目標狀態(tài)。如果有，則說明搜索成功，從初始狀態(tài)到目標狀態(tài)的一系列算符即是問題的解；若沒有，則按某種控制策略從已生成的狀態(tài)中再選一個狀態(tài)作為當前狀態(tài)，重復上述過程，直到目標狀態(tài)出現或不再有可供操作的狀態(tài)及算符為止。圖搜索策略搜索法求解問題的基本思想:85兩種基本狀態(tài)空間搜索(a)廣度優(yōu)先

如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。寬度優(yōu)先搜索又稱廣度優(yōu)先搜索，是一種盲目搜索策略。其基本思想是：從初始節(jié)點開始，逐層對節(jié)點進行依次擴展，并考慮它是否為目標節(jié)點，在對下層節(jié)點進行擴展（或搜索）前，必須完成對當前層的所有節(jié)點的擴展（或搜索）兩種基本狀態(tài)空間搜索(a)廣度優(yōu)先如果搜索86兩種基本狀態(tài)空間搜索(b)深度優(yōu)先深度優(yōu)先搜索也是一種盲目搜索策略，其基本思想是：首先擴展最新產生的（即最深）節(jié)點，即從初始節(jié)點S開始，在其后繼節(jié)點中選擇一個節(jié)點，對其進行考察，若它不是目標節(jié)點，則對該節(jié)點進行擴展，并再從它的后繼節(jié)點中選擇一個節(jié)點進行考察。依次類推，一直搜索下去，當到達某個既非目標節(jié)點又無法繼續(xù)擴展的節(jié)點時，才選擇其兄弟節(jié)點進行考察。深度界限兩種基本狀態(tài)空間搜索(b)深度優(yōu)先深度優(yōu)87深度優(yōu)先搜索（深度限制=2)深度優(yōu)先搜索（深度限制=2)88例2九宮重排問題83647■5初始狀態(tài)1238■4765目標狀態(tài)深度和寬度優(yōu)先法應用示例二例2九宮重排問題83初始狀態(tài)128923184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abd12384765目標深度優(yōu)先法應用示例232328329023184765

231847652831476523184765283147652831647528314765283164752831647528371465

832147652814376528314576123784651238476512567312384765目標8234187654寬度優(yōu)先法應用示例23232832919.1 圖搜索算法圖是構造搜索空間、開展搜索過程的便利工具。定義9.1圖G=(v,E)是一個二元組，其中v={v1,v2,...,vn}是節(jié)點的有限集，E={(vi,vj)vv}是連結v中節(jié)點的連線集。

一個圖可為有向圖亦可為無向圖。有向圖的連線是有方向性的，因而從vi到vj的連線(vi,vj)與從vj到vi的連線（vj,vi)是不同的。但在無向圖中，連線（vi,vj）與（vj,vi）是相同的。圖9.1.1是有向圖G=({v1,v2,v3,v4,v5},{(v1

v2),(v1,v4),(v2,v5),(v3,v2),(v3,v4),(v4,v3)}的圖示。

9.1 圖搜索算法圖是構造搜索空間、開展搜索過程的便利工具92有向圖示例，節(jié)點定義9.2 在有向圖G=(v,E)中，若vi,vj

v且(vi,vj)E，亦即存在連線(vi,vj)，則節(jié)點vj是節(jié)點vi的子節(jié)點或稱后輩節(jié)點。同樣，vi是

vj的父節(jié)點或稱前輩節(jié)點。

有向圖示例，節(jié)點93有向圖和無向圖（a）有向圖 （b）無向圖圖9-2有向圖示與無向圖

有向圖和無向圖（a）有向圖 （b）無向圖94樹（圖）T樹（圖）T是一類除根節(jié)點外的每個節(jié)點都有且只有一個父節(jié)點的圖，如圖9-3所示的有向圖就是一個樹。x2是x5的父節(jié)點，x5是x2的子節(jié)點。沒有父節(jié)點的節(jié)點稱為根節(jié)點，如圖9-3中的x1點；沒有子節(jié)點的節(jié)點稱為葉節(jié)點，如圖9-3中的x4、x5、x7和x8。樹（圖）T樹（圖）T是一類除根節(jié)點外的每個節(jié)點都有且只有一個95樹定義9.3 樹是一類除根節(jié)點外的每個節(jié)點都只有一個父節(jié)點的圖。如果從圖9.1.1所示有向圖中去掉兩根連線(v3,v2),(v3,v4),，則所余下的就是一個樹。在搜索過程中，樹被用來記錄已展開的路徑。多數情況下，有待考察的圖是一個有向圖，通常還有唯一的一個起始節(jié)點。搜索過程不斷生成后輩節(jié)點并把它們加入圖中。這一過程被稱為節(jié)點展開。搜索持續(xù)進行，直到它找到屬于終止節(jié)點集的任一節(jié)點。樹定義9.3 樹是一類除根節(jié)點外的每個節(jié)點都只有一個父節(jié)點96回溯以圖的形式記錄搜索過程的一個重要原因是為了便于回溯?；厮菔沟盟阉鬟^程得以廢棄任何失敗的路徑；回溯可以使搜索過程得以放棄較差或錯誤的搜索路徑，返回某一搜索過的節(jié)點，從而重新開拓一條新的路徑。

回溯以圖的形式記錄搜索過程的一個重要原因是為了便于回溯?；厮?7圖轉化成樹

(a)有向圖 (b)樹圖轉化成樹(a)有向圖 (98路徑代價一個路徑是否有助于求解通常決定于代價函數。它對一個節(jié)點的評價基于至今已經花費的代價和其通往目標節(jié)點的可能性。代價函數可與圖中的連線一起被用來表達搜索過程中從一個節(jié)點到另一個節(jié)點的代價。

定義9.4 cost(vi,vj）是節(jié)點vi與節(jié)點vj

間連線的代價。定義9.5節(jié)點序列vlv2...vk是從節(jié)點v1到節(jié)點vk的長度為k的路徑。其中對于j=1,...,k-1，有vj+1為vj的子節(jié)點。

路徑代價一個路徑是否有助于求解通常決定于代價函數。它對一個節(jié)99代價函數一條路徑的代價就是從起始節(jié)點經由如下公式列出的中間節(jié)點到達目標節(jié)點的路徑上所有連線代價之和，即

要評價節(jié)點n，可以建立一個代價函數f(n)，并使其包含兩個組成部分：其一是從起始節(jié)點到n的實際代價；其二是從n到終止節(jié)點的代價估值。下面給出的基于f(n)的圖搜索過程Graph-Search試圖找到一個從起始節(jié)點到終止節(jié)點的最小代價路徑。

代價函數一條路徑的代價就是從起始節(jié)點經由如下公式列出的中間節(jié)100圖搜索步驟在表9-1中給出幾種不同的搜索算法。可以簡單劃分為無信息任意路徑算法（包括前面提到的深度優(yōu)先和廣度優(yōu)先搜索）、有信息任意路徑算法、無信息優(yōu)化算法和有信息優(yōu)化算法。表9-1幾種不同的搜索算法序號名稱分類操作1深度優(yōu)先無信息任意路徑算法對整個樹全面搜索直至達到目標節(jié)點2廣度優(yōu)先3最好優(yōu)先有信息任意路徑算法利用最好狀態(tài)方法啟發(fā)式搜索估計到目標節(jié)點的距離4均勻價值法無信息優(yōu)化算法利用路徑測算尋找最短路徑5A*算法有信息優(yōu)化算法利用路徑和啟發(fā)式函數尋找最短路徑圖搜索步驟在表9-1中給出幾種不同的搜索算法?？梢院唵蝿澐譃?01Graph-Search算法

輸入：起始節(jié)點和一組終止節(jié)點{ti}。輸出：圖G和樹T。(1)初始化。以起始節(jié)點s：構造圖G和集合OPEN（未擴展的節(jié)點，或待展開的節(jié)點），G{s}，OPEN{s}，且令集合CLOSED（已經擴展或已經展開的節(jié)點），其初始化為空集。(2) LOOP:若OPEN為空集，算法以失敗結束。(3)從OPEN中取出第一個節(jié)點n，并使OPENOPEN-{n},CLOSEDCLOSED{n}，即把第一個節(jié)點從OPEN中移出放進CLOSED表中。Graph-Search算法輸入：起始節(jié)點和一組終止節(jié)點{102Graph-Search算法（續(xù)）(4)若n{ti}為目標節(jié)點，算法以成功結束，此解是沿著指針從n到s這條路徑而得到的。(5) 展開節(jié)點n，并令M為n的子節(jié)點且不是其前輩節(jié)點的節(jié)點集。將M的這些成員作為n的后繼節(jié)點加入圖G中。(6) 將M中既不在OPEN中也不在CLOSED中的節(jié)點（即那些未曾在G中出現過的節(jié)點）放入OPEN。(7) 給每個M中既不在OPEN中也不在CLOSED中的節(jié)點設置一個指向其父節(jié)點的逆向指針。Graph-Search算法（續(xù)）(4)若n{ti}103Graph-Search算法（續(xù)）(8) 調整M中那些同時也在OPEN或CLOSED中的節(jié)點的逆向指針。(9) 調整M和CLOSED中每個節(jié)點的后繼節(jié)點的逆向指針。(10)依據評價函數值（探試值）重新安排OPEN中的節(jié)點。(11)回到LOOP。CLOSED存放已擴展節(jié)點；OPEN存放未擴展節(jié)點，待擴展節(jié)點Graph-Search算法（續(xù)）(8) 調整M中那些同時104一般搜索過程框圖一般搜索過程框圖105Graph-Search算法（續(xù)）上述算法中所用的逆向指針就構成了解樹T，而回溯則是通過將節(jié)點分別放入OPEN和CLOSED兩集合中而實現的。如果一個節(jié)點尚未被展開，亦即它的子節(jié)點還未被生成，則將它放入OPEN；否則，一個已被展開的節(jié)點將被放入CLOSED。圖9-6示范出一個執(zhí)行Graph-Search算法歷經3次循環(huán)的例子。

Graph-Search算法（續(xù)）上述算法中所用的逆向指針106搜索圖圖9-6搜索圖算例搜索圖圖9-6搜索圖算例107Graph-Search算法（續(xù)）循環(huán)1

步驟(1)：最初OPEN={s}，CLOSED為空集。見圖9-6(a)。

步驟(3)：s被展開，OPEN為空集，CLOSED={s}。

步驟(5)：假定展開s生成3個子節(jié)點，M={a,b,c}。見圖9-6(b)。

步驟(6)：OPEN={a,b,c}。

步驟(7)：設置逆向指針。見圖9-6(c)Graph-Search算法（續(xù)）循環(huán)1步驟(1)：108Graph-Search算法（續(xù)）循環(huán)2步驟(3)：假定a被選來擴展;OPEN={b,c},CLOSED={s,a}。

步驟(5)：假定擴展a生成三個子節(jié)點，M={b,d,e}，見圖9.1.3(d)。步驟(6)：OPEN={b,c,d,e}。

步驟(7)：設置逆向指針。見圖9.1.3(e)。注意b在此之前已有逆向指針指向，這種情況下不作調整。

Graph-Search算法（續(xù)）循環(huán)2步驟(3)：假定109Graph-Search算法（續(xù)）循環(huán)3步驟(3)：假定b被選來擴展,OPEN={c,d,e}，CLOSED={s,a,b}。

步驟(5)：假定擴展b生成一個子節(jié)點，M={e}。見圖9.1.3(f）。

步驟(6)：OPEN={c,d,e}。

步驟(7)：設置逆向指針。見圖9.1.3(g).注意e在此之前已有反向指針指向a，這種情況下要調整為指向b。

Graph-Search算法（續(xù)）循環(huán)3步驟(3)：假定110啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題求解程序的搜索器而被開發(fā)出來的。在多數情況下，待解問題可以用狀態(tài)空間加以表達，并用狀態(tài)空間或圖搜索算法求解。

寬度優(yōu)先和深度優(yōu)先等圖搜索算法的應用范圍有限。不過，與待解問題相關的（啟發(fā)）信息一般來說是可獲取并運用于搜索過程。

啟發(fā)式搜索要用到問題自身的某些特性信息，以指導搜索朝著有希望的方向前進。避免了盲目搜索，搜索效率高。啟發(fā)式搜索方法啟發(fā)式搜索最初是作為人工智能中問題111啟發(fā)式搜索方法啟發(fā)式搜索方法依靠任務無關信息來簡化搜索進程。在很多情況下，問題求解可視為系統(tǒng)化地構造或查找解答的過程。因此，在人工智能領域中，開發(fā)出了用于計算機問題求解的各種不同搜索算法。盡管在某些情況下并非十分有效，迷宮、定理證明、國際象棋等問題都可以由計算機程序給出解答。一般來說，搜索過程包括檢查搜索空間、估價可能有解的各種不同路徑、記錄已經搜索到的各個路徑。

啟發(fā)式搜索方法啟發(fā)式搜索方法依靠任務無關信息來簡化搜索進程。112啟發(fā)式搜索方法為簡化搜索并減少搜索過程中時有出現的大量可選路徑，從與待解問題有關的信息中所得到的啟發(fā)知識或“經驗法則”可用來確定搜索的方向。精心選擇的啟發(fā)信息可在很大程度上加大找出解答的機會，且在同時減少求解所需的時間。這一章統(tǒng)觀啟發(fā)式搜索方法并著重介紹A*算法。

啟發(fā)式搜索方法為簡化搜索并減少搜索過程中時有出現的大量可選路1139.2 啟發(fā)函數

啟發(fā)式方法，或更一般地，經驗規(guī)則，是指引搜索方向以有效求取到達目標節(jié)點路徑的原則或規(guī)則。一般來說，所用的啟發(fā)知識在很大程度上取決于待解問題和節(jié)點表示。例如，可用于求解前述s數碼問題的一個很好的啟發(fā)信息就是不在最終位置上的離家將牌個數，記為Misplaced(n).對于圖9.1所示初始將牌布局，將牌4,5,6離家，因而Misplaced(n)=3。8數碼問題

9.2 啟發(fā)函數啟發(fā)式方法，或更一般地，經驗規(guī)則，是指引搜1149.2 啟發(fā)函數（續(xù)）在圖搜索中，啟發(fā)知識的數值表示為從當前節(jié)點到目標節(jié)點的代價。它構成了如下代價函數的一部分：f(n)=g(n)+h(n) (9.2.1）其中，g(n)是從起始節(jié)點到當前節(jié)點n代價的最小估值，h(n)為從當前節(jié)點n到終止節(jié)點代價的估值。顯然，g(n)可用至今已被展開的從起始節(jié)點到當前節(jié)點元的所用路徑中的最小代價來近似。9.2 啟發(fā)函數（續(xù)）在圖搜索中，啟發(fā)知識的數值表示為從當1159.2 啟發(fā)函數（續(xù)）然而，從n到任一目標節(jié)點的路徑都是未知的。為此，無法精確確定h(n)而只能對其加以估算。在此規(guī)定目標節(jié)點的啟發(fā)函數值為零，即對于n{ti}，h(n)=0。在無法獲取啟發(fā)知識亦即對于所有節(jié)點n都有著h(n)=0的情況下，啟發(fā)式搜索退化為寬度優(yōu)先搜索。

當其啟發(fā)函數具有f(n)=g(n)+h(n)這一特殊形式時Graph-Search算法成為A算法。

9.2 啟發(fā)函數（續(xù)）然而，從n到任一目標節(jié)點的路徑1168數碼問題

布局n1

n2終止返回8數碼問題1179.2 啟發(fā)函數（續(xù)）A算法輸入：起始節(jié)點s和一組終止節(jié)點{ti}。輸出：圖G和樹T。(1) 初始化。以起始節(jié)點s構造圖G和集合OPEN，G{s}，OPEN{s}，且令集合CLOSE為空集。(2) LOOP：若OPEN為空集，算法以失敗結束。(3) 從OPEN中取出具有最小f(n)值的節(jié)點n，并使OPENOPEN－{n},CLOSEDCLOSED{n}。(4) 若n任{ti}，算法以成功結束。(5) 展開n且令M為n的子節(jié)點且不為其前輩節(jié)點的節(jié)點集。將M加入G。9.2 啟發(fā)函數（續(xù)）A算法輸入：起始節(jié)點s和一1189.2 啟發(fā)函數（續(xù)）A算法續(xù)

(6) 對每一個節(jié)點mM：①如果mOPEN且mCLOSED，將m放入OPEN。估計h(m)并計算f(m)=g(m)+h(m)，其中g(m)=g(n)+cost(n,m)。②如果mOPEN或mCLOSED，將其逆向指針調整到給出最小g(m)值的路徑。③如果m的逆向指針被調整且m在CLOSED中，將其重新加入OPEN。(7) 回到LOOP9.2 啟發(fā)函數（續(xù)）A算法續(xù)(6) 對每一個節(jié)1199.2 啟發(fā)函數（續(xù)）A算法續(xù)

函數g(n)，h(n)和f(n)在最小代價路徑上的值可基于下列定義得到。定義9.6g*(n)是從s到n的所有路徑中的最小代價。定義9.7h*(n)是從n到一個目標節(jié)點的所有路徑中的最小代價。由g*(n)和h*(n)的定義可得f*(n)=g*(n)+h*(n) (9.2.2)其中f*(n)是從起始節(jié)點經過節(jié)點n到達一個目標節(jié)點的所有路徑中的最小代價。

9.2 啟發(fā)函數（續(xù)）A算法續(xù)函數g(n)，h(n1209.2 啟發(fā)函數（續(xù)）A算法續(xù)下面用圖9.2.1給出的實例示范g*和h*的計算方法。

9.2 啟發(fā)函數（續(xù)）A算法續(xù)下面用圖9.2.1給出的實1219.2 啟發(fā)函數（續(xù)）A算法續(xù)有向圖G=(v,E)中，v={a,b,c,d,e,i,j,k,l}E={(s,a),(s,b),(s,c),(a,d),(b,d),(b,e),(c,e),(d,i),(d,j),(d,k),(e,j),(e,k),(e,i)}連線的代價由函數cost給出，且起始節(jié)點為s，目標節(jié)點為{j,k}。計算g*，h*和f