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