人工智能第三章基本的問題求解方法(編輯修改稿)
2025-03-09 12:49 本頁面
【文章內(nèi)容簡介】 。528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765125 6 7312384765目標(biāo)8234187654p寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第 8步具體化為本算法中的第 6步，這實際是將 OPEN表作為 “ 先進先出 ” 的隊列進行操作。p一定能找到解p找到的解一定是最佳解u(在每個路徑消耗是同樣的意義上 )p搜索的空間大、慢。 分析p深度優(yōu)先搜索：首先擴展最新產(chǎn)生的 (即最深的 )節(jié)點。深度相等的節(jié)點可以任意排列。p特點：擴展最深的節(jié)點 ,使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當(dāng)搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。p算法：與寬度優(yōu)先相似，不同在于： (5) 把 n的所有后繼節(jié)點放到 OPEN表的前端 depthfirst search34 5 6 78 9 10 11 12 13 14 1516 17 18 19 20 21 ★ 23 24 ★ 26 27 28 29 30 3112活結(jié)點表1 2 4 84 95 10105★演示例 九宮重排問題2 8 3 1 6 42 7 ■ 5初始狀態(tài)1 2 3 8 ■ 47 6 5目標(biāo)狀態(tài)應(yīng)用示例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61234 567 89a bd1 2 3 8 47 6 5目標(biāo)分析① 不一定能找到解。② 解不一定是最佳解。 其他方法p含有深度界限的深度優(yōu)先搜索算法：p基于代價樹的搜索算法：TOPIC4 heuristic searchp盲目搜索效率低，耗費過多的計算空間與時間，這是組合爆炸的一種表現(xiàn)形式。 p利用知識來引導(dǎo)搜索，達到減少搜索范圍，降低問題復(fù)雜度的目的。p啟發(fā)式方法 的本質(zhì)是部分地放棄算法 一般化 , 通用化 的概念 , 把所要解的問題的具體領(lǐng)域 的知識加進算法中去 , 以提高算法的效率。 ?啟發(fā)式搜索 ：就是利用與問題有關(guān)的啟發(fā)信息進行搜索?啟發(fā)信息：與具體問題有關(guān)的特性信息?啟發(fā)信息的強度?強：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解?弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎赡芸梢哉业阶顑?yōu)解?難點：?獲??；?強度的確定；啟發(fā)信息的用途a、用于決定要擴展的下一節(jié)點（避免盲目擴展）b、在擴展過程中，用于決定生成哪一個或哪幾個后繼（以免太多無用節(jié)點）C、用于決定被拋棄 or被修剪的節(jié)點（博羿中常用，其它不常見）?；舅枷?
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1