ch5狀態(tài)空間搜索策略new-文庫(kù)吧資料
2025-02-28 00:49本頁(yè)面
【正文】 2 3 8 4 7 6 5 g=3 h=1, f=4 h=0, f=4 h=2, f=6 八數(shù)碼難題的的 A*搜索圖 （ h(n) = P(n)） A*算法例 2： 修道士和野人問(wèn)題 設(shè)在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束： ，但每次船上至多可載兩個(gè)人； ，修道士就會(huì)被野人吃掉。盡管不能確切知道 h*(n) ，但當(dāng)采用單位代價(jià)時(shí)，通過(guò)對(duì)“不在位”數(shù)碼個(gè)數(shù)的估計(jì)，可以得出至少要移動(dòng) W(n)步才能到達(dá)目標(biāo)，顯然有 W(n)≤h*(n)，滿足 A*算法的限制條件。所以，可考慮對(duì)估價(jià)函數(shù) f(n)進(jìn)行某些修改或限制。 因此 ， 初始節(jié)點(diǎn)棋局 的 f(n)值等于 4。 失敗 成功 局部最佳優(yōu)先搜索算法框圖 是 否 是 否 把子節(jié)點(diǎn)送入 OPEN表，并對(duì)其中的所有節(jié)點(diǎn)按估價(jià)函數(shù)值由小到大重排。 ? 其算法效率類似于縱向搜索算法，但使用了與問(wèn)題特性相關(guān)的估價(jià)函數(shù)來(lái)確定下一步待擴(kuò)展的節(jié)點(diǎn)，因此是一種啟發(fā)式搜索方法。 1. 全局擇優(yōu) 在 Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展 2. 局部擇優(yōu) 在剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。需要根據(jù)問(wèn)題自身的特性來(lái)確定，體現(xiàn)了問(wèn)題自身的啟發(fā)性信息，因此也稱為 啟發(fā)函數(shù) 。可以從節(jié)點(diǎn) n反向跟蹤到初始節(jié)點(diǎn) S0,得到一條當(dāng)前最小代價(jià)路徑，把這條路徑上所有有向邊的代價(jià)相加，就得到g(n)的值。一般有以下三種： ① 幫助確定擴(kuò)展節(jié)點(diǎn)的信息； ② 幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息； ③ 在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)決定哪些節(jié)點(diǎn)應(yīng)被刪除的信息 ? 估價(jià)函數(shù) f(n)： 用于估計(jì) 節(jié)點(diǎn)代價(jià) 的函數(shù) 定義 為從初始節(jié)點(diǎn) S0出發(fā)，經(jīng)過(guò)節(jié)點(diǎn) n約束后，到達(dá)目標(biāo)節(jié)點(diǎn) Sg的所有路徑中最優(yōu)路徑的代價(jià)估計(jì)值。 ? 啟發(fā)式算法 利用問(wèn)題的特殊性，選擇待擴(kuò)展的節(jié)點(diǎn)，以縮小搜索范圍，提高搜索速度。這種利用問(wèn)題自身的特性來(lái)引導(dǎo)搜索過(guò)程， 提高搜索效率 的搜索策略稱為 啟發(fā)式搜索 或 有信息搜索 。 解路徑為 : So： l →11 → 12 →13 → 14 ： Sg Sg 八數(shù)碼難題的有界深度優(yōu)先搜索 2 8 3 1 4 7 6 5 S0 1 2 8 3 1 4 7 6 5 2 2 3 1 8 4 7 6 5 11 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 3 7 13 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 4 8 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 5 6 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 9 10 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 14 12 深度限制為 4 ?上面討論的搜索方法都沒(méi)有用到問(wèn)題本身的特性信息，只是按事先設(shè)定的線路進(jìn)行搜索，具有較大的盲目性。 2 8 3 1 4 7 6 5 S0 1 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 3 2 8 3 1 6 7 5 4 4 2 8 1 6 3 7 5 4 2 8 3 1 6 7 5 4 5 2 8 1 6 3 7 5 4 6 八數(shù)碼難題的深度優(yōu)先搜索 從深度優(yōu)先搜索的算法可以看出 ,搜索一旦進(jìn)入某個(gè)分支，就將沿這個(gè)分支一直進(jìn)行下去，如果目標(biāo)恰好在這個(gè)分支上 ,則它可以很快找到解 .但是 ,如果目標(biāo)不在這個(gè)分支上，且分支是一個(gè)無(wú)窮分支，則搜索過(guò)程就不可能找到解。圖示如下： S0 1 2 3 7 6 8 4 5 9 起始結(jié)點(diǎn) 起始 把 S0放入 Open表 S0是否為 目標(biāo)結(jié)點(diǎn) 是否 Open 為空表 把 Open表中的第一個(gè)結(jié) 點(diǎn) n移入 Closed表 結(jié)點(diǎn) n 的深度是否等于深度 界限 擴(kuò)展結(jié)點(diǎn) n，把其后代放入 Open表的前端 是否有 任何后繼結(jié)點(diǎn)為目標(biāo) 結(jié)點(diǎn) 成功 失敗 成功 是 否 是 是 是 否 否 否 示意圖 算法框圖 ? 深度優(yōu)先搜索算法如下： ? (1)把初始結(jié)點(diǎn) S0放入 Open表中； ? (2)如果 Open表空 ， 則問(wèn)題無(wú)解 ， 失敗退出； ? (3)把 Open表的第一個(gè)結(jié)點(diǎn)取出放入 Close表 ， 并記該結(jié)點(diǎn)為 n。 ?深度優(yōu)先搜索 ?深度優(yōu)先搜索是一種 后生成的結(jié)點(diǎn)先擴(kuò)展的策略 。 S L O M F P Q N F F F 起始結(jié)點(diǎn) 起始 把 S0放入 Open表
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1