[工學]狀態(tài)空間的搜索策略-文庫吧資料
2025-01-25 11:37本頁面
【正文】 ， 解答路徑也不一定是最短路徑 。 深度界限 ? 為避免考慮太長路徑 ， 防止搜索沿著無益路徑擴展 ， 往往給出一個節(jié)點擴展的最大深度 ， 稱為深度界限 。 有界深度優(yōu)先搜索 節(jié)點深度定義 ? 起始節(jié)點 （ 即根節(jié)點 ） 的深度為 0。 因此 ， 深度優(yōu)先搜索是不完備的 。 深度與寬度優(yōu)先搜索的不同 寬度 深度 OPEN表 先進先出的隊列結(jié)構(gòu) 先進后出的堆棧結(jié)構(gòu) 最優(yōu)解 總能找到最短解題路徑 不一定能找到最優(yōu)解 深度優(yōu)先搜索的缺陷及解決方法 搜索一旦進入某個分支 ， 就沿著該分支一直向下搜索 。 若 n不是目標節(jié)點 ， 搜索 n所有子節(jié)點以及子節(jié)點的后裔節(jié)點 。 ⑥ 擴展 n， 將其子節(jié)點放入 OPEN表 ， 并配置指向父節(jié)點的指針；計算各子節(jié)點的代價 ， 按代價對 OPEN表中全部節(jié)點從小到大進行排序 ， 然后轉(zhuǎn)第 ② 步 。 ④ 如果 n是目標節(jié)點 ， 則求得問題的解 ， 退出 。 ② 如果 OPEN是個空表 ， 則沒有解 ， 失敗退出 。 g(j)=g(i)+c(i, j) 代價樹的寬度優(yōu)先搜索算法流程 ① 把起始節(jié)點 S放到未擴展節(jié)點表 OPEN中 。 相關(guān)記號 若節(jié)點 j是 i的子女 ， c(i, j)： 從 i到 j的連接弧線代價 。 除 A外 ， 其它節(jié)點可能在代價樹中多次出現(xiàn) 。 對其他節(jié)點作相同處理 。 結(jié)論：在搜索樹中給每條邊都標上代價 。 設有 5個城市 , 它們之間的交通路線如圖所示 ， 圖中的數(shù)字表示兩個城市之間的交通費用 ，即代價 。 然而 ， 對許多問題這種假設是不現(xiàn)實的 ， 即 狀態(tài)空間中各邊的代價不可能完全相同 。 因此 ， 當圖中分枝數(shù)太多 ， 實用意義不大 。 如果問題無解 ， 對有限圖 ， 算法會失敗退出；對無限圖 ， 則永遠不會終止 。 ⑥ 如果 n的任一個后繼節(jié)點是個目標節(jié)點 ， 則找到一個解答 ， 成功退出；否則轉(zhuǎn)向步驟 ② ； 盲目搜索策略 —— 寬度優(yōu)先搜索 寬度優(yōu)先搜索算法的幾點說明 刪除 OPEN或 CLOSED表中出現(xiàn)過的子狀態(tài) ， 避免循環(huán)搜索 。 如果沒有后繼節(jié)點 ， 則轉(zhuǎn)向步驟 ② 。 ③ 把第一個節(jié)點 （ 節(jié)點 n） 從 OPEN表移出 ， 并把它放入CLOSED的擴展節(jié)點表中 。 寬度優(yōu)先搜索 算法流程 ① 把起始節(jié)點放到 OPEN表中 ， 如果該起始節(jié)點為一目標節(jié)點 ， 則求得一個解答 。 CLOSED表 ? 記錄已被生成擴展過的節(jié)點 。 ? 表中節(jié)點的排列次序就是搜索的次序 。 在第 n層節(jié)點沒有全部擴展并考察之前 ， 不對第n+1層的節(jié)點進行擴展 。 實心圓圈代表已擴展節(jié)點 ， 它們位于 CLOSED表中； 空心圓圈代表未擴展節(jié)點 ， 它們位于 OPEN表中； 有向邊旁的箭頭是指向父節(jié)點的指針 。 擴展節(jié)點時 ， 生成該節(jié)點的所有后繼節(jié)點 。 判斷子節(jié)點是否是當前擴展節(jié)點的父節(jié)點 、 祖父節(jié)點等 ， 若是 ， 則刪除 。 一般搜索過程的幾點說明 4. 步驟 ⑥ 的說明 一個節(jié)點經(jīng)一個算符操作通常指生成一個子節(jié)點 。 – 解是由從初始節(jié)點到該目標節(jié)點路徑上的算符構(gòu)成 。 一般搜索過程的幾點說明 3. 搜索過程終止條件 ? 在第 ⑤ 步 ， 當被選作擴展的節(jié)點是目標節(jié)點時 ， 搜索過程成功結(jié)束 ， 得到了一個解 。 – OPEN表上的節(jié)點都是搜索圖上未被擴展的端節(jié)點 。 – 擴展某節(jié)點時圖 G已保存了從初始節(jié)點到該節(jié)點的搜索樹 。 一般搜索過程的幾點說明 2. 搜索圖和搜索樹 ? 圖搜索的一般過程中生成的明確圖 ， 被稱為搜索圖 G 。 ? 排序可以是任意的 ， 即肓目的 —— 盲目搜索 。 一般搜索過程 一般搜索過程的幾點說明 1. 搜索過程具有通用性 此后討論的各種搜索策略都可以看成是它的特例 。 OPEN表 狀態(tài)節(jié)點 父節(jié)點 COLSE表 編號 狀態(tài)節(jié)點 父節(jié)點 一般搜索過程算法流程 ① 建立只含有初始節(jié)點 S的 搜索圖 G， 把 S放到 OPEN表中； ② 建立 CLOSED表 ， 其初始值為空表； ③ 若 OPEN表是空表 ， 則失敗退出； ④ 選擇 OPEN表中第一個節(jié)點 ， 把它從 OPEN表移出并放進CLOSED表中 ， 稱此節(jié)點為節(jié)點 n； ⑤ 若 n為目標節(jié)點 ， 則
教學課件相關(guān)推薦
鄂ICP備17016276號-1