搜索與或圖搜索ppt課件-在線瀏覽
2025-06-17 18:08本頁面
【正文】 n 與 /或樹的搜索過程實(shí)際上是一個不斷尋找 解樹的過程。Date16 與 /或樹的一般搜索n 在與 /或樹中，除端節(jié)點(diǎn)和終止節(jié)點(diǎn)外，一個節(jié)點(diǎn)的可解性完全是由其子節(jié)點(diǎn)來決定的。n 可解標(biāo)記過程n 由可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為可解節(jié)點(diǎn)的過程。Date17 與 /或樹的一般搜索n 搜索解樹的過程中，節(jié)點(diǎn) 刪除策略 ：n ① 如果搜索過程確定某個節(jié)點(diǎn)為可解節(jié)點(diǎn)，則其不 可解的后裔節(jié)點(diǎn)就可從搜索樹中刪去；n ② 如果搜索過程能確定某個節(jié)點(diǎn)為不可解節(jié)點(diǎn)，則 其后裔節(jié)點(diǎn)也可從搜索樹中刪去。若有，則標(biāo)記這些終 止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用 可解標(biāo)記過程 對其父節(jié)點(diǎn)及先輩 節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)記。Date20 與 /或樹的廣度優(yōu)先搜索n 搜索算法（續(xù)）：n （ 4） 如果節(jié)點(diǎn) n不可擴(kuò)展，則做下列工作： n ① 標(biāo)記節(jié)點(diǎn) n為不可解節(jié)點(diǎn)； n ② 應(yīng)用 不可解標(biāo)記過程 對節(jié)點(diǎn) n的先輩中不可解的節(jié)點(diǎn)進(jìn)行標(biāo)記。Date21【 例 】 t t t3的節(jié)點(diǎn)是終止節(jié)點(diǎn)， A 、 B 、 C為不可解的端節(jié)點(diǎn)12 3A 4 t1t3 CBt25(1) 1 2 3 1(2) 2 3 A 4 1 2(3) 3 A 4 5 1 2 3 t1(4) A 4 5 (5) 4 5 B 1 2 3 t1 4 t2(6) 5 B 1 2 3 t1 4 t2 5 t3(7) 搜索成功 , 解樹 : 1, 2, 3, 4, 5, t1, t2, t3擴(kuò)展節(jié)點(diǎn) Open 列表 Closed列表Date22內(nèi)容n 與或樹表示n 與 /或樹的一般搜索n 與 /或樹的廣度優(yōu)先搜索n 與 /或樹的深度優(yōu)先搜索n 與／或樹的啟發(fā)式搜索n 博弈樹的啟發(fā)式搜索Date23 與 /或樹的深度優(yōu)先搜索n 與 /或樹的深度優(yōu)先搜索算法：n （ 1）把初始節(jié)點(diǎn) S0放入 Open表中； n （ 2）把 Open表的第一個節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； n （ 3）如果節(jié)點(diǎn) n的深度等于 dm，則轉(zhuǎn)第（ 5）步的第 ① 點(diǎn)； n （ 4）如果節(jié)點(diǎn) n可擴(kuò)展，則做下列工作：n ① 擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的 首部 ，并為每一 個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； n ② 考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。如果初始節(jié)點(diǎn) S0能夠 被標(biāo)記為可解節(jié)點(diǎn)，就得到了解樹，搜索成功，退出搜 索過程；如果不能確定 S0為可解節(jié)點(diǎn)，則從 Open表中刪 去具有可解先輩的節(jié)點(diǎn)； n ③ 轉(zhuǎn)第（ 2）步。如果初始節(jié)點(diǎn) S0也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定為不可解節(jié)點(diǎn)，則從 Open表中刪去具有不可解先輩的節(jié)點(diǎn)； n ③ 轉(zhuǎn)第（ 2）步。n 則其擴(kuò)展節(jié)點(diǎn)的順序?yàn)椋?1， 3， 5， 2， 4n 其解樹與上例相同。對搜索的每一步，算法都試圖找到一個最有希望成為最優(yōu)解樹的子樹（ 希望樹 ）。Date28 與／或樹的啟發(fā)式搜索n 如何計(jì)算解樹的代價？目標(biāo)目標(biāo)初始節(jié)點(diǎn)abcDate29 與／或樹的啟發(fā)式搜索n 解樹的代價可按如下規(guī)則計(jì)算：n （ 1）若 n為終止節(jié)點(diǎn)： n （ 2）若 n為 或節(jié)點(diǎn) ，且子節(jié)點(diǎn)為 n1， n2， … ， nk， n （ 3）若 n為與節(jié)點(diǎn)，且子節(jié)點(diǎn)為 n1， n2， … ， nk， n 和代價法：n 最大代價法：n （ 4）若 n是端節(jié)點(diǎn)，但又不是終止節(jié)點(diǎn)：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1