【正文】 86427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321??????????567481320??????????567408321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 64 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321??????????567481320??????????567408321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 65 ??????????586427301??????????586427031??????????586407321??????????586427310??????????506487321??????????586470321??????????586047321??????????560487321??????????056487321??????????567480321??????????567481320??????????567408321初 始 化開 始O P E N 表 = { }失 敗是取 得 待 擴(kuò) 展 節(jié) 點(diǎn) nn : = M O V E F I R S T ( O P E N )否n 是 目 標(biāo) 狀 態(tài) 節(jié) 點(diǎn)成 功是擴(kuò) 展 節(jié) 點(diǎn) n 的 子 節(jié) 點(diǎn)插 入 搜 索 圖 G 和 O P E N 表 否標(biāo) 記 和 修 改 指 針重 新 排 序 O P E N 表2022/8/21 66 狀態(tài)空間搜索 —— （ 2）一般圖搜索算法 ——搜索過程中的指針修改 ? 節(jié)點(diǎn) n擴(kuò)展后 的子節(jié)點(diǎn)分為 3類 ： ? (i)全新節(jié)點(diǎn) ? (ii)已出現(xiàn)在 OPEN表 中的節(jié)點(diǎn) ? (iii)已出現(xiàn)的 CLOSE表 中的節(jié)點(diǎn) ? 指針標(biāo)記和修改的方法： ? (i)類節(jié)點(diǎn)：加入 OPEN表，建立從子節(jié)點(diǎn)到父節(jié)點(diǎn) n的指針 ? (ii)類節(jié)點(diǎn)、 (iii)類節(jié)點(diǎn) ? 比較 經(jīng)由 老父節(jié)點(diǎn) 、 新父節(jié)點(diǎn) n到達(dá) 初始狀態(tài)節(jié)點(diǎn) 的 路徑代價 ? 經(jīng)由新父節(jié)點(diǎn) n的代價比較小，則將原子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，修改為指向新父節(jié)點(diǎn) n ? (iii)類節(jié)點(diǎn)還得從 CLOSE表中移出，重新加入 OPEN表。 2022/8/21 67 狀態(tài)空間搜索 —— S n4 ni nj n1 n2 n3 n31 n32 ? 節(jié)點(diǎn) ni是當(dāng)前擴(kuò)展的節(jié)點(diǎn)； ? 擴(kuò)展出 4個后續(xù)節(jié)點(diǎn)； ? n n2是新節(jié)點(diǎn) ， 只需建立指向父節(jié)點(diǎn)的指針，并加入 OPEN表 ； 2022/8/21 68 狀態(tài)空間搜索 —— S n4 ni nj n1 n2 n3 n31 n32 ? n4已經(jīng)存在于 OPEN表，并且已有父節(jié)點(diǎn) nj ? n4經(jīng) nj的路徑代價大 ? 取消 n4指向 nj的指針 ? 改為建立 n4指向新父節(jié)點(diǎn) ni的指針 ? n3已經(jīng)存在于 CLOSE表，并且已有父節(jié)點(diǎn) nj ? 需要做和 n4同樣的比較和指針修改工作。并且要重新加入open表。 2022/8/21 69 狀態(tài)空間搜索 —— （ 2）一般圖搜索算法 ? OPEN表中節(jié)點(diǎn)簡單的排序方式 ： ? 深度優(yōu)先 ——擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是 置于OPEN表的前端 ，即 OPEN表 作為 棧 ， 后進(jìn)先出 ，使 搜索優(yōu)先向縱深方向發(fā)展 。 2022/8/21 70 深度優(yōu)先實例 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 4 6 8 9 11 13 14 16 18 19 1 2 3 8 4 7 6 5 目標(biāo) 5 7 10 12 15 17 20 21 2022/8/21 71 深度優(yōu)先搜索 ? 在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的 (最深的 )節(jié)點(diǎn)，深度 相等的節(jié)點(diǎn)可以任意排列。 ? “ 最晚產(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展 ” ? 起始節(jié)點(diǎn)深度為 0 ? 任何其他節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上 1 :dn=dn1+1 2022/8/21 72 深度優(yōu)先搜索 ?很明顯這樣做， 不一定 找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴(kuò)展下去，這當(dāng)然是不允許的。 ?為保證找到解，應(yīng)選擇適當(dāng)?shù)?深度界限 ，或者采取不斷加大深度界限的辦法，反復(fù)搜索，直到找到解。這種改進(jìn)的方法叫做迭代加深搜索 。 2022/8/21 73 Procedure Depth First Search Begin 把初始節(jié)點(diǎn)壓入棧，并設(shè)置棧頂指針； While 棧不空 do Begin 彈出棧頂元素； If 棧頂元素 =goal，成功返回并結(jié)束； Else 以任意次序把棧頂元素的子女壓入棧中； End While End ?基于棧實現(xiàn)的深度優(yōu)先搜索算法： 2022/8/21 74 ? 初始節(jié)點(diǎn)放到棧中，棧指針指向棧的最上邊的元素。 ? 為了對該節(jié)點(diǎn)進(jìn)行檢測，需要從棧中彈出該節(jié)點(diǎn)，如果是目標(biāo)，該算法結(jié)束，否則把其子節(jié)點(diǎn)以任何順序壓入棧中。該過程直到棧變成為空。 ? 遍歷 一棵樹的過程（下圖）。 2022/8/21 75 深度優(yōu)先搜索的性質(zhì) ?一般不能保證找到最優(yōu)解 ?當(dāng)深度限制不合理時， 可能找不到解 ，可以將算法改為 可變深度限制 ?最壞情況時，搜索空間等同于窮舉 ?是一個通用的與問題無關(guān)的方法 2022/8/21 76 ? 深度優(yōu)先搜索 的 優(yōu)點(diǎn) 是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需要保存搜索樹的一部分，它由當(dāng)前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點(diǎn)標(biāo)志所組成。 ? 深度優(yōu)先搜索的存儲器要求是深度約束的線性函數(shù)。 深度優(yōu)先搜索的優(yōu)點(diǎn) 2022/8/21 77 深度優(yōu)先搜索的缺點(diǎn) 既不是完備的，也不是最優(yōu)的。 主要問題是可能搜索到了錯誤的路徑上。很多問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜索下去，而不會回到正確的路徑上。這樣一來對于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優(yōu)的答案。 2022/8/21 78 狀態(tài)空間搜索 —— （ 2）一般圖搜索算法 ? OPEN表中節(jié)點(diǎn)簡單的排序方式 ： ? 深度優(yōu)先 ——擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是 置于OPEN表的前端 ，即 OPEN表 作為 棧 ， 后進(jìn)先出 ，使 搜索優(yōu)先向縱深方向發(fā)展 。 ? 寬度優(yōu)先 ——擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是 置于OPEN表的后端 ，即 OPEN表 作為 隊列 ， 先進(jìn)先出 ，使搜索優(yōu)先向橫向方向發(fā)展 。 2022/8/21 79 寬度優(yōu)先實例 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 1 2 5 6 7 3 1 2 3 8 4 7 6 5 目標(biāo) 8 2 3 4 1 8 7 6 5 4 9 10 11 12 13 14 15 16 17 2022/8/21 80 寬度優(yōu)先搜索 ?如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做 寬度優(yōu)先搜索。 ?這種搜索是逐層進(jìn)行的，在對下一層的任意節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 ?“先產(chǎn)生的