人工智能第1章盲目搜索-資料下載頁
2025-02-20 15:24本頁面
【正文】 若所有連接弧線具有相等代價，則簡化為橫向搜索算法。 均一代價搜索中的幾個記號： 起始節(jié)點記為 S； 從節(jié)點 i到它的后繼節(jié)點 j的連接弧線代價記為 c(i， j)； 從起始節(jié)點 S到任一節(jié)點 i的路徑代價記為 g(i)。 開始 把 S放入 OPEN表 OPEN表為空表？ 把第一個節(jié)點 (n)從 OPEN表移至 CLOSED表 擴展 n，把 n的后繼節(jié)點放入 OPEN表的末端，提供返回節(jié)點 n的指針 失敗 均一代價搜索算法框圖 是 否 把第一個節(jié)點 (n)從 OPEN表移至 CLOSED表 n為目標節(jié)點嗎？ 成功 是 否 按 g(i)值由小到大的順序重排 OPEN表 均一代價搜索法思路： 從 A點開始依次展開得到 AB（ 7） 、 AC（ 3） 、 AD（ 10） 、 AE（ 15） 四個新結(jié)點 ， 把第一層結(jié)點 A標記為已展開 ， 并且每個新結(jié)點要記錄下其距離 （ 括號中的數(shù)字 ） ； 把未展開過的 AB、 AC、 AD、 AE四個結(jié)點中距離最小的一個展開 ， 即展開 AC（ 3） 結(jié)點 ， 得到 ACB（ 8） 、 ACD（ 16） 、 ACE（ 13） 三個結(jié)點 ， 并把結(jié)點 AC標記為已展開； 再從未展開的所有結(jié)點中找出距離最小的一個展開 ， 即展開 AB（ 7） 結(jié)點 ， 得到 ABC（ 12） 、 ABD（ 20） 、 ABE（ 19） 三個結(jié)點 ， 并把結(jié)點AB標記為已展開； 再次從未展開的所有結(jié)點中找出距離最小的一個展開 ， 即展開 ACB（ 8）結(jié)點 …… ； 每次展開所有未展開的結(jié)點中距離最小的那個結(jié)點 ， 直到展開的新結(jié)點中出現(xiàn)目標情況 （ 結(jié)點含有 5個字母 ） 時 ， 即得到了結(jié)果 。 算法分析： 由上可見 ， 均一代價搜索法并沒有象橫向搜索一樣展開所有結(jié)點 ， 只是根據(jù)代價最小的原則 ， 每次展開距離 A點最近的那個結(jié)點 ， 反復(fù)下去即可最終得到答案 。 雖然中途有時也展開了一些并不是答案的結(jié)點 ， 但這種展開并不是大規(guī)模的 ， 不是全部展開 ，因而耗時要比橫向搜索小得多 。 迷宮問題如下， F是入口， B是出口，試采用均一代價搜索算法進行求解。 舉例：迷宮問題 0 1 2 3 x 1 2 3 y F G H E C A D B 2 2 2 4 1 1 1 1 注：每個節(jié)點小括號內(nèi)的數(shù)值表示走到該節(jié)點所需付出的代價。 F(0) G(1) H(3) E(2) C(3) A(6?4) D(5) B(6) 1 2 3 4 5 6 7 8 搜索到的路徑為黃線所示 演講完畢，謝謝觀看！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1