人工智能第1章盲目搜索(參考版)
2025-02-22 15:24本頁面
【正文】 舉例：迷宮問題 0 1 2 3 x 1 2 3 y F G H E C A D B 2 2 2 4 1 1 1 1 注：每個節(jié)點(diǎn)小括號內(nèi)的數(shù)值表示走到該節(jié)點(diǎn)所需付出的代價(jià)。 雖然中途有時也展開了一些并不是答案的結(jié)點(diǎn) ， 但這種展開并不是大規(guī)模的 ， 不是全部展開 ，因而耗時要比橫向搜索小得多 。 開始 把 S放入 OPEN表 OPEN表為空表？ 把第一個節(jié)點(diǎn) (n)從 OPEN表移至 CLOSED表 擴(kuò)展 n，把 n的后繼節(jié)點(diǎn)放入 OPEN表的末端，提供返回節(jié)點(diǎn) n的指針 失敗 均一代價(jià)搜索算法框圖 是 否 把第一個節(jié)點(diǎn) (n)從 OPEN表移至 CLOSED表 n為目標(biāo)節(jié)點(diǎn)嗎？ 成功 是 否 按 g(i)值由小到大的順序重排 OPEN表 均一代價(jià)搜索法思路： 從 A點(diǎn)開始依次展開得到 AB（ 7） 、 AC（ 3） 、 AD（ 10） 、 AE（ 15） 四個新結(jié)點(diǎn) ， 把第一層結(jié)點(diǎn) A標(biāo)記為已展開 ， 并且每個新結(jié)點(diǎn)要記錄下其距離 （ 括號中的數(shù)字 ） ； 把未展開過的 AB、 AC、 AD、 AE四個結(jié)點(diǎn)中距離最小的一個展開 ， 即展開 AC（ 3） 結(jié)點(diǎn) ， 得到 ACB（ 8） 、 ACD（ 16） 、 ACE（ 13） 三個結(jié)點(diǎn) ， 并把結(jié)點(diǎn) AC標(biāo)記為已展開； 再從未展開的所有結(jié)點(diǎn)中找出距離最小的一個展開 ， 即展開 AB（ 7） 結(jié)點(diǎn) ， 得到 ABC（ 12） 、 ABD（ 20） 、 ABE（ 19） 三個結(jié)點(diǎn) ， 并把結(jié)點(diǎn)AB標(biāo)記為已展開； 再次從未展開的所有結(jié)點(diǎn)中找出距離最小的一個展開 ， 即展開 ACB（ 8）結(jié)點(diǎn) …… ； 每次展開所有未展開的結(jié)點(diǎn)中距離最小的那個結(jié)點(diǎn) ， 直到展開的新結(jié)點(diǎn)中出現(xiàn)目標(biāo)情況 （ 結(jié)點(diǎn)含有 5個字母 ） 時 ， 即得到了結(jié)果 。 若所有連接弧線具有相等代價(jià)，則簡化為橫向搜索算法。 開始 把 S放入 OPEN表 OPEN表為空表？ 把第一個節(jié)點(diǎn) (n)從 OPEN表移至 CLOSED表 擴(kuò)展 n，把 n的后繼節(jié)點(diǎn)放入 OPEN表的末端，提供返回節(jié)點(diǎn) n的指針 失敗 寬度優(yōu)先搜索 算法框圖 是 否 把第一個節(jié)點(diǎn) (n)從 OPEN表移至 CLOSED表 n為目標(biāo)節(jié)點(diǎn)嗎？ 成功 是 否 舉例： ? 八數(shù)碼魔方 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （目標(biāo)狀態(tài)） （初始狀態(tài) ） 1 2 3 8 4 5 6 7 1 2 3 8 4 1 2 3 8 4 5 6 7 4 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1