第三章?tīng)顟B(tài)空間搜索策略(編輯修改稿)
2024-11-16 12:54 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 前面 ， 先進(jìn)入的節(jié)點(diǎn)排在后面 。 深度優(yōu)先搜索 第三章 狀態(tài)空間搜索策略 算法 狀態(tài)空間圖的深度優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) S0放人 OPEN表； (2)如果 OPEN表為空 ， 則問(wèn)題無(wú)解 ， 退出； (3)從 OPEN表中將其第一個(gè)節(jié)點(diǎn) (節(jié)點(diǎn) n)移出 ， 放入已擴(kuò)展節(jié)點(diǎn)表 CLOSED中； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn) ， 若是 ， 則找到問(wèn)題的解 ，用 回溯法 求解的路徑 ， 退出； (5)若節(jié)點(diǎn) n不可擴(kuò)展 ， 則轉(zhuǎn)第 (2)步； (6)擴(kuò)展節(jié)點(diǎn) n ， 將 其后繼節(jié)點(diǎn)放到 OPEN表的 前端 ， 并為其設(shè)置指向節(jié)點(diǎn) n的指針 ， 然后轉(zhuǎn)第 (2)步 。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 ?深度優(yōu)先搜索 與 寬度優(yōu)先搜索 的 區(qū)別 就在于：在對(duì)節(jié)點(diǎn) n進(jìn)行擴(kuò)展時(shí)， 其后繼節(jié)點(diǎn)在 OPEN表中的 存放位置 。 ?寬度優(yōu)先搜索 是將后繼節(jié)點(diǎn)放入 OPEN表的 末端 ——“先入先出 ” 。 ?深度優(yōu)先搜索 是將后繼節(jié)點(diǎn)放入 OPEN表的 前端 ——“后入先出 ” 。 第三章 狀態(tài)空間搜索策略 例 對(duì)例 ，利用深度優(yōu)先方法進(jìn)行搜索求解問(wèn)題。 第三章 狀態(tài)空間搜索策略 深度優(yōu)先搜索的特點(diǎn)： ?搜索策略是完備的。 搜索若進(jìn)入某一分支，則沿著這一分支一直搜索下去，對(duì)于有限的狀態(tài)空間圖，從理論上講，解總是能夠找到的。 ?搜索效率低。 由于某些分支可能擴(kuò)展得很深，而解又不在這些分支上，這就無(wú)疑會(huì)降低搜索的效率。 第三章 狀態(tài)空間搜索策略 在深度優(yōu)先搜索中，為了避免搜索過(guò)程沿著無(wú)窮的路徑一直搜索下去，往往對(duì)一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度進(jìn)行限制。 任何節(jié)點(diǎn)如果達(dá)到了 深度界限 ，就把它作為沒(méi)有后繼節(jié)點(diǎn)進(jìn)行處理，而對(duì)另一個(gè)分支進(jìn)行搜索。 有界深度優(yōu)先搜索 搜索樹(shù)中 節(jié)點(diǎn)深度 (d)定義： (1)搜索樹(shù)中 初始節(jié)點(diǎn) 的深度為 0。 (2)任何 其他節(jié)點(diǎn) 的深度等于其 父輩節(jié)點(diǎn) 的深度加上 1。 第三章 狀態(tài)空間搜索策略 算法 有界深度優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) So放入 OPEN表中。 (2)如果 OPEN表為空，則問(wèn)題無(wú)解，退出。 (3)把 OPEN表中的第一個(gè)節(jié)點(diǎn) n從 OPEN表移到 CLOSED表。 (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得問(wèn)題的解，退出；否則繼續(xù)執(zhí)行第 (5)步。 (5)如果節(jié)點(diǎn) n的深度 dn等于最大深度 dm， 則轉(zhuǎn)第 (2)步 。 (6)如果節(jié)點(diǎn) n不可擴(kuò)展，即沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)第 (2)步；否則繼續(xù)第 (7)步。 (7)擴(kuò)展節(jié)點(diǎn) n，將其后繼節(jié)點(diǎn)放入 OPEN表的 前端 ，并為其設(shè)置指向節(jié)點(diǎn)的指針，轉(zhuǎn)第 (2)步。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 例 設(shè)八數(shù)碼難題的初始狀態(tài)及目標(biāo)狀態(tài)分別如下圖 (a)和圖 (b)所示，試用有界深度優(yōu)先搜索策略求解問(wèn)題。深度界限 dm=5。 第三章 狀態(tài)空間搜索策略 第三章 狀態(tài)空間搜索策略 ?有界深度優(yōu)先搜索算法的 深度界限的選擇很重要 。選擇過(guò)大，可能會(huì)影響搜索的效率；選擇的過(guò)小，有可能求不到解。 ?有界深度優(yōu)先 搜索策略是不完備的 。對(duì)于某些問(wèn)題，可能它的解就位于某一分支較深的位置，而界限值選取的沒(méi)有那么大，就會(huì)導(dǎo)致找不到問(wèn)題的解。 第三章 狀態(tài)空間搜索策略 搜索代價(jià)問(wèn)題 ：在實(shí)際問(wèn)題的搜索求解中，在將一個(gè)狀態(tài)變換成另一個(gè)狀態(tài)時(shí)，往往所付出的 操作代價(jià) (或費(fèi)用 )是不一樣的，也就是狀態(tài)空間圖中各 有向邊的代價(jià) 是不一樣的。這是前面討論搜索算法沒(méi)有考慮的。 代價(jià)樹(shù)的寬度優(yōu)先搜索 代價(jià)樹(shù) ：把 有向邊 上標(biāo)有 代價(jià) 的搜索樹(shù)稱(chēng)為 代價(jià)搜索樹(shù) ，簡(jiǎn)稱(chēng) 代價(jià)樹(shù) 。 第三章 狀態(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的連線(xiàn)之代價(jià) (有向邊代價(jià) )記為 C(i,， j)，則 g(j)=g(i)+C(i， j)。 代價(jià)樹(shù)寬度優(yōu)先搜索的 基本思想 ：每次從 OPEN表中選擇一個(gè) 代價(jià)最小 的節(jié)點(diǎn)，移入 CLOSED表。 第三章 狀態(tài)空間搜索策略 算法 代價(jià)樹(shù)的寬度優(yōu)先搜索算法 (1)把初始節(jié)點(diǎn) So放入 OPEN表，令 g(So)=0。 (2)如果 OPEN表為空，則問(wèn)題無(wú)解，退出。 (3)把 OPEN表中 代價(jià)最小 的節(jié)點(diǎn)，即 排在前端的第一個(gè)節(jié)點(diǎn) (即為節(jié)點(diǎn)n)，移入 CLOSED表中。 (4)如果節(jié)點(diǎn) n是目標(biāo)節(jié)點(diǎn)，則求得問(wèn)題的解，退出，否則繼續(xù)。 (5)判斷節(jié)點(diǎn) n是否可擴(kuò)展，若不可擴(kuò)展，則轉(zhuǎn) (2)步；否則轉(zhuǎn) (6)步。 (6)對(duì)節(jié)點(diǎn) n進(jìn)行擴(kuò)展，將它們所有的后繼節(jié)點(diǎn)放入 OPEN表中，并對(duì)每個(gè) 后繼節(jié)點(diǎn) j計(jì)算其代價(jià) g(j)=g(i)+C(i， j)，為每個(gè)后繼節(jié)點(diǎn)設(shè)置指向 n節(jié)點(diǎn)的指針，然后，根據(jù)節(jié)點(diǎn)的代價(jià)大小對(duì) OPEN表中的 所有 節(jié)點(diǎn)進(jìn)行從小到大的排序 。 (7)轉(zhuǎn)向第 (2)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1