【正文】 幾個概念? 可解標(biāo)示過程 ：由可解子節(jié)點來確定父節(jié)點，祖父節(jié)點等為可解節(jié)點的過程? 不可解標(biāo)示過程 ：由不可解子節(jié)點來確定父節(jié)點，祖父節(jié)點等為不可解節(jié)點的過程基本思想：? 對與或樹（圖）標(biāo)記（示）可解與不可解的遞歸過程，通過對終節(jié)點的可解與否最終確定初始節(jié)點是否可解。d(n)= d(n)p(n)g(n)h(n)f(n)=③ d(n)=(前面例子中：初始狀態(tài) :d(n)W(n)g(n)h(n)f(n)=– ② d(n)(搜索深度 ),g(n)g(n)h(n)f(n)0:h(n)h*(n)? h(n)取值分析：– p(n)顯然 有 h(n)p(n)（ 每一個將牌與其目 標(biāo) 位置之 間 距離的 總 和 ），h*(n)h(n)W(n)但在問題求解過程中不可能都明確知道? 例：八數(shù)碼難題h(n) = w(n) (將牌不在位個數(shù) )， 顯然有 h(n)可以證明 :(1)如果滿足單調(diào)限制 ,則當(dāng) A*選擇節(jié)點 n擴展時 ,就已經(jīng)發(fā)現(xiàn)了通向節(jié)點 n的最佳路徑 .即 :g(n)=g*(n)(2)如果 A*滿足單調(diào)限制 ,則 A*所擴展節(jié)點序列的估價函數(shù)值是單調(diào)上升的 .43A*算法的理論意義? A*算法的理論意義在于給出了求解最佳解的條件 h(n) ≤ h*(n)?？煽闯?:節(jié)點 ni到目標(biāo)節(jié)點最優(yōu)費用的估價不會超過從節(jié)點 ni到其子節(jié)點 nj的弧代價加上從 nj到目標(biāo)節(jié)點最優(yōu)費用的估價 .nj)h(nj)+)nj的弧代價 .將上式改寫成 : c(ni,nj)其中 ,在 A*算法中 ,每當(dāng)要擴展一個節(jié)點時 ,都要先檢查其子節(jié)點是否已在 OPEN表或 CLOSED表中 ,有時還需要調(diào)整指向父節(jié)點的指針 ,這就增加了搜索的代價 .如果對啟發(fā)函數(shù) h(n)加上單調(diào)限制 ,就可以減少檢查及調(diào)整的工作量 ,提高搜索效率 .單調(diào)限制是指 h(n)滿足兩個條件 :(1) h(Sg)=0(2) 設(shè) nj是節(jié)點 ni的任意子節(jié)點 ,則有 :h(ni)h(nj) [證畢 ] 42（ 3）單調(diào)性 指 h(n)的單調(diào)限制這與定理的前提條件矛盾 ,至少在節(jié)點 n上有 h1g2(n)≥ f*(s)h1(n)g1(n)≤ g2(n)故有 A2擴展的節(jié)點 ,=g2(n)≤ f*(s)所以 h2(n)≤ f*(s)g2(n)f2(n)≤ f*(s),有 g1(n)≥ f*(s)所以 ≥ f*(s)+≥ f*(s),n沒有被 A1選擇擴展 ,因此 A1結(jié)束時 ,A1擴展了 n的父節(jié)點 ,沒有被 A1擴展 。1)被 A2擴展了 ,k(d(n) (3) 證明 d(n)=k+1時 , 所有路徑的端節(jié)點 ,結(jié)論成立 。 41證明 : 使數(shù)學(xué)歸納法 , 對節(jié)點的深度應(yīng)用歸納法 。擴展的節(jié)點數(shù)就較少。即啟發(fā)函數(shù)中 ,可以想像到 f(n)越接近于 f*(n),f*(n),其評價函數(shù)值 f(n) [證畢 ]40（ 2） A*算法的最優(yōu)性 （信息性）? 應(yīng)用 A*的過程中 ,f*(s) f(t) 這時算法 A*應(yīng)選 n作為當(dāng)前點擴展 , 不可能選 t, 從而也不會去測試目標(biāo)節(jié)點 t, 即這與假定 A*選 t結(jié)束矛盾。所以， A*算法一定會終止c) A*算法一定會終止在最優(yōu)路徑上證明：反證法若 A*算法不是在最優(yōu)路徑上終止，而是在某個目標(biāo)節(jié)點 t結(jié)束則 f(t) = g(t) f*(s)而根據(jù) b)證明可知：在 A*結(jié)束前， OPEN表中存在最優(yōu)路徑上的節(jié)點 n, 且有 f(n) ≤≤所以 f(設(shè)每個弧的長度均為 1)39 所以 g*(n)≥ d*(n)e因 g(n) ≥ g*(n) 所以 g(n) ≥ d*(n)e因 h(n) ≥ 0 (設(shè) h(n) ≥ 0) 所以 f(n) = g(n) + h(n) ≥ g(n)所以 f(n) ≥ d*(n)e若 A*不結(jié)束 ,圖中各邊的最小代價d*(n)（反證法）? 假定 A*不結(jié)束 ,f*(s)。所以 f(n) 因為：最佳路徑上的所有節(jié)點的 f*值都應(yīng)相等=+h(n)≤g*(n)h(n)g(n)f(n)因而 s到 n的最佳路徑也能找到 ,因此能找到 s到 np,的最佳路徑 ,因 s一開始是在 OPEN上 ),在 OPEN中存在最佳路徑上的節(jié)點。s在 OPEN中 ,– 結(jié)論： A*算法是可采納的? 證明：– 對有限圖， A*算法一定會在有限步結(jié)束– 對無限圖，只有從 S0到 Sg有路徑存在，則 A*算法也必然會結(jié)束– A*算法一定會終止在最優(yōu)路徑上37a)對有限圖， A*算法一定會在有限步結(jié)束證明：因為搜索圖為有限圖，所以會出現(xiàn)以下情況：– 算法找到解，則成功結(jié)束（算法第 4步）– 算法找不到解，則必然會因 OPEN表變空而結(jié)束（算法第 2步）b)對無限圖，只有從 S0到 Sg有路徑存在，則 A*算法也必然會結(jié)束證明 ： （分 2步）– 第 1步證明 ： A*結(jié)束前 ,? A*算法的性質(zhì)：（ 1）可采納性– 如果一個搜索算法對于任何具有解路徑的圖都能找到一條最佳解路徑。? 對于寬度優(yōu)先搜索算法， h(n)=0，滿足 h(n)≤h*(n)。36A*算法 又稱最佳圖搜索算法，由著名人工智能學(xué)者Nilsson提出 。這個定義包含了 g（ x） ≥ g*（ x ） 。? 實現(xiàn)類型：局部擇優(yōu)搜索、全局擇優(yōu)搜索局部擇優(yōu)搜索 類似深度優(yōu)先? 基本思想：在當(dāng)前擴展的子節(jié)點中選 f(x) 值最小的子節(jié)點為下一個考察的節(jié)點? 實現(xiàn)：節(jié)點 n擴展后的各子節(jié)點計算出估價值后，按由小到大次序放到 OPEN表的首部? 分析：可把深度優(yōu)先、代價樹的深度優(yōu)先看成其特例?？刂撇呗詾?: 選取評價函數(shù)值最小者進行擴展 (往下搜索 )。其他子節(jié)點深度為父結(jié)點深度加 1。d(n)是搜索的深度。8)不在位。2,初始狀態(tài) w(n)=4,例如 ,? h(n)=w(n),+=+=30開始把 S放入 OPEN表，計算估價函數(shù) f (s)OPEN表為空表？選取 OPEN表中 f值最小的節(jié)點 i放入 CLOSED表i為目標(biāo)節(jié)點嗎？擴展 i，得后繼節(jié)點 j，計算 f(j)，提供返回節(jié)點 i的指針，利用 f(j)對 OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖 有序搜索算法框圖是否是否v算法31例： 八數(shù)碼難題（ 8puzzle? 啟發(fā)式算法通常由兩部分組成 : – 啟發(fā)方法– 使用該方法搜索狀態(tài)空間的算法。– h(n) g(n)時 , 也可以忽略 g(n), 這時有 f(n) = h(n), 這有利于搜索的效率 , 但影響搜索的完備性。– 保持 g(n)項就保持了搜索的寬度優(yōu)先趨勢 , 這有利于搜索的完備性 , 但影響搜索的效率。? g(x)、 h(x)作用分析– 一般地 , 在 f(n)中 , g(n)的比重越大 , 越傾向于寬度優(yōu)先搜索方式。 ② h(x)為啟發(fā)函數(shù) ,① 估價函數(shù) 評估節(jié)點的方法– 用來估算節(jié)點希望程度的量度，叫做估價函數(shù) 28f(x)=g(x)+h(x)? 27啟發(fā)性信息類型1）用于 擴展節(jié)點的選擇– 即決定下一個擴展節(jié)點 ,以免象在廣度優(yōu)先和深度優(yōu)先搜索中那樣盲目地擴展2）用于生成節(jié)點的選擇– 即用于決定生成哪個或哪幾個后繼節(jié)點 ,而不是生成所有的節(jié)點3）用于刪除節(jié)點的選擇– 即決定用于從搜索樹中拋棄或修剪的節(jié)點? 我們討論的主要是基于 “擴展節(jié)點的選擇 ”的啟發(fā)式搜索，這種搜索總是選擇 “最有希望 ”的節(jié)點作為下一個被擴展的節(jié)點。? 解決：– 利用問題的啟發(fā)性信息來引導(dǎo)搜索– 減少搜索范圍– 降低問題復(fù)雜度? 啟發(fā)信息：進行搜索技術(shù)一般需要某些有關(guān)具體