[工學(xué)]狀態(tài)空間的搜索策略(編輯修改稿)
2025-02-15 11:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的引入 例：城市交通問(wèn)題 。 設(shè)有 5個(gè)城市 , 它們之間的交通路線如圖所示 ， 圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用 ，即代價(jià) 。 求從 A市出發(fā)到 E市 ， 費(fèi)用最小的交通路線 。 結(jié)論：在搜索樹中給每條邊都標(biāo)上代價(jià) 。 生成代價(jià)樹的方法 從初始節(jié)點(diǎn) A開始 ， 把與 A直接相鄰的節(jié)點(diǎn)作為子節(jié)點(diǎn) 。 對(duì)其他節(jié)點(diǎn)作相同處理 。 若一個(gè)節(jié)點(diǎn)已是某節(jié)點(diǎn)的直系先輩節(jié)點(diǎn) ， 就不能再作為該節(jié)點(diǎn)的子節(jié)點(diǎn) 。 除 A外 ， 其它節(jié)點(diǎn)可能在代價(jià)樹中多次出現(xiàn) 。 為便于區(qū)分 ， 用下標(biāo) 1, 2, …… 標(biāo)出 。 相關(guān)記號(hào) 若節(jié)點(diǎn) j是 i的子女 ， c(i, j)： 從 i到 j的連接弧線代價(jià) 。 g(i)： 從起始節(jié)點(diǎn) S到 i的路徑代價(jià) ， 即從 S到 i的最少代價(jià)路徑上的代價(jià) 。 g(j)=g(i)+c(i, j) 代價(jià)樹的寬度優(yōu)先搜索算法流程 ① 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn)表 OPEN中 。 如果 S為一目標(biāo)節(jié)點(diǎn) ， 則求得一個(gè)解；否則令 g(S)=0。 ② 如果 OPEN是個(gè)空表 ， 則沒(méi)有解 ， 失敗退出 。 ③ 把 OPEN表中第一個(gè)節(jié)點(diǎn) n取出 ， 放入 CLOSED表 。 ④ 如果 n是目標(biāo)節(jié)點(diǎn) ， 則求得問(wèn)題的解 ， 退出 。 ⑤ 若 n不可擴(kuò)展 ， 則轉(zhuǎn)第 (2)步 。 ⑥ 擴(kuò)展 n， 將其子節(jié)點(diǎn)放入 OPEN表 ， 并配置指向父節(jié)點(diǎn)的指針；計(jì)算各子節(jié)點(diǎn)的代價(jià) ， 按代價(jià)對(duì) OPEN表中全部節(jié)點(diǎn)從小到大進(jìn)行排序 ， 然后轉(zhuǎn)第 ② 步 。 代價(jià)樹的寬度優(yōu)先搜索示例 最優(yōu)解為： A ?B1 ?E1 代價(jià)為： 9 OPEN表 狀態(tài)節(jié)點(diǎn) A C1B1 B1D1 D2E1D1 E1D1E3C2 COLSED表 狀態(tài)節(jié)點(diǎn) A C1A B1C1A D2B1C1A E1D2B1C1A 深度優(yōu)先搜索的基本思想 從初始節(jié)點(diǎn)開始 ， 在其子節(jié)點(diǎn)中選擇一個(gè)進(jìn)行考察 ，記為子節(jié)點(diǎn) n。 若 n不是目標(biāo)節(jié)點(diǎn) ， 搜索 n所有子節(jié)點(diǎn)以及子節(jié)點(diǎn)的后裔節(jié)點(diǎn) 。 當(dāng)?shù)竭_(dá)某個(gè)子節(jié)點(diǎn) ， 該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展 ， 才選擇 n的兄弟節(jié)點(diǎn)進(jìn)行考察 。 深度與寬度優(yōu)先搜索的不同 寬度 深度 OPEN表 先進(jìn)先出的隊(duì)列結(jié)構(gòu) 先進(jìn)后出的堆棧結(jié)構(gòu) 最優(yōu)解 總能找到最短解題路徑 不一定能找到最優(yōu)解 深度優(yōu)先搜索的缺陷及解決方法 搜索一旦進(jìn)入某個(gè)分支 ， 就沿著該分支一直向下搜索 。 如果目標(biāo)節(jié)點(diǎn)不在此分支上 ， 且該分支又是一個(gè)無(wú)窮分支 ， 則不可能得到解 。 因此 ， 深度優(yōu)先搜索是不完備的 。 為了防止搜索沿著一條路徑無(wú)限地?cái)U(kuò)展下去 ， 深度優(yōu)先搜索常設(shè)定 深度限制值 ， 即有界深度優(yōu)先搜索 。 有界深度優(yōu)先搜索 節(jié)點(diǎn)深度定義 ? 起始節(jié)點(diǎn) （ 即根節(jié)點(diǎn) ） 的深度為 0。 ? 其他節(jié)點(diǎn)的深度等于其父節(jié)點(diǎn)的深度加 1。 深度界限 ? 為避免考慮太長(zhǎng)路徑 ， 防止搜索沿著無(wú)益路徑擴(kuò)展 ， 往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度 ， 稱為深度界限 。 ? 若達(dá)到深度界限 ， 對(duì)任何節(jié)點(diǎn)都認(rèn)為它們沒(méi)有后繼節(jié)點(diǎn) 。 采用深度界限后 ， 解答路徑也不一定是最短路徑 。 有界深度優(yōu)先搜索算法流程 ① 把起始節(jié)點(diǎn) S放到 OPEN表中 。 如果此節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn) ，則得到一個(gè)解 。 ② 如果 OPEN為空表 ， 則失敗退出 。 ③ 把第一個(gè)節(jié)點(diǎn) （ 節(jié)點(diǎn) n） 從 OPEN表移到 CLOSED表 。 ④ 如果 n的深度等于最大深度 dm， 則轉(zhuǎn)向步驟 ② 。 ⑤ 擴(kuò)展 n， 產(chǎn)生其全部后裔 ， 并把它們放入 OPEN表的前頭 。如果沒(méi)有后裔 ， 則轉(zhuǎn)向步驟 ② 。 ⑥ 如果后繼節(jié)點(diǎn)中有任一個(gè)為目標(biāo)節(jié)點(diǎn) ， 則求得一個(gè)解 ，成功退出；否則 ， 轉(zhuǎn)向步驟 ② 。 有界深度優(yōu)先搜索的幾點(diǎn)說(shuō)明 如果問(wèn)題有解 ， 且路徑長(zhǎng)度 ?dm， 則上述搜索過(guò)程一定能求得解 。 但若解的路徑長(zhǎng)度 dm， 則得不到解 。 為找到最優(yōu)解 ， 可增設(shè)表 R， 每找到一個(gè)目標(biāo)節(jié)點(diǎn) Sg后 ， 就把它放到 R的前面 ， 并令 dm等于該目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)的路徑長(zhǎng)度 ， 然后繼續(xù)搜索 。 代價(jià)樹的深度優(yōu)先搜索算法流程 ① 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn)表 OPEN中 。 如果 S為一目標(biāo)節(jié)點(diǎn) ， 則求得一個(gè)解；否則令 g(S)=0。 ② 如果 OPEN是個(gè)空表 ， 則沒(méi)有解 ， 失敗退出 。 ③
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1