人工智能第三章基本的問題求解方法(參考版)
2025-02-21 12:49本頁面
【正文】 p要求：同前 THE END 演講完畢，謝謝觀看！。 注意結合前面所學知識表示的基礎內容，將其與問題求解方法融為一體。p(n)擴 展 節(jié) 點數 26 6 5生成 節(jié) 點數 46 13 11附：評價搜索算法的指標外顯率（ Perance） P=L/TL — 從初始狀態(tài)到目標狀態(tài)的長度；T — 從初始狀態(tài)到目標狀態(tài)所產生的所有狀態(tài)的個數；顯然 P=1時，說明有效路徑所經歷的節(jié)點都有用有效分支數（ Effective Branching Factor）B — 搜索過程中，平均每個節(jié)點產生的分支數目；因為每個節(jié)點產生的平均分支數為 B，所以從初始到目標狀態(tài)產生的總分支數 T為： 本章回顧p教學內容：本章在上一章知識表示的基礎上研究問題求解的方法，是人工智能研究的又一核心問題。W(n) h(n) h(n)=即啟發(fā)函數取每一個將牌與其目標位置之間距離的總和的信息 實際 上 ① 中 h(n) =0 ≤h*(n) ， ② 和 ③ 均已證明 W(n)≤h*(n) ， P（ n） ≤h*(n) ，即 3種算法都是 A*算法。=③ (搜索深度 )。+=+=即啟發(fā)函數取將牌不在位的信息 ,=② ①h(n) = 0: 即啟 發(fā) 函數啟 發(fā) 信息 為0, f(n) = h(n) + g(n) = g(n)＝ d(n)(搜索深度 ),啟發(fā)信息的強度的進一步分析強： 降低搜索工作量 ，但可能導致找不到最優(yōu)解弱： 一般導致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最優(yōu)解h(n)取不同函數 時 的八數 碼難題 求解情況 進行比 較 , 比 較 h(n) = 0、 h(n) = W(n)和 h(n) = p(n)三種情況的求解 結 果。 以前面 八數 碼難題為 例定 義 h(n)為 任意 節(jié) 點與目 標 之 間 的差異?若取 = w(n)(將牌不在位個數 ), 那未很容易看出 , 盡管我 們對 具體的 h*(n)是多少很 難 確切知道 , 但根據 “ 不在位 ” 將牌個數 這 個估 計 , 就能得出 至少要移 動 W(n)步 才能到達目 標 , 顯然有 h(n) = W(n)≤ h*(n) 。因此 , 對實際問題 , 能不能使所定義的啟發(fā)函數滿足下界范圍條件 ? 這是個問題。（why？）?證明見參考資料 A*算法具有可采納性?考慮 h(n)≡0 的情況?。。。*算法的理論意義 A*算法的理 論 意 義 在于 給 出了求解最佳解的條件?h(n)≤ h*(n) 對給定的問題 ,函數 h*(n)在問題有解的條件下客觀上是存在的。h(n)=p(n)+3s(n)A算法A*算法具有可采納性 一般地說對任意一個圖 , 當 s到目標節(jié)點有一條路徑存在時 , 如果搜索算法總是在找到一條從 s到目標節(jié)點的最佳路徑上結束 , 則稱該搜索 算法是可采納的 (Admissibility)。h(n)=w(n),示例：161。(圖見前 )解法二：取估價函數為 f（ n） =d（ n） +P（ n），同理也是 A*算法；如圖Tips A算法與 A*算法區(qū)別161。47312 啟發(fā)式搜索算法 A*又稱為最佳圖搜索算法(Optimall 稱 h（ x）為 h*（ x）的下界，它表示某種偏于保守的估計。 在 A算法中，如果滿足條件：l 節(jié)點排序是按照 f(n)從小到大排 。 在 Graphsearch過程中，如果第 8步的重排open表是依據 f（ n） =g（ n） +h（ n）進行的，則稱該過程為 A算法。 A算法161。 h?0l 沒有啟發(fā)式信息 。g*(n)l 隨著算法的執(zhí)行， 由于指針的變動，g(n)會下降 . g(n)l 一般 取實際走過的路徑的費用和 .l g(n)分別是 g*(n)、 h*(n) f*(n)=g*(n)+h*(n)： 從 s經過n到 g的最短路徑l g*(n)：從 s到 n的最短路徑l h*(n)：從 n到 g的最短路徑161。 從而達到降低問題復雜度 ,大大減少了擴展的節(jié)點 ,與深度優(yōu)先搜索和寬度優(yōu)先搜索相比較 ,68262685147316826181831524735247315268686868n W(n):與目標相比 , 錯位的數字數目，即不在位的數字個數 。526c8b47325668圖（ c）中 s（ a） =6。526c8b4732564731e． g．八數碼難題的估價函數f（ n） =g（ n） +h（ n）d（ n）：節(jié)點 n的深度w（ n）：不在位的數字個數p（ n）：不在位的數字離目標的距離之和例：右圖（ a）中 6不在位， w（ n） =4 ， p（ n） =1+2+1+1=5；（ b） 1不在位， w（ n） =4 ， p（ n） =3+2+2+2=9 2 這就需要 有一種方法來計算待擴展節(jié)點有希望通向目標節(jié)點的不同程度 ,基本思想啟發(fā)式搜索過程中 , p利用知識來引導搜索，達到減少搜索范圍
規(guī)章制度相關推薦
鄂ICP備17016276號-1