[工學(xué)]狀態(tài)空間的搜索策略(已改無錯字)
2023-02-19 11:37:39 本頁面
【正文】 把 OPEN表中第一個節(jié)點 n取出 ， 放入 CLOSED表 。 ④ 如果 n是目標(biāo)節(jié)點 ， 則求得問題的解 ， 退出 。 ⑤ 若 n不可擴(kuò)展 ， 則轉(zhuǎn)第 (2)步 。 ⑥ 擴(kuò)展 n， 將其子節(jié)點按邊代價從小到大的順序放入 OPEN表 ， 并配置指向父節(jié)點的指針 ， 然后轉(zhuǎn)第 ② 步 。 代價樹的深度優(yōu)先搜索示例 代價樹的寬度優(yōu)先搜索最優(yōu)解為： A ?B1 ?E1 代價為： 9 OPEN表 狀態(tài)節(jié)點 A C1B1 D1B1 E2B2B1 COLSE表 狀態(tài)節(jié)點 A C1A D1C1A E2D1C1A 代價樹的深度優(yōu)先搜索最優(yōu)解為： A ?C1 ? D1? E2 代價為： 13 盲目搜索存在的問題 擴(kuò)展節(jié)點數(shù)目較多 。 效率低 ， 耗費過多的計算時間和空間 。 解決方案：選擇最有希望的節(jié)點擴(kuò)展 。 啟發(fā)式策略 的應(yīng)用場合 由于在問題陳述和數(shù)據(jù)獲取方面固有的模糊性 ， 可能使問題沒有一個確定解 ， 即它是一個 模糊系統(tǒng) 。 一個問題可能有確定解 ， 但 求解過程中的搜索代價太大 。 啟發(fā)搜索通常由兩部分組成： ? 啟發(fā)方法 ? 使用該方法搜索狀態(tài)空間的算法 注意： 啟發(fā)式搜索可能得到一個次最佳解 ， 也可能無解 ， 這是由其固有局限性決定的 ， 不能通過 “ 更好 ”的啟發(fā)式策略來克服 。 啟發(fā)信息 指導(dǎo)搜索過程 ， 與具體問題求解有關(guān)的控制性信息 。 陳述性 更準(zhǔn)確精練地描述狀態(tài) ， 使?fàn)顟B(tài)空間縮小 。 過程性 構(gòu)造操作算子 ， 使操作算子少而精 。 控制性： 一般被反映在估價函數(shù)之中 關(guān)于控制策略方面的知識 ， 包括協(xié)調(diào)整個問題求解過程中所使用的各種處理方法 、 搜索策略 、 控制結(jié)構(gòu)等有關(guān)知識 。 估價函數(shù) f(n) f(n)是從初始節(jié)點經(jīng)過節(jié)點 n到達(dá)目標(biāo)節(jié)點的路徑的最小代價估計值 ， 其一般形式是： f(n)=g(n)+h(n) g(n)： 從初始節(jié)點到 n的實際代價； ? g(n)在 f(n)所占比重較大 ， 越傾向于寬度優(yōu)先搜索方式 ， 它有利于搜索完備性 ， 但影響搜索效率 。 h(n)： 啟發(fā)函數(shù) ? 從 n到目標(biāo)節(jié)點的最佳路徑的估計代價 。 ? h(n)的比重越大 ， 表示啟發(fā)性能越強 估價函數(shù)的選擇 一個節(jié)點處在最佳路徑上的概率 。 求出任意一個節(jié)點與目標(biāo)節(jié)點集之間的距離度量或差異度量 。 根據(jù)格局 （ 如博弈問題 ） 或狀態(tài)的特點來計算 。 啟發(fā)式與寬度 /深度優(yōu)先搜索的異同 相同處 都使用了兩張表來記錄狀態(tài)信息 。 ? OPEN表中保留所有已生成而未擴(kuò)展的節(jié)點； ? CLOSED表中記錄已擴(kuò)展過的節(jié)點 。 不同處： ? 啟發(fā)式： OPEN表按節(jié)點的啟發(fā)估價函數(shù)值的大小排列 ， ? 深度 /寬度：隊列或堆棧的數(shù)據(jù)結(jié)構(gòu) 。 有序搜索算法（ A算法）的基本思想 應(yīng)用某個算法選擇 OPEN表上具有最小 f值的節(jié)點作為下一個要擴(kuò)展的節(jié)點 ， 這種搜索方法叫做有序搜索（ 最佳優(yōu)先搜索 ） 。 有序搜索總是選擇最有希望的節(jié)點作為下一個要擴(kuò)展的節(jié)點 。 有序搜索算法流程 ① 把起始節(jié)點 S放到 OPEN表中 ， 計算 f(S)， 并把值與 S聯(lián)系起來 。 ② 如果 OPEN表是個空表 ， 則失敗退出 ， 無解 。 ③ 從 OPEN表中選擇一個 f值最小的節(jié)點 i。 如果有多個節(jié)點滿足這一要求 ， 且其中有一個為目標(biāo)節(jié)點 ， 則選擇它作為 i ；否則就選擇其中任意一個節(jié)點作為 i。 ④ 把 i 從 OPEN表中移出 ， 并放入 CLOSED表中 。 ⑤ 如果 i是個目標(biāo)節(jié)點 ， 則成功退出 ， 求得一個解 。 有序搜索算法流程 ⑥ 擴(kuò)展 i， 生成其全部后繼節(jié)點 。 對 i的每個后繼節(jié)點 j： a) 計算 f(j)。 b) 如果 j不在 OPEN和 CLOSED表中 ， 則用 f(j)把它添入 OPEN表 ， 并為 j設(shè)置指向 i的指針 。 c) 若 j已在 OPEN或 CLOSED表上 ， 則比較 f(j)和前面計算過的該節(jié)點在表中的 f(j)old值 。 若 f(j)較小 ， 則： I. 以 f(j) 取代 f(j)old。 II. 修正 j的父指針 ， 使其指向 i。 III. 若 j在 CLOSED表中 ， 把它移回 OPEN表 。 ⑦ 轉(zhuǎn)向 ② 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1