[工學(xué)]狀態(tài)空間的搜索策略-全文預(yù)覽
【正文】 啟發(fā)式策略 的應(yīng)用場(chǎng)合 由于在問(wèn)題陳述和數(shù)據(jù)獲取方面固有的模糊性 ， 可能使問(wèn)題沒(méi)有一個(gè)確定解 ， 即它是一個(gè) 模糊系統(tǒng) 。 ⑥ 擴(kuò)展 n， 將其子節(jié)點(diǎn)按邊代價(jià)從小到大的順序放入 OPEN表 ， 并配置指向父節(jié)點(diǎn)的指針 ， 然后轉(zhuǎn)第 ② 步 。 ② 如果 OPEN是個(gè)空表 ， 則沒(méi)有解 ， 失敗退出 。 但若解的路徑長(zhǎng)度 dm， 則得不到解 。 ⑤ 擴(kuò)展 n， 產(chǎn)生其全部后裔 ， 并把它們放入 OPEN表的前頭 。 如果此節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn) ，則得到一個(gè)解 。 深度界限 ? 為避免考慮太長(zhǎng)路徑 ， 防止搜索沿著無(wú)益路徑擴(kuò)展 ， 往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度 ， 稱(chēng)為深度界限 。 因此 ， 深度優(yōu)先搜索是不完備的 。 若 n不是目標(biāo)節(jié)點(diǎn) ， 搜索 n所有子節(jié)點(diǎn)以及子節(jié)點(diǎn)的后裔節(jié)點(diǎn) 。 ④ 如果 n是目標(biāo)節(jié)點(diǎn) ， 則求得問(wèn)題的解 ， 退出 。 g(j)=g(i)+c(i, j) 代價(jià)樹(shù)的寬度優(yōu)先搜索算法流程 ① 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn)表 OPEN中 。 除 A外 ， 其它節(jié)點(diǎn)可能在代價(jià)樹(shù)中多次出現(xiàn) 。 結(jié)論：在搜索樹(shù)中給每條邊都標(biāo)上代價(jià) 。 然而 ， 對(duì)許多問(wèn)題這種假設(shè)是不現(xiàn)實(shí)的 ， 即 狀態(tài)空間中各邊的代價(jià)不可能完全相同 。 如果問(wèn)題無(wú)解 ， 對(duì)有限圖 ， 算法會(huì)失敗退出；對(duì)無(wú)限圖 ， 則永遠(yuǎn)不會(huì)終止 。 如果沒(méi)有后繼節(jié)點(diǎn) ， 則轉(zhuǎn)向步驟 ② 。 寬度優(yōu)先搜索 算法流程 ① 把起始節(jié)點(diǎn)放到 OPEN表中 ， 如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn) ， 則求得一個(gè)解答 。 ? 表中節(jié)點(diǎn)的排列次序就是搜索的次序 。 實(shí)心圓圈代表已擴(kuò)展節(jié)點(diǎn) ， 它們位于 CLOSED表中； 空心圓圈代表未擴(kuò)展節(jié)點(diǎn) ， 它們位于 OPEN表中； 有向邊旁的箭頭是指向父節(jié)點(diǎn)的指針 。 判斷子節(jié)點(diǎn)是否是當(dāng)前擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn) 、 祖父節(jié)點(diǎn)等 ， 若是 ， 則刪除 。 – 解是由從初始節(jié)點(diǎn)到該目標(biāo)節(jié)點(diǎn)路徑上的算符構(gòu)成 。 – OPEN表上的節(jié)點(diǎn)都是搜索圖上未被擴(kuò)展的端節(jié)點(diǎn) 。 一般搜索過(guò)程的幾點(diǎn)說(shuō)明 2. 搜索圖和搜索樹(shù) ? 圖搜索的一般過(guò)程中生成的明確圖 ， 被稱(chēng)為搜索圖 G 。 一般搜索過(guò)程 一般搜索過(guò)程的幾點(diǎn)說(shuō)明 1. 搜索過(guò)程具有通用性 此后討論的各種搜索策略都可以看成是它的特例 。 ? 不同搜索策略 ， 節(jié)點(diǎn)在 OPEN表中的排列順序不同 。 應(yīng)綜合考慮各種因素 ， 盡量使搜索系統(tǒng)的總開(kāi)銷(xiāo)較小 。 ? 盲目搜索 – 對(duì)特定問(wèn)題不具有任何有關(guān)信息 ， 按預(yù)定步驟 （ 依次或隨機(jī) ）進(jìn)行搜索 ， 搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略 。 已提出的搜索策略 求任一解路的搜索策略 ? 爬山法 （ Hill Climbing） 、 深度優(yōu)先法 （ Depthfirst） 、 限定范圍搜索法 （ Beam Search） 、 回溯法 （ Backtracking） 、 最好優(yōu)先法 （ Bestfirst） 求最佳解路的搜索策略 ? 寬度優(yōu)先法 （ Breadthfirst ） 、 分枝界限法 （ Branch and Bound） 、 動(dòng)態(tài)規(guī)劃法 （ Dynamic Programming） 、 最佳圖搜索法 （ A*） 求與或關(guān)系解圖的搜索法 ? 一般的與或圖搜索法 （ AO*） 、 極大極小法 （ Minima） 、 ??剪枝法 （ Alphabeta Pruning） 、 啟發(fā)式剪枝法 （ Heuristic Pruning） 搜索策略選取操作算子的方式 搜索策略的主要任務(wù)是確定選取操作算子的方式 。 – 特點(diǎn)：優(yōu)先選取合適的操作算子 ， 減少不必要搜索 ， 提高效率 啟發(fā)式搜索一般優(yōu)于盲目搜索 ， 但不能過(guò)于追求更多的甚至更完整的啟發(fā)信息 。 ? 存放剛生成的節(jié)點(diǎn) 。 ⑧ 按某種方式或按某個(gè)試探值 ， 重排 OPEN表； ⑨ 轉(zhuǎn)第 ③ 步 。 ? 可以用啟發(fā)信息為依據(jù) —— 啟發(fā)式搜索 。 – G中每個(gè)節(jié)點(diǎn) （ S除外 ） 都有且僅有一個(gè)指向 G中一個(gè)父節(jié)點(diǎn)的指針 。 – 從目標(biāo)節(jié)點(diǎn)按指向父節(jié)點(diǎn)的指針 （ 第 ⑦ 步形成 ） 不斷回溯 ，能重現(xiàn)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的成功路徑 。 由于適用于一個(gè)節(jié)點(diǎn)的算符可能有多個(gè) ， 此時(shí)就會(huì)生成一組子節(jié)點(diǎn) 。 一般搜索過(guò)程的幾點(diǎn)說(shuō)明 5. 步驟 ⑦ 的說(shuō)明 ? 問(wèn)題： 一個(gè)新生成的節(jié)點(diǎn) ， 若已作為其他節(jié)點(diǎn)的后繼節(jié)點(diǎn)被生成過(guò) ， 該新節(jié)點(diǎn)應(yīng)作為哪個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn) ？ ? 解決方法：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1