第三章狀態(tài)空間搜索策略-在線瀏覽
2024-12-14 12:54本頁面
【正文】 有解，并成功退出。 (6)擴展節(jié)點 n生成一組不是 n的祖先的后繼節(jié)點，并將它們記為集合 M，將 M中的這些節(jié)點作為 n的后繼節(jié)點加入圖 G中。 (8)按某一任意方式或按某種策略重排 OPEN表中節(jié)點的順序 。 算法 狀態(tài)空間圖的一般搜索算法 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 ?在搜索過程中，生成了一個圖 G， 它是問題狀態(tài)空間圖的一部分 ，稱為 搜索圖 。 ?在搜索過程中，問題的 解 就是從初始節(jié)點 So到目標節(jié)點 路徑 上的 算符所構(gòu)成的序列 。 第三章 狀態(tài)空間搜索策略 寬度優(yōu)先搜索策略 寬度優(yōu)先搜索 又稱為 廣度優(yōu)先搜索 。 在對下層節(jié)點進行擴展(或搜索 )之前 ， 必須完成對當前層的所有節(jié)點的擴展 (或搜索 )。 第三章 狀態(tài)空間搜索策略 算法 狀態(tài)空間圖的寬度優(yōu)先搜索算法 (1)把初始節(jié)點 S0放人 OPEN表中。 (3)把 OPEN表中的第一個節(jié)點 (記為節(jié)點 n)移出，并放人CLOSED表中。 (5)若節(jié)點 n不可擴展，轉(zhuǎn)第 (2)步；否則繼續(xù)執(zhí)行 (6)步。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 例 八數(shù)碼難題 ：設(shè)在 3 3的一個方格棋盤上 ， 擺放著 8個數(shù)碼 8， 有一個方格是 空格 ， 其初始狀態(tài)如下圖 (a)所示 ， 要求對空格執(zhí)行下列的操作 (或算符 )： 左移 ， 上移 ， 右移 ， 下移 。 要求尋找從初始狀態(tài)到目標狀態(tài)的路徑 。 當目標節(jié)點距離初始節(jié)點較遠時，將會產(chǎn)生大量的無用節(jié)點。 只要問題有解，寬度優(yōu)先搜索總可以找到它的解，而且是搜索樹中，從初始節(jié)點到目標節(jié)點的路徑最短的解。 即從初始節(jié)點 So開始 ，在其后繼節(jié)點中選擇一個節(jié)點 ， 對其進行考察 ， 若它不是目標節(jié)點 ， 則對該節(jié)點進行擴展 ， 并再從它的后繼節(jié)點中選擇一個節(jié)點進行考察 。 當?shù)竭_某個既非目標節(jié)點又無法繼續(xù)擴展的節(jié)點時 ，才選擇其兄弟節(jié)點進行考察 。 深度優(yōu)先搜索 第三章 狀態(tài)空間搜索策略 算法 狀態(tài)空間圖的深度優(yōu)先搜索算法 (1)把初始節(jié)點 S0放人 OPEN表； (2)如果 OPEN表為空 ， 則問題無解 ， 退出； (3)從 OPEN表中將其第一個節(jié)點 (節(jié)點 n)移出 ， 放入已擴展節(jié)點表 CLOSED中； (4)考察節(jié)點 n是否為目標節(jié)點 ， 若是 ， 則找到問題的解 ，用 回溯法 求解的路徑 ， 退出； (5)若節(jié)點 n不可擴展 ， 則轉(zhuǎn)第 (2)步； (6)擴展節(jié)點 n ， 將 其后繼節(jié)點放到 OPEN表的 前端 ， 并為其設(shè)置指向節(jié)點 n的指針 ， 然后轉(zhuǎn)第 (2)步 。 ?寬度優(yōu)先搜索 是將后繼節(jié)點放入 OPEN表的 末端 ——“先入先出 ” 。 第三章 狀態(tài)空間搜索策略 例 對例 ，利用深度優(yōu)先方法進行搜索求解問題。 搜索若進入某一分支，則沿著這一分支一直搜索下去，對于有限的狀態(tài)空間圖，從理論上講，解總是能夠找到的。 由于某些分支可能擴展得很深，而解又不在這些分支上，這就無疑會降低搜索的效率。 任何節(jié)點如果達到了 深度界限 ，就把它作為沒有后繼節(jié)點進行處理，而對另一個分支進行搜索。 (2)任何 其他節(jié)點 的深度等于其 父輩節(jié)點 的深度加上 1。 (2)如果 OPEN表為空，則問題無解，退出。 (4)考察節(jié)點 n是否為目標節(jié)點，若是，則求得問題的解，退出；否則繼續(xù)執(zhí)行第 (5)步。 (6)如果節(jié)點 n不可擴展，即沒有后繼節(jié)點，則轉(zhuǎn)第 (2)步；否則繼續(xù)第 (7)步。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 例 設(shè)八數(shù)碼難題的初始狀態(tài)及目標狀態(tài)分別如下圖 (a)和圖 (b)所示，試用有界深度優(yōu)先搜索策略求解問題。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 ?有界深度優(yōu)先搜索算法的 深度界限的選擇很重要 。 ?有界深度優(yōu)先 搜索策略是不完備的 。 第三章 狀態(tài)空間搜索策略 搜索代價問題 ：在實際問題的搜索求解中，在將一個狀態(tài)變換成另一個狀態(tài)時，往往所付出的 操作代價 (或費用 )是不一樣的，也就是狀態(tài)空間圖中各 有向邊的代價 是不一樣的。 代價樹的寬度優(yōu)先搜索 代價樹 ：把 有向邊 上標有 代價 的搜索樹稱為 代價搜索樹 ，簡稱 代價樹 。 代價樹寬度優(yōu)先搜索的 基本思想 ：每次從 OPEN表中選擇一個 代價最小 的節(jié)點，移入 CLOSED表。 (2)如果 OPEN表為空，則問題無解，退出。 (4)如果節(jié)點 n是目標節(jié)點，則求得問題的解，退出，否則繼續(xù)。 (6)對節(jié)點 n進行擴展，將它們所有的后繼節(jié)點放入 OPEN表中，并對每個 后繼節(jié)點 j計算其代價 g(j)=g(i)+C(i， j)，為每個后繼節(jié)點設(shè)置指向 n節(jié)點的指針，然后，根據(jù)節(jié)點的代價大小對 OPEN表中的 所有 節(jié)點進行從小到大的排序 。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 例 推銷員旅行問題 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1