第三章狀態(tài)空間搜索策略-資料下載頁
2025-10-02 12:54本頁面
【導(dǎo)讀】如果我們把該迷宮。一個(gè)有向圖表示。我們通過例子引入狀態(tài)空間搜索的概念。數(shù)碼，每個(gè)數(shù)碼占一格，且有一個(gè)空格。圖)，給出數(shù)碼的移動(dòng)序列。該問題稱為八數(shù)碼難題或重排。因此，研究狀態(tài)空間搜索具。度最小的求解路線。定的搜索控制策略進(jìn)行搜索。著最有希望的方向前進(jìn)，加速問題的求解，并找到最優(yōu)解。相關(guān)特性和信息難。搜索分為盲目搜索和啟發(fā)式搜索兩種。點(diǎn))，然后檢查這組后繼狀態(tài)中有沒有目標(biāo)狀態(tài)。生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或不再有可供操作的狀。態(tài)及算符時(shí)為止。OPEN的表中，而將已擴(kuò)展的節(jié)點(diǎn)存于一個(gè)名為CLOSED的表中。CLOSED表中存儲(chǔ)的是一棵不斷成長的搜索樹。組織在一起，并做某種排列，以便控制搜索的方向和順序。前待考查的節(jié)點(diǎn)。建立CLOSED表，且置為空表。題有解，并成功退出。圖G中沿著指針從n到S0的這條路徑得到。
【正文】 第 (2)步 。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 2．全局最佳優(yōu)先搜索 基本思想 ：在確定下一個(gè)擴(kuò)展節(jié)點(diǎn)時(shí)，在 OPEN表中的 全部節(jié)點(diǎn) 中選擇一個(gè)估價(jià)函數(shù)值 f(x)最小的節(jié)點(diǎn) ，作為下一個(gè)被考察的節(jié)點(diǎn)。類似于寬度優(yōu)先搜索。 第三章 狀態(tài)空間搜索策略 算法 全局最佳優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) So放入 OPEN表，計(jì)算 f(So)。 (2)如果 OPEN為空表，則問題無解，退出。 (3)把 OPEN表中第一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn) n移入 CLOSED表。 (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得問題的解，退出；否則轉(zhuǎn)第 (5)步。 (5)如果節(jié)點(diǎn) n可擴(kuò)展，轉(zhuǎn)第 (6)步；否則轉(zhuǎn)第 (2)步。 (6)對節(jié)點(diǎn) n進(jìn)行擴(kuò)展，并計(jì)算所有后繼節(jié)點(diǎn)的估價(jià)函數(shù) f(x)的值，并為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向 n的指針。 (7)把這些后繼節(jié)點(diǎn)都送入 OPEN表，然后對 OPEN表中的 全部節(jié)點(diǎn)按照估價(jià) f(x)值從小到大的順序排序 。 (8)轉(zhuǎn)第 (2)步。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 例 用全局最佳優(yōu)先搜索方法求解八數(shù)碼難題。初始狀態(tài)圖及目標(biāo)狀態(tài)圖分別如下圖 (a)和 (b)所示，試求由 So轉(zhuǎn)換為Sg的路徑。 第三章 狀態(tài)空間搜索策略 解 ：首先定義一個(gè)估價(jià)函數(shù)： f(x)=d(x)+h(x) d(x)：表示節(jié)點(diǎn) x在搜索樹中的 深度 ； h(x)：表示與節(jié)點(diǎn) x對應(yīng)的棋盤中 ， 與目標(biāo)節(jié)點(diǎn) Sg所對應(yīng)的棋盤中 棋子位置不同的個(gè)數(shù) 。 第三章 狀態(tài)空間搜索策略 1. A*算法的定義 A*算法 也是一種 啟發(fā)式搜索方法 ，它對 算法 擴(kuò)展節(jié)點(diǎn)選擇方法做了一些限制 ，選用了一個(gè)比較 特殊的估價(jià)函數(shù) 。這時(shí)的估價(jià)函數(shù) f(x)=g(x)+h(x)是對下列函數(shù) f*(x)=g*(x)+h*(x) 的一種 估計(jì)或近似 。即： ? f(x)是對 f*(x)的一種估計(jì)； ? g(x)是對 g*(x)的估計(jì)； ? h(x)是對 h*(x)的估計(jì)。 A*算法 第三章 狀態(tài)空間搜索策略 ? g*(x)：從節(jié)點(diǎn) So到節(jié)點(diǎn) x之間 最佳路徑 的 實(shí)際代價(jià) 。 ? h*(x)：從 x節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn) Sg的 最佳路徑 的 代價(jià) 。 ? f*(x)：表示從節(jié)點(diǎn) So到節(jié)點(diǎn) x的一條 最佳路徑 的 實(shí)際代價(jià)加上從節(jié)點(diǎn) x到目標(biāo)節(jié)點(diǎn) Sg的一條 最佳路徑 的 代價(jià) 之和 。 ? g(x) ：從初始節(jié)點(diǎn) So到節(jié)點(diǎn) x的 路徑代價(jià) ， 顯然恒有g(shù)(x)≥ g*(x)。 ? h(x) ：依賴于有關(guān)問題領(lǐng)域的啟發(fā)信息 。 第三章 狀態(tài)空間搜索策略 定義 如果在一般狀態(tài)空間圖的搜索算法 (算法 )中的第 (8)步 ， 依據(jù)估價(jià)函數(shù) f(x)=g(x)+h(x) 對 OPEN表中的節(jié)點(diǎn)進(jìn)行排序 ， 并且要求啟發(fā)函數(shù) h(x)是h*(x)的一個(gè)下界 ， 即 h(x)≤h *(x)， 則這種狀態(tài)空間圖的搜索算法就稱為 A*算法 。 如果對啟發(fā)函數(shù) h(x)， 不限制條件 h(x)≤h *(x)， 則這種狀態(tài)空間圖的搜索算法稱為 A算法 。 第三章 狀態(tài)空間搜索策略 ?在啟發(fā)式搜索中 ， 估價(jià)函數(shù) f(x)如果定義得不好 ， 則搜索算法不一定能 找到問題的解 。 即便找到解 ， 也不一定是 最優(yōu)解 。 ?A*啟發(fā)式搜索算法使用了特殊定義的估價(jià)函數(shù) ， 它要求啟發(fā)函數(shù) h(x) 是 h*(x) 的下界 ， 即對 所有 的 x 均 有： h(x)≤h*(x) 。 這一要求十分重要 ， 它能保證 A*算法找到最優(yōu)解 。 ?A*算法是對 算法 ， 它可以使問題的 求解更快速 、 更有效 。 第三章 狀態(tài)空間搜索策略 2. A*算法的性質(zhì) (1)可采納性 即對于可求解的狀態(tài)空間圖 (從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在 )來說， A*算法能在有限步內(nèi) 終止 ，并找到 最優(yōu)解 。 第三章 狀態(tài)空間搜索策略 (2)單調(diào)性 當(dāng)啟發(fā)函數(shù) h(x)滿足下面 限制條件 時(shí) ， 所擴(kuò)展的節(jié)點(diǎn)序列估價(jià)函數(shù) f(x)的值是 非遞減 的 ， 從而減少對 OPEN表或 CLOSED表的檢查和調(diào)整 ， 排序簡單 ， 提高搜索效率 。 ① 對所有的節(jié)點(diǎn) xi， 如果 xj是節(jié)點(diǎn) xi的任意子節(jié)點(diǎn) ， 有h(xi)h(xj)≤C(x i， xj)。 其中 C(xi， xj)是節(jié)點(diǎn) xi到節(jié)點(diǎn) xj的 有向邊代價(jià) 。 ② 目標(biāo)節(jié)點(diǎn) Sg 的啟發(fā)函數(shù)的值為 0， 即 h(Sg)=0。 第三章 狀態(tài)空間搜索策略 (3)信息性 A*算法的 搜索效率 主要取決于啟發(fā)函數(shù) h(x)， 在滿足h(x)≤h*(x) 的前提下 ， h(x)的值越大越好 。 h(x)的值越大 ，表明它攜帶與求解問題相關(guān)的啟發(fā)信息越多 ， 搜索過程就會(huì)在啟發(fā)信息指導(dǎo)下朝著目標(biāo)節(jié)點(diǎn)前進(jìn) ， 所擴(kuò)展的節(jié)點(diǎn)數(shù)就不會(huì)太多 ， 走的彎路少 ， 搜索效率就會(huì)提高 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1