第三章?tīng)顟B(tài)空間搜索策略-文庫(kù)吧資料
2024-10-19 12:54本頁(yè)面
【正文】 6)步。 (3)把 OPEN表中 代價(jià)最小 的節(jié)點(diǎn)，即 排在前端的第一個(gè)節(jié)點(diǎn) (即為節(jié)點(diǎn)n)，移入 CLOSED表中。 第三章 狀態(tài)空間搜索策略 算法 代價(jià)樹(shù)的寬度優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) So放入 OPEN表，令 g(So)=0。 第三章 狀態(tài)空間搜索策略 代價(jià)計(jì)算 ：在代價(jià)樹(shù)中，把從初始節(jié)點(diǎn) So到任意節(jié)點(diǎn) i的路徑代價(jià)記為 g(i)，而把從節(jié)點(diǎn) i到其后繼節(jié)點(diǎn) j的連線之代價(jià) (有向邊代價(jià) )記為 C(i,， j)，則 g(j)=g(i)+C(i， j)。這是前面討論搜索算法沒(méi)有考慮的。對(duì)于某些問(wèn)題，可能它的解就位于某一分支較深的位置，而界限值選取的沒(méi)有那么大，就會(huì)導(dǎo)致找不到問(wèn)題的解。選擇過(guò)大，可能會(huì)影響搜索的效率；選擇的過(guò)小，有可能求不到解。深度界限 dm=5。 (7)擴(kuò)展節(jié)點(diǎn) n，將其后繼節(jié)點(diǎn)放入 OPEN表的 前端 ，并為其設(shè)置指向節(jié)點(diǎn)的指針，轉(zhuǎn)第 (2)步。 (5)如果節(jié)點(diǎn) n的深度 dn等于最大深度 dm， 則轉(zhuǎn)第 (2)步 。 (3)把 OPEN表中的第一個(gè)節(jié)點(diǎn) n從 OPEN表移到 CLOSED表。 第三章 狀態(tài)空間搜索策略 算法 有界深度優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) So放入 OPEN表中。 有界深度優(yōu)先搜索 搜索樹(shù)中 節(jié)點(diǎn)深度 (d)定義： (1)搜索樹(shù)中 初始節(jié)點(diǎn) 的深度為 0。 第三章 狀態(tài)空間搜索策略 在深度優(yōu)先搜索中，為了避免搜索過(guò)程沿著無(wú)窮的路徑一直搜索下去，往往對(duì)一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度進(jìn)行限制。 ?搜索效率低。 第三章 狀態(tài)空間搜索策略 深度優(yōu)先搜索的特點(diǎn)： ?搜索策略是完備的。 ?深度優(yōu)先搜索 是將后繼節(jié)點(diǎn)放入 OPEN表的 前端 ——“后入先出 ” 。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 ?深度優(yōu)先搜索 與 寬度優(yōu)先搜索 的 區(qū)別 就在于：在對(duì)節(jié)點(diǎn) n進(jìn)行擴(kuò)展時(shí)， 其后繼節(jié)點(diǎn)在 OPEN表中的 存放位置 。 在搜索過(guò)程中 ， 未擴(kuò)展節(jié)點(diǎn)表 OPEN中的節(jié)點(diǎn)排序準(zhǔn)則是： “ 后入先出 ” ，即后進(jìn)入的節(jié)點(diǎn)排在前面 ， 先進(jìn)入的節(jié)點(diǎn)排在后面 。 依次類推 ， 一直搜索下去 。 第三章 狀態(tài)空間搜索策略 基本思想： 首先擴(kuò)展最新產(chǎn)生的 (即最深的 )節(jié)點(diǎn) 。 ?搜索策略是完備的。 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 S0 (a) 初始狀態(tài) Sg (b) 目標(biāo)狀態(tài) 第三章 狀態(tài)空間搜索策略 解的路徑為 : So→ 3→ 8→16→27→ Sg 第三章 狀態(tài)空間搜索策略 寬度優(yōu)先搜索的特點(diǎn)： ?搜索盲目性較大，效率低。 使 8個(gè)數(shù)據(jù)最終按下圖 (b)的格式擺放 ， 圖 (b)稱為目標(biāo)狀態(tài) Sg。 (6)對(duì)節(jié)點(diǎn) n進(jìn)行擴(kuò)展，將它的所有后繼節(jié)點(diǎn)放人 OPEN表的末端，并為這些后繼節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn) n的指針，然后轉(zhuǎn)第 (2)步。 (4)判斷節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)，若是，則求解結(jié)束，并用回溯法找出解的路徑，退出；否則繼續(xù)執(zhí)行 (5)。 (2)如果 OPEN表是空表，則沒(méi)有解，失敗退出；否則繼續(xù)。 在搜索過(guò)程中 ， 未擴(kuò)展節(jié)點(diǎn)表 OPEN中的節(jié)點(diǎn)排序準(zhǔn)則是： “ 先入先出 ” ，即先進(jìn)入的節(jié)點(diǎn)排在前面 ， 后進(jìn)入的節(jié)點(diǎn)排在后面 。 基本思想： 是從初始節(jié)點(diǎn)開(kāi)始 ， 逐層對(duì)節(jié)點(diǎn)進(jìn)行依次擴(kuò)展 ， 并考察它是否為目標(biāo)節(jié)點(diǎn) 。 ?路徑 是通過(guò)目標(biāo)節(jié)點(diǎn)按設(shè)置的指針指向初始節(jié)點(diǎn) So回溯 而得到的。 ?由搜索圖 G中的 所有節(jié)點(diǎn) 及設(shè)置的指向父節(jié)點(diǎn)的 反向指針 ，所構(gòu)成的集合 T，稱為 搜索樹(shù) 。 (9)轉(zhuǎn)第 (3)步。 (7)對(duì)那些 未曾在 G中出現(xiàn)過(guò) 的 M中的節(jié)點(diǎn)，設(shè)置一個(gè)指向父節(jié)點(diǎn) (即節(jié)點(diǎn) n)的指針，并把這些節(jié)點(diǎn)加入OPEN表中；對(duì)于 已在 G中出現(xiàn)過(guò) 的 M中的那些節(jié)點(diǎn)，確定是否需要修改指向父節(jié)點(diǎn) (n節(jié)點(diǎn) )的指針；對(duì)于那些 先前已在 G中出現(xiàn) 并且已在CLOSED表中的那些 M中的節(jié)點(diǎn)，確定是否需要修改通向它們后繼節(jié)點(diǎn)的指針。問(wèn)題的解即可從圖 G中沿著指針從 n到 S0的這條路徑得到。 (4)若 OPEN表非空，選擇 OPEN表中的第一個(gè)節(jié)點(diǎn)，把它從 OPEN表移出，并放人CLOSED表中，將此節(jié)點(diǎn)記為節(jié)點(diǎn) n。 (2)建立 CLOSED表，且置為空表。我們采用一個(gè)稱為 OPEN表的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，來(lái)專門(mén)登記當(dāng)前待考查的節(jié)點(diǎn)。 CLOSED表中存儲(chǔ)的是一棵不斷成長(zhǎng)的搜索樹(shù)。 狀態(tài)空間圖的一般搜索策略： 第三章 狀態(tài)空間搜索策略 搜索的目的是為了尋找初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的 路徑 ，所以在搜索過(guò)程中就得 隨時(shí)記錄搜索軌跡 。 ?未擴(kuò)展節(jié)點(diǎn)： 對(duì)狀態(tài)空間圖中的某個(gè)節(jié)點(diǎn)，如果 尚未求出它的后繼節(jié)點(diǎn) ，則此節(jié)點(diǎn)稱為未擴(kuò)展節(jié)點(diǎn)。 第三章 狀態(tài)空間搜索策略 節(jié)點(diǎn)擴(kuò)展 概念 ?擴(kuò)展： 就是用合適的算符對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行操作生成一組后繼節(jié)點(diǎn)，擴(kuò)展過(guò)程實(shí)際上就是 求后繼節(jié)點(diǎn) 的過(guò)程。 ?如果有
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1