[工學(xué)]狀態(tài)空間的搜索策略-文庫吧
2025-01-04 11:37 本頁面
【正文】 2. 搜索圖和搜索樹 ? 圖搜索的一般過程中生成的明確圖 ， 被稱為搜索圖 G 。 ? 由圖 G中所有節(jié)點(diǎn)及反向指針 （ 在第 ⑦ 步 形成的指向父節(jié)點(diǎn)的指針 ） 構(gòu)成的集合 T， 是一棵樹 ， 稱為搜索樹 。 – 擴(kuò)展某節(jié)點(diǎn)時(shí)圖 G已保存了從初始節(jié)點(diǎn)到該節(jié)點(diǎn)的搜索樹 。 – G中每個(gè)節(jié)點(diǎn) （ S除外 ） 都有且僅有一個(gè)指向 G中一個(gè)父節(jié)點(diǎn)的指針 。 – OPEN表上的節(jié)點(diǎn)都是搜索圖上未被擴(kuò)展的端節(jié)點(diǎn) 。 – CLOSED表上的節(jié)點(diǎn) ， 或者是已被擴(kuò)展但沒有生成后繼節(jié)點(diǎn)的端節(jié)點(diǎn) ， 或者是搜索樹的非端節(jié)點(diǎn) 。 一般搜索過程的幾點(diǎn)說明 3. 搜索過程終止條件 ? 在第 ⑤ 步 ， 當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí) ， 搜索過程成功結(jié)束 ， 得到了一個(gè)解 。 – 從目標(biāo)節(jié)點(diǎn)按指向父節(jié)點(diǎn)的指針 （ 第 ⑦ 步形成 ） 不斷回溯 ，能重現(xiàn)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的成功路徑 。 – 解是由從初始節(jié)點(diǎn)到該目標(biāo)節(jié)點(diǎn)路徑上的算符構(gòu)成 。 ? 當(dāng)搜索樹不再有末被擴(kuò)展的端節(jié)點(diǎn)時(shí) ， 即 OPEN表為空 ，搜索過程失敗 ， 從初始節(jié)點(diǎn)達(dá)不到目標(biāo)節(jié)點(diǎn) 。 一般搜索過程的幾點(diǎn)說明 4. 步驟 ⑥ 的說明 一個(gè)節(jié)點(diǎn)經(jīng)一個(gè)算符操作通常指生成一個(gè)子節(jié)點(diǎn) 。 由于適用于一個(gè)節(jié)點(diǎn)的算符可能有多個(gè) ， 此時(shí)就會生成一組子節(jié)點(diǎn) 。 判斷子節(jié)點(diǎn)是否是當(dāng)前擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn) 、 祖父節(jié)點(diǎn)等 ， 若是 ， 則刪除 。 余下的子節(jié)點(diǎn)記做集合 M， 加入圖 G中 。 擴(kuò)展節(jié)點(diǎn)時(shí) ， 生成該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn) 。 一般搜索過程的幾點(diǎn)說明 5. 步驟 ⑦ 的說明 ? 問題： 一個(gè)新生成的節(jié)點(diǎn) ， 若已作為其他節(jié)點(diǎn)的后繼節(jié)點(diǎn)被生成過 ， 該新節(jié)點(diǎn)應(yīng)作為哪個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn) ？ ? 解決方法： 一般由初始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的 代價(jià) 來決定 ，那條路經(jīng)付出的代價(jià)小 ， 相應(yīng)的節(jié)點(diǎn)就作為父節(jié)點(diǎn) 。 實(shí)心圓圈代表已擴(kuò)展節(jié)點(diǎn) ， 它們位于 CLOSED表中； 空心圓圈代表未擴(kuò)展節(jié)點(diǎn) ， 它們位于 OPEN表中； 有向邊旁的箭頭是指向父節(jié)點(diǎn)的指針 。 設(shè)有向弧兩端節(jié)點(diǎn)間的代價(jià)都為 1 4 4 5 2 4 3 5 常見的幾種盲目搜索策略 回溯策略 寬度優(yōu)先搜索 （ 廣度優(yōu)先搜索 ） 深度優(yōu)先搜索 代價(jià)樹的寬度優(yōu)先搜索 代價(jià)樹的深度優(yōu)先搜索 寬度優(yōu)先搜索基本思想 從初始節(jié)點(diǎn)開始 ， 逐層對節(jié)點(diǎn)進(jìn)行擴(kuò)展 ， 并考察它是否為目標(biāo)節(jié)點(diǎn) 。 在第 n層節(jié)點(diǎn)沒有全部擴(kuò)展并考察之前 ， 不對第n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展 。 寬度優(yōu)先搜索的數(shù)據(jù)結(jié)構(gòu) OPEN表 ? 包含已生成但子節(jié)點(diǎn)未被搜索的節(jié)點(diǎn) 。 ? 表中節(jié)點(diǎn)的排列次序就是搜索的次序 。 ? OPEN表采用 先進(jìn)先出的隊(duì)列結(jié)構(gòu) 。 CLOSED表 ? 記錄已被生成擴(kuò)展過的節(jié)點(diǎn) 。 ? 相當(dāng)于回溯算法中 PS表和 NSS表的合并 。 寬度優(yōu)先搜索 算法流程 ① 把起始節(jié)點(diǎn)放到 OPEN表中 ， 如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn) ， 則求得一個(gè)解答 。 ② 若 OPEN是空表 ， 則沒有解 ， 失敗退出；否則繼續(xù) 。 ③ 把第一個(gè)節(jié)點(diǎn) （ 節(jié)點(diǎn) n） 從 OPEN表移出 ， 并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中 。 ④ 擴(kuò)展 n。 如果沒有后繼節(jié)點(diǎn) ， 則轉(zhuǎn)向步驟 ② 。 ⑤ 把 n的所有后繼節(jié)點(diǎn)放到 OPEN表的末端 ， 并提供從這些后繼節(jié)點(diǎn)回到 n的指針 。 ⑥ 如果 n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn) ， 則找到一個(gè)解答 ， 成功退出；否則轉(zhuǎn)向步驟 ② ； 盲目搜索策略 —— 寬度優(yōu)先搜索 寬度優(yōu)先搜索算法的幾點(diǎn)說明 刪除 OPEN或 CLOSED表中出現(xiàn)過的子狀態(tài) ， 避免循環(huán)搜索 。 只要問題有解 ， 總能找到最短解題路徑 。 如果問題無解 ， 對有限圖 ， 算法會失敗退出；對無限圖 ， 則永遠(yuǎn)不會終止 。 寬度優(yōu)先搜索算法的缺陷 盲目性較大 ， 當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn) ， 會產(chǎn)生許多無用節(jié)點(diǎn) ， 搜索效率低 。 因此 ， 當(dāng)圖中分枝數(shù)太多 ， 實(shí)用意義不大 。 圖中各邊代價(jià)都相同 ， 都為一個(gè)單位量 ， 從而可用路徑的長度代替路徑的代價(jià) 。 然而 ， 對許多問題這種假設(shè)是不現(xiàn)實(shí)的 ， 即 狀態(tài)空間中各邊的代價(jià)不可能完全相同 。 代價(jià)樹的寬度優(yōu)先搜索算法 啟發(fā)式搜索算法 代價(jià)樹的寬度優(yōu)先搜索算法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1