第三章狀態(tài)空間搜索策略-預(yù)覽頁
【正文】 面，還得不斷地把待考查的節(jié)點(diǎn)（ 未擴(kuò)展的節(jié)點(diǎn)）組織在一起，并做某種排列，以便 控制搜索的方向和順序 。 (3)判斷 OPEN表是否為空表，若為空，則問題無解，退出。 (6)擴(kuò)展節(jié)點(diǎn) n生成一組不是 n的祖先的后繼節(jié)點(diǎn)，并將它們記為集合 M，將 M中的這些節(jié)點(diǎn)作為 n的后繼節(jié)點(diǎn)加入圖 G中。 算法 狀態(tài)空間圖的一般搜索算法 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 ?在搜索過程中，生成了一個(gè)圖 G， 它是問題狀態(tài)空間圖的一部分 ，稱為 搜索圖 。 第三章 狀態(tài)空間搜索策略 寬度優(yōu)先搜索策略 寬度優(yōu)先搜索 又稱為 廣度優(yōu)先搜索 。 第三章 狀態(tài)空間搜索策略 算法 狀態(tài)空間圖的寬度優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) S0放人 OPEN表中。 (5)若節(jié)點(diǎn) n不可擴(kuò)展，轉(zhuǎn)第 (2)步；否則繼續(xù)執(zhí)行 (6)步。 要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑 。 只要問題有解，寬度優(yōu)先搜索總可以找到它的解，而且是搜索樹中，從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑最短的解。 當(dāng)?shù)竭_(dá)某個(gè)既非目標(biāo)節(jié)點(diǎn)又無法繼續(xù)擴(kuò)展的節(jié)點(diǎn)時(shí) ，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察 。 ?寬度優(yōu)先搜索 是將后繼節(jié)點(diǎn)放入 OPEN表的 末端 ——“先入先出 ” 。 搜索若進(jìn)入某一分支，則沿著這一分支一直搜索下去，對(duì)于有限的狀態(tài)空間圖，從理論上講，解總是能夠找到的。 任何節(jié)點(diǎn)如果達(dá)到了 深度界限 ，就把它作為沒有后繼節(jié)點(diǎn)進(jìn)行處理，而對(duì)另一個(gè)分支進(jìn)行搜索。 (2)如果 OPEN表為空，則問題無解，退出。 (6)如果節(jié)點(diǎn) n不可擴(kuò)展，即沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)第 (2)步；否則繼續(xù)第 (7)步。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 ?有界深度優(yōu)先搜索算法的 深度界限的選擇很重要 。 第三章 狀態(tài)空間搜索策略 搜索代價(jià)問題 ：在實(shí)際問題的搜索求解中，在將一個(gè)狀態(tài)變換成另一個(gè)狀態(tài)時(shí)，往往所付出的 操作代價(jià) (或費(fèi)用 )是不一樣的，也就是狀態(tài)空間圖中各 有向邊的代價(jià) 是不一樣的。 代價(jià)樹寬度優(yōu)先搜索的 基本思想 ：每次從 OPEN表中選擇一個(gè) 代價(jià)最小 的節(jié)點(diǎn)，移入 CLOSED表。 (4)如果節(jié)點(diǎn) n是目標(biāo)節(jié)點(diǎn)，則求得問題的解，退出，否則繼續(xù)。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 例 推銷員旅行問題 。 第三章 狀態(tài)空間搜索策略 算法 代價(jià)樹的深度優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) So放人 OPEN表中。 (5)判斷節(jié)點(diǎn) n是否可擴(kuò)展，若不可擴(kuò)展則轉(zhuǎn)第 (2)步，否則轉(zhuǎn)第 (6)步。 ?代價(jià)樹的深度優(yōu)先搜索法是 不完備 的，因?yàn)榇鷥r(jià)樹的深度優(yōu)先搜索法有可能進(jìn)入無窮分支路徑而 搜索不到問題的解 。 啟發(fā)信息 按其作用來分可以有 三種 ： (1)用于 決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn) ，以免像在寬度優(yōu)先或深度優(yōu)先中那樣盲目地?cái)U(kuò)展。設(shè)估價(jià)函數(shù)為 f(x)，則將其定義為： f(x)=g(x)+h(x) 估價(jià)函數(shù) ：在決定哪個(gè)節(jié)點(diǎn)是下一步要擴(kuò)展的節(jié)點(diǎn)上，通?？梢詷?gòu)造一個(gè) 函數(shù)來表示節(jié)點(diǎn)的 “ 希望 ” 程度 ，這種函數(shù)稱為估價(jià)函數(shù)。依賴于對(duì)問題特性了解的某種經(jīng)驗(yàn)估計(jì)，主要體現(xiàn)了 搜索的啟發(fā)信息 。 第三章 狀態(tài)空間搜索策略 最佳優(yōu)先搜索 最佳優(yōu)先搜索 基于 估價(jià)函數(shù) f(x)的值來選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。 第三章 狀態(tài)空間搜索策略 算法 局部最佳優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) So放入 OPEN表 ， 并計(jì)算估價(jià)函數(shù) f(So)。 (5)如果節(jié)點(diǎn) n可擴(kuò)展 ， 轉(zhuǎn) (6)步；否則轉(zhuǎn)第 (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)。 (3)把 OPEN表中第一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn) n移入 CLOSED表。 (7)把這些后繼節(jié)點(diǎn)都送入 OPEN表，然后對(duì) OPEN表中的 全部節(jié)點(diǎn)按照估價(jià) f(x)值從小到大的順序排序 。 第三章 狀態(tài)空間搜索策略 解 ：首先定義一個(gè)估價(jià)函數(shù)： f(x)=d(x)+h(x) d(x)：表示節(jié)點(diǎn) x在搜索樹中的 深度 ； h(x)：表示與節(jié)點(diǎn) x對(duì)應(yīng)的棋盤中 ， 與目標(biāo)節(jié)點(diǎn) Sg所對(duì)應(yīng)的棋盤中 棋子位置不同的個(gè)數(shù) 。 A*算法 第三章 狀態(tài)空間搜索策略 ? g*(x)：從節(jié)點(diǎn) So到節(jié)點(diǎn) x之間 最佳路徑 的 實(shí)際代價(jià) 。 ? h(x) ：依賴于有關(guān)問題領(lǐng)域的啟發(fā)信息 。 即便找到解 ， 也不一定是 最優(yōu)解 。 第三章 狀態(tài)空間搜索策略 2. A*算法的性質(zhì) (1)可采納性 即對(duì)于可求解的狀態(tài)空間圖 (從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在 )來說， A*算法能在有限步內(nèi) 終止 ，并找到 最優(yōu)解 。 ② 目標(biāo)節(jié)點(diǎn) Sg 的啟發(fā)函數(shù)的值為 0， 即 h(Sg)=0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1