ch5狀態(tài)空間搜索策略new(編輯修改稿)
2025-03-14 00:49 本頁面
【文章內(nèi)容簡介】 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 3 7 13 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 4 8 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 5 6 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 9 10 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 14 12 深度限制為 4 ?上面討論的搜索方法都沒有用到問題本身的特性信息，只是按事先設(shè)定的線路進(jìn)行搜索，具有較大的盲目性。事實上，如果能利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程，則對搜索將是非常有益的。這種利用問題自身的特性來引導(dǎo)搜索過程， 提高搜索效率 的搜索策略稱為 啟發(fā)式搜索 或 有信息搜索 。 ?啟發(fā)式搜索方法所依據(jù)的是問題自身的 啟發(fā)性信息 ，而啟發(fā)性信息又是通過 估價函數(shù) 而作用于搜索過程的 。 ? 啟發(fā)式算法 利用問題的特殊性，選擇待擴(kuò)展的節(jié)點，以縮小搜索范圍，提高搜索速度。 ? 啟發(fā)信息 可指導(dǎo)搜索過程，且與具體問題求解過程有關(guān)的控制性信息。一般有以下三種： ① 幫助確定擴(kuò)展節(jié)點的信息； ② 幫助決定哪些后繼節(jié)點應(yīng)被生成的信息； ③ 在擴(kuò)展一個節(jié)點時決定哪些節(jié)點應(yīng)被刪除的信息 ? 估價函數(shù) f(n)： 用于估計 節(jié)點代價 的函數(shù) 定義 為從初始節(jié)點 S0出發(fā)，經(jīng)過節(jié)點 n約束后，到達(dá)目標(biāo)節(jié)點 Sg的所有路徑中最優(yōu)路徑的代價估計值。 一般形式 為 f(n)=g(n)＋ h(n) g(n)是從初始節(jié)點 S0到節(jié)點 n的實際代價?？梢詮墓?jié)點 n反向跟蹤到初始節(jié)點 S0,得到一條當(dāng)前最小代價路徑，把這條路徑上所有有向邊的代價相加，就得到g(n)的值。 ； h(n)是從節(jié)點 n到目標(biāo)節(jié)點 S0的最優(yōu)路徑的估計代價。需要根據(jù)問題自身的特性來確定，體現(xiàn)了問題自身的啟發(fā)性信息，因此也稱為 啟發(fā)函數(shù) 。 估價函數(shù)例： f(n) = d(n) + W(n) 2 8 3 1 4 7 6 5 S0 節(jié)點 n在搜索樹中的深度 n中“不在位”的數(shù)碼個數(shù) f(S0) = ? = 0 + 3 = 3 1 2 3 8 4 7 6 5 Sg ? 根據(jù)搜索過程中選擇擴(kuò)展節(jié)點的范圍，分為全局擇優(yōu)搜索和局部擇優(yōu)搜索。 1. 全局擇優(yōu) 在 Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進(jìn)行擴(kuò)展 2. 局部擇優(yōu) 在剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進(jìn)行擴(kuò)展。 局部最佳優(yōu)先搜索算法 ? 對 OPEN表中所有節(jié)點的 f(n)進(jìn)行比較，按從小到大的順序重排 OPEN表。 ? 其算法效率類似于縱向搜索算法，但使用了與問題特性相關(guān)的估價函數(shù)來確定下一步待擴(kuò)展的節(jié)點，因此是一種啟發(fā)式搜索方法。 開始 把 S放入 OPEN表，計算估價函數(shù) f (s) OPEN表為空表？ 把 OPEN表中的第一個節(jié)點 n放入 CLOSED表 n為目標(biāo)節(jié)點嗎？ 擴(kuò)展 n，計算所有子節(jié)點的估價函數(shù)值，并提供它們返回節(jié)點 n的指針。 失敗 成功 局部最佳優(yōu)先搜索算法框圖 是 否 是 否 把子節(jié)點送入 OPEN表，并對其中的所有節(jié)點按估價函數(shù)值由小到大重排。 ? 舉例： 八數(shù)碼魔方（ 8puzzle problem） 1 2 3 8 4 5 6 7 （目標(biāo)狀態(tài)） 1 2 3 8 4 5 6 7 （初始狀態(tài)） 5 7 ① ④ ⑤ ⑥ ③ 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (5) (5) ② 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (4) (3) (3) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (2) (4) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (4) 1 2 3 8 4 5 6 7 (1) 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 (0) (2) 八數(shù)碼魔方的局部最佳優(yōu)先搜索樹 1 2 3 8 4 6 (4) ⑦ 搜索得到的路徑如黃線所示 ? 本題采用了簡單的估價函數(shù) f(n)=W(n) 其中： W(n)用來計算對應(yīng)于節(jié)點 n的數(shù)據(jù)庫中錯放的棋子個數(shù) 。 因此 ， 初始節(jié)點棋局 的 f(n)值等于 4。 1 2 3 8 4 5 6 7 ? 第 ② 步有三種情況 ,我們選擇其中f(n)最小的 : ? 其它依次類推 .最后用了 7步得出了結(jié)果 . 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (5) (5) ? ?最佳優(yōu)先算法有時無法得到最優(yōu)解，因為它的估價函數(shù) f的選取時，忽略了從初始節(jié)點到目前節(jié)點的代價值。所以，可考慮對估價函數(shù) f(n)進(jìn)行某些
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1