[工學(xué)]狀態(tài)空間的搜索策略-免費(fèi)閱讀
【正文】 如果對 h(n)加上單調(diào)性限制 ， 可以減少檢查及調(diào)整的工作量 ， 從而減少搜索代價(jià) 。 e) 若至 OLD節(jié)點(diǎn)的代價(jià)較低或一樣 ， 則停止擴(kuò)展節(jié)點(diǎn) 。 ③ 選取 OPEN表中未設(shè)置過的具有最小 f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn) BESTNODE， 并把它放入 CLOSED表 。 ? g*(n) = k(S, n)： 從初始節(jié)點(diǎn) S到節(jié)點(diǎn) n的最小代價(jià) 。 若 f(j)較小 ， 則： I. 以 f(j) 取代 f(j)old。 ③ 從 OPEN表中選擇一個(gè) f值最小的節(jié)點(diǎn) i。 根據(jù)格局 （ 如博弈問題 ） 或狀態(tài)的特點(diǎn)來計(jì)算 。 啟發(fā)信息 指導(dǎo)搜索過程 ， 與具體問題求解有關(guān)的控制性信息 。 ⑤ 若 n不可擴(kuò)展 ， 則轉(zhuǎn)第 (2)步 。 有界深度優(yōu)先搜索的幾點(diǎn)說明 如果問題有解 ， 且路徑長度 ?dm， 則上述搜索過程一定能求得解 。 有界深度優(yōu)先搜索算法流程 ① 把起始節(jié)點(diǎn) S放到 OPEN表中 。 如果目標(biāo)節(jié)點(diǎn)不在此分支上 ， 且該分支又是一個(gè)無窮分支 ， 則不可能得到解 。 ③ 把 OPEN表中第一個(gè)節(jié)點(diǎn) n取出 ， 放入 CLOSED表 。 若一個(gè)節(jié)點(diǎn)已是某節(jié)點(diǎn)的直系先輩節(jié)點(diǎn) ， 就不能再作為該節(jié)點(diǎn)的子節(jié)點(diǎn) 。 圖中各邊代價(jià)都相同 ， 都為一個(gè)單位量 ， 從而可用路徑的長度代替路徑的代價(jià) 。 ④ 擴(kuò)展 n。 寬度優(yōu)先搜索的數(shù)據(jù)結(jié)構(gòu) OPEN表 ? 包含已生成但子節(jié)點(diǎn)未被搜索的節(jié)點(diǎn) 。 由于適用于一個(gè)節(jié)點(diǎn)的算符可能有多個(gè) ， 此時(shí)就會(huì)生成一組子節(jié)點(diǎn) 。 – G中每個(gè)節(jié)點(diǎn) （ S除外 ） 都有且僅有一個(gè)指向 G中一個(gè)父節(jié)點(diǎn)的指針 。 ⑧ 按某種方式或按某個(gè)試探值 ， 重排 OPEN表； ⑨ 轉(zhuǎn)第 ③ 步 。 – 特點(diǎn)：優(yōu)先選取合適的操作算子 ， 減少不必要搜索 ， 提高效率 啟發(fā)式搜索一般優(yōu)于盲目搜索 ， 但不能過于追求更多的甚至更完整的啟發(fā)信息 。 ? 盲目搜索 – 對特定問題不具有任何有關(guān)信息 ， 按預(yù)定步驟 （ 依次或隨機(jī) ）進(jìn)行搜索 ， 搜索過程中獲得的中間信息不用來改進(jìn)控制策略 。 ? 不同搜索策略 ， 節(jié)點(diǎn)在 OPEN表中的排列順序不同 。 一般搜索過程的幾點(diǎn)說明 2. 搜索圖和搜索樹 ? 圖搜索的一般過程中生成的明確圖 ， 被稱為搜索圖 G 。 – 解是由從初始節(jié)點(diǎn)到該目標(biāo)節(jié)點(diǎn)路徑上的算符構(gòu)成 。 實(shí)心圓圈代表已擴(kuò)展節(jié)點(diǎn) ， 它們位于 CLOSED表中； 空心圓圈代表未擴(kuò)展節(jié)點(diǎn) ， 它們位于 OPEN表中； 有向邊旁的箭頭是指向父節(jié)點(diǎn)的指針 。 寬度優(yōu)先搜索 算法流程 ① 把起始節(jié)點(diǎn)放到 OPEN表中 ， 如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn) ， 則求得一個(gè)解答 。 如果問題無解 ， 對有限圖 ， 算法會(huì)失敗退出；對無限圖 ， 則永遠(yuǎn)不會(huì)終止 。 結(jié)論：在搜索樹中給每條邊都標(biāo)上代價(jià) 。 g(j)=g(i)+c(i, j) 代價(jià)樹的寬度優(yōu)先搜索算法流程 ① 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn)表 OPEN中 。 若 n不是目標(biāo)節(jié)點(diǎn) ， 搜索 n所有子節(jié)點(diǎn)以及子節(jié)點(diǎn)的后裔節(jié)點(diǎn) 。 深度界限 ? 為避免考慮太長路徑 ， 防止搜索沿著無益路徑擴(kuò)展 ， 往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度 ， 稱為深度界限 。 ⑤ 擴(kuò)展 n， 產(chǎn)生其全部后裔 ， 并把它們放入 OPEN表的前頭 。 ② 如果 OPEN是個(gè)空表 ， 則沒有解 ， 失敗退出 。 啟發(fā)式策略 的應(yīng)用場合 由于在問題陳述和數(shù)據(jù)獲取方面固有的模糊性 ， 可能使問題沒有一個(gè)確定解 ， 即它是一個(gè) 模糊系統(tǒng) 。 h(n)： 啟發(fā)函數(shù) ? 從 n到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià) 。 有序搜索總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn) 。 對 i的每個(gè)后繼節(jié)點(diǎn) j： a) 計(jì)算 f(j)。 f(i)定義為從起始節(jié)點(diǎn)至 i的代價(jià) ， 則退化為代價(jià)樹的寬度優(yōu)先搜索 。 A*算法流程 ① 把 S放入 OPEN表 ， 記 f =h， 令 CLOSED為空表 。 c) 如果 SUCCESSOR?OPEN， 則稱此節(jié)點(diǎn)為 OLD， 把它添至BESTNODE的后繼節(jié)點(diǎn)表中 。 ? A*算法是可納的 ， 它能在有限步內(nèi)終止并找到最優(yōu)解 。 。 ⑦ 計(jì)算 f值 ， 轉(zhuǎn)第 (2)步 。 ⑥ 對每個(gè) SUCCESSOR進(jìn)行下列過程： A*算法 a) 建立從 SUCCESSOR返回 BESTNODE的指針
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1