人工智能第三章基本的問題求解方法-資料下載頁
2025-02-19 12:49本頁面
【正文】 g161。 f*(n)=g*(n)+h*(n)： 從 s經(jīng)過n到 g的最短路徑l g*(n)：從 s到 n的最短路徑l h*(n)：從 n到 g的最短路徑161。 f（ n） =g（ n） +h（ n）：從 s經(jīng)過 n到 g的最短路徑的估計(jì)值l g(n)、 h(n)分別是 g*(n)、 h*(n)的估計(jì)值161。 g(n)l 一般 取實(shí)際走過的路徑的費(fèi)用和 .l g(n)?g*(n)l 隨著算法的執(zhí)行， 由于指針的變動(dòng)，g(n)會(huì)下降 .161。 h?0l 沒有啟發(fā)式信息 。啟發(fā)式搜索算法161。 A算法161。 A*算法A算法161。 在 Graphsearch過程中，如果第 8步的重排open表是依據(jù) f（ n） =g（ n） +h（ n）進(jìn)行的，則稱該過程為 A算法。l g(n)取實(shí)際走過的路徑的費(fèi)用和 。l 節(jié)點(diǎn)排序是按照 f(n)從小到大排 。l 如前例 九宮重排問題算法 A*161。 在 A算法中，如果滿足條件：0≤h(n)≤h*(n)則 A算法稱為 A*算法。l 稱 h（ x）為 h*（ x）的下界，它表示某種偏于保守的估計(jì)。161。 啟發(fā)式搜索算法 A*又稱為最佳圖搜索算法(OptimalSearch)。 經(jīng)典例題（八數(shù)碼難題）：設(shè)有八數(shù)碼難題，起始狀態(tài)如右圖，要求找出九宮重排的最終解路徑，并畫框圖。28316475解法一：第一步：取估價(jià)函數(shù)為 f（ n） =d（ n） +w（ n），則顯然按照定義 1它是 A算法；第二步：因?yàn)?w（ n）指的是不在位的個(gè)數(shù)，所以w（ n） =4，即估計(jì)只需要走 4步即可到達(dá)目標(biāo)狀態(tài)，而實(shí)際上要到達(dá)目標(biāo)狀態(tài)肯定要大于 3步，即 w（ x） ≤w *（ x），滿足定義，所以是 A*算法；第三步：畫圖，并計(jì)算各個(gè)狀態(tài) f（ n）的值，取f（ n）值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)充。(圖見前 )解法二：取估價(jià)函數(shù)為 f（ n） =d（ n） +P（ n），同理也是 A*算法；如圖Tips A算法與 A*算法區(qū)別161。區(qū)別在于在 A*算法中， 0≤h(n)≤h*(n)161。示例：161。八數(shù)碼難題中 h(n)的三種定義252。h(n)=w(n),h(n)=p(n)A*算法252。h(n)=p(n)+3s(n)A算法A*算法具有可采納性 一般地說對任意一個(gè)圖 , 當(dāng) s到目標(biāo)節(jié)點(diǎn)有一條路徑存在時(shí) , 如果搜索算法總是在找到一條從 s到目標(biāo)節(jié)點(diǎn)的最佳路徑上結(jié)束 , 則稱該搜索 算法是可采納的 (Admissibility)。lA*就具有可采納性即當(dāng)問題有解時(shí) , A*一定能找到一條到達(dá)目標(biāo)節(jié)點(diǎn)的最佳路徑。（why？）?證明見參考資料 A*算法具有可采納性?考慮 h(n)≡0 的情況?。。?！A*算法的理論意義 A*算法的理 論 意 義 在于 給 出了求解最佳解的條件?h(n)≤ h*(n) 對給定的問題 ,函數(shù) h*(n)在問題有解的條件下客觀上是存在的。但在問題求解過程中不可能都明確知道。因此 , 對實(shí)際問題 , 能不能使所定義的啟發(fā)函數(shù)滿足下界范圍條件 ? 這是個(gè)問題。如果困難很大 , 那未 A*算法的實(shí)際應(yīng)用就會(huì)受到限制。 以前面 八數(shù) 碼難題為 例定 義 h(n)為 任意 節(jié) 點(diǎn)與目 標(biāo) 之 間 的差異?若取 = w(n)(將牌不在位個(gè)數(shù) ), 那未很容易看出 , 盡管我 們對 具體的 h*(n)是多少很 難 確切知道 , 但根據(jù) “ 不在位 ” 將牌個(gè)數(shù) 這 個(gè)估 計(jì) , 就能得出 至少要移 動(dòng) W(n)步 才能到達(dá)目 標(biāo) , 顯然有 h(n) = W(n)≤ h*(n) 。?進(jìn) 一步考 慮 任意 節(jié) 點(diǎn)與目 標(biāo) 之 間 距離的信息 , 即取 h(n) = p(n), p(n)定 義為 每一個(gè)將牌與其目 標(biāo) 位置之 間 距離 (不考 慮夾 在其 間 的將牌 )的 總 和 ,那未同 樣 能斷定 至少也要移 動(dòng) p(n)步才能達(dá)到目 標(biāo) ，仍然有 P(n)≤ h*(n) 。啟發(fā)信息的強(qiáng)度的進(jìn)一步分析強(qiáng)： 降低搜索工作量 ，但可能導(dǎo)致找不到最優(yōu)解弱： 一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最優(yōu)解h(n)取不同函數(shù) 時(shí) 的八數(shù) 碼難題 求解情況 進(jìn)行比 較 , 比 較 h(n) = 0、 h(n) = W(n)和 h(n) = p(n)三種情況的求解 結(jié) 果。 ①h(n) = 0: 即啟 發(fā) 函數(shù)啟 發(fā) 信息 為0, f(n) = h(n) + g(n) = g(n)＝ d(n)(搜索深度 ),此實(shí)際上是寬度優(yōu)先搜索。 ② h(n)=W(n):即啟發(fā)函數(shù)取將牌不在位的信息 ,f(n)=h(n)+g(n)=W(n)+d(n)(搜索深度 )。③ h(n)=p(n):即啟發(fā)函數(shù)取每一個(gè)將牌與其目標(biāo)位置之間距離的總和的信息 實(shí)際 上 ① 中 h(n) =0 ≤h*(n) ， ② 和 ③ 均已證明 W(n)≤h*(n) ， P（ n） ≤h*(n) ，即 3種算法都是 A*算法。比較搜索空間， 分析啟發(fā)信息強(qiáng)弱的效果 ：啟 發(fā) 函數(shù) h(n)=0 h(n)=W(n) h(n)=p(n)擴(kuò) 展 節(jié) 點(diǎn)數(shù) 26 6 5生成 節(jié) 點(diǎn)數(shù) 46 13 11附：評價(jià)搜索算法的指標(biāo)外顯率（ Perance） P=L/TL — 從初始狀態(tài)到目標(biāo)狀態(tài)的長度；T — 從初始狀態(tài)到目標(biāo)狀態(tài)所產(chǎn)生的所有狀態(tài)的個(gè)數(shù)；顯然 P=1時(shí)，說明有效路徑所經(jīng)歷的節(jié)點(diǎn)都有用有效分支數(shù)（ Effective Branching Factor）B — 搜索過程中，平均每個(gè)節(jié)點(diǎn)產(chǎn)生的分支數(shù)目；因?yàn)槊總€(gè)節(jié)點(diǎn)產(chǎn)生的平均分支數(shù)為 B，所以從初始到目標(biāo)狀態(tài)產(chǎn)生的總分支數(shù) T為： 本章回顧p教學(xué)內(nèi)容：本章在上一章知識表示的基礎(chǔ)上研究問題求解的方法，是人工智能研究的又一核心問題。本章主要介紹基本的搜索技術(shù)p教學(xué)重點(diǎn)：圖搜索策略、啟發(fā)式搜索p教學(xué)難點(diǎn)：啟發(fā)式搜索p教學(xué)方法：課堂教學(xué)為主，輔以恰當(dāng)?shù)膶?shí)驗(yàn)。注意結(jié)合前面所學(xué)知識表示的基礎(chǔ)內(nèi)容，將其與問題求解方法融為一體。p教學(xué)要求：重點(diǎn)掌握一般圖搜索策略，掌握各種搜索方法，尤其是啟發(fā)式搜索中的 A*算法 。 homeworkp選做：利用 A*算法求解九宮重排問題。p要求：同前 THE END 演講完畢，謝謝觀看！
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1