【正文】 (BreadthFirst Strategy)新的節(jié)點(diǎn)被插入到棧 OPEN的 后部12 34 5OPEN= (11,6,7,8,9,12,13)CLOSED=(1,2,3,4,5,10 )6 7 8 910 1112 13 14 15深度優(yōu)先搜索策略n 新節(jié)點(diǎn)優(yōu)先擴(kuò)展 , 直到達(dá)到一定的深度限制 .若找不到目標(biāo)或無法在擴(kuò)展時 ,回溯到另一節(jié)點(diǎn)繼續(xù)擴(kuò)展 .n 特點(diǎn) : 需要深度限制 , 需要回溯控制 , 省空間n 探索算法 : n 數(shù)據(jù)結(jié)構(gòu) : OPEN表 : 后進(jìn)先出隊列 ,存放待擴(kuò)展的節(jié)點(diǎn) . CLOSED表 : 存放已被擴(kuò)展過的節(jié)點(diǎn) .n 除擴(kuò)展后的子節(jié)點(diǎn)應(yīng)放入到 OPEN表的首部以外 ,與寬度優(yōu)先算法一樣 .深度優(yōu)先算法框圖v 算法 開始把 S放入 OPEN表OPEN表為空表？把第一個節(jié)點(diǎn) (n)從 OPEN表移至 CLOSED表是否有后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？擴(kuò)展 n，把 n的后繼節(jié)點(diǎn)放入 OPEN表的 前端 ，提供返回節(jié)點(diǎn) n的指針失敗成功是否是否深度優(yōu)先搜索算法n Step1: 把初始節(jié)點(diǎn) S0放入 OPEN表中 。n Step4: 若目標(biāo)節(jié)點(diǎn) Sg=N, 則搜索成功 ,結(jié)束 .n Step5: 若 N不可擴(kuò)展 , 則轉(zhuǎn) Step2。深度優(yōu)先搜索 (DepthFirst Strategy)新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 5OPEN= (1)CLOSED=( )6 7 8 910 1112 13 14 15DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 5OPEN = (2, 3)CLOSED=( 1 )6 7 8 910 1112 13 14 15DepthFirst Strategy 新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 5OPEN = (4, 5, 3)CLOSED=( 1,2 )6 7 8 910 1112 13 14 15DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 5CLOSED=( 1,2,4 )6 7OPEN = (6,7, 5, 3)8 910 1112 13 14 15DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 56 7 8 910 11CLOSED=( 1,2,4,6 )OPEN = (7, 5, 3)12 13 14 15DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 56 7 8 910 11CLOSED=( 1,2,4,6,7 )OPEN = (5, 3)12 13 14 15DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 56 7 8 910 11CLOSED=( 1,2,4, 5,6,7 )OPEN = (8,9,3)12 13 14 15DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 56 7 8 910 11CLOSED=( 1,2,4,5, 6,7 ,8)OPEN = (9, 3)12 13 14 15DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 56 7 8 9 1210 1113 14 15CLOSED=( 1,2,4, 5,6,7, 8,9)OPEN = (3)DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 56 7 8 9 1210 1113 14 15CLOSED=( 1,2,4, 5,6,7,8,9,3)OPEN = (10,11)DepthFirst Strategy新的節(jié)點(diǎn)被插入到棧 OPEN的 前部12 34 56 7 8 910 11CLOSED=( 1,2,4, 5,6,7,8,9,3,10)12 13 14 15OPEN = (12,13,11)代價樹搜索代價樹 ：搜索樹中每條連接弧線上的有關(guān)代價 ,表示時間、距離等花費(fèi)。 *若所有連接弧線具有相等代價，則簡化為寬度優(yōu)先搜索算法。n 等代價搜索方法以 g(i)的遞增順序擴(kuò)展其節(jié)點(diǎn)。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解；否則令 g（ S） =0。n （ 3） 從 OPEN 表中選擇一個節(jié)點(diǎn) i，使其 g（ i）為最小。把節(jié)點(diǎn) i從 OPEN表移至擴(kuò)展節(jié)點(diǎn)表CLOSED中。n （ 5） 擴(kuò)展節(jié)點(diǎn) i。n （ 6） 對于節(jié)點(diǎn) i的每個后繼節(jié)點(diǎn) j，計算 g（ j） =g（ i） +c（ i,j）， 并把所有后繼節(jié)點(diǎn) j放進(jìn) OPEN表。n （ 7） 轉(zhuǎn)向第（ 2）步。n 探索算法 :n 全局擇優(yōu)搜索 (最好優(yōu)先搜索 ), 局部擇優(yōu)搜索n 數(shù)據(jù)結(jié)構(gòu)： OPEN表 、 CLOSED表 啟發(fā)信息n 啟發(fā)式搜索就是利用啟發(fā)性信息進(jìn)行制導(dǎo)的搜索。n 按其用途劃分，啟發(fā)性信息一般可分為以下三類： (1)用于擴(kuò)展節(jié)點(diǎn)的選擇 ，即用于決定應(yīng)先擴(kuò)展哪一個節(jié)點(diǎn)，以免盲目擴(kuò)展。 (3)用于刪除節(jié)點(diǎn)的選擇 ，即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn)，以免造成進(jìn)一步的時空浪費(fèi)。n 應(yīng)用這種排序過程，需要某些估算節(jié)點(diǎn) “希望 ”的量度。n 一個節(jié)點(diǎn)的 “希望 ”（ promise）有幾種不同 的定義方法。n 我們用符號 f來標(biāo)記估價函數(shù)，用 f（ n） 表示節(jié)點(diǎn) n的估價函數(shù)值。通?？梢詤⒖嫉乃悸酚校? （ 1） 一個節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離或差異的度量； （ 2）一個節(jié)點(diǎn)處在最佳路徑上的概率； （ 3）或者根據(jù)經(jīng)驗(yàn)的主觀打分。– 該函數(shù)給出了一個更好的距離評估f2 = 1 + 1 + 2 + 2 = 61 3 2476581 2 38 47 6 5目標(biāo)： 啟發(fā)式搜索算法n n 啟發(fā)式搜索要用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值的計算與傳播過程，并且由啟發(fā)函數(shù)值來確定節(jié)點(diǎn)的擴(kuò)展順序。n 全局擇優(yōu)搜索 在 OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，并用啟發(fā)函數(shù)h(x)對它們?nèi)窟M(jìn)行估價，從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，而不管這個節(jié)點(diǎn)出現(xiàn)在搜索樹的什么地方。n Step2: 若 OPEN表為空 ,則搜索失敗 ,退出 .n Step3: 移出 OPEN中第一個節(jié)點(diǎn) N放入 CLOSED表 中 , 并標(biāo)以順序編號 n。n Step6: 擴(kuò)展 N,計算每個子節(jié)點(diǎn)的函數(shù)值 h(x),將所有子節(jié)點(diǎn)配上指向 N的返回指針后放入 OPEN表中 , 再 按函數(shù)值的升序重新排序 OPEN表中的節(jié)點(diǎn) , 轉(zhuǎn) Step2。 h(n):目標(biāo)格局與現(xiàn)格局 (Sn)相比 ,位置不同的牌數(shù). 初始格局 S0 目標(biāo)格局 Sg 2 8 3 1 2 3 1 4 === 8 4 7 6 5 7 6 5h(S0) = 3局部擇優(yōu)搜索算法n Step1: 把初始節(jié)點(diǎn) S0放入 OPEN表中 ,計算 h(S0)。n Step4: 若目標(biāo)節(jié)點(diǎn) Sg=N, 則搜索成功 ,結(jié)束 .n Step5: 若 N不可擴(kuò)展 , 則轉(zhuǎn) Step2。局部搜索算法n 特點(diǎn)： 從單獨(dú)的一個當(dāng)前狀態(tài)出發(fā)，通常只移動到與之相鄰的狀態(tài)，并且不保留解的路徑。（ 啟發(fā)函數(shù)值越小離目標(biāo)越近 ）n 相當(dāng)于深度優(yōu)先算法 +啟發(fā)式搜索n 線式搜索 ，不能回溯n 向目標(biāo)值增加的方向持續(xù)移動啟發(fā)式搜索 :A算法n 評價函數(shù) f(x) = g(x) + h(x)，表示通過節(jié)點(diǎn) x的估計代價值。n 特點(diǎn) : 效率高 , 無回溯 , n 搜索算法OPEN表 : 存放待擴(kuò)展的節(jié)點(diǎn) . CLOSED表 : 存放已被擴(kuò)展過的節(jié)點(diǎn) .啟發(fā)式搜索 :A算法n Step1: 把附有計算 f(S0)初始節(jié)點(diǎn) S0放入 OPEN表中 。n Step4: 若目標(biāo)節(jié)點(diǎn) Sg=N, 則搜索成功 ,結(jié)束 .n Step5: 若 N不可擴(kuò)展 , 則轉(zhuǎn) Step2。n 刪除重復(fù)節(jié)點(diǎn)和修改返回指針 .八數(shù)碼難題（ 8puzzle problem）1 2 38 4567（目標(biāo)狀態(tài)）12 384567（初始狀態(tài)）A算法的應(yīng)用八數(shù)碼難題 :評價函數(shù) n 簡單的評價函數(shù) h(n)=d(n)+W(n)n 其中： d(n)是搜索樹中節(jié)點(diǎn) n的深度； W(n)用來計算對應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫中錯放的棋子個數(shù)。h*(n):從 N到目標(biāo)節(jié)點(diǎn)的最短路徑 。n 定義 2 在 A算法中，如果對所有的 x存在h(x)≤h*(x) （ 低估 ） ,則稱 h(x)為 h*(x)的下界，它表示某種偏于保守的估計。具有 f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為 A*算法的充分條件n 1) 搜索樹上存在著從起始點(diǎn)到終了點(diǎn)的最優(yōu)路徑。n 3）所有結(jié)點(diǎn)的子結(jié)點(diǎn)的搜索代價值 0。n Step2: 若 OPEN表為空 ,則搜索失敗 ,退出 .n Step3: 移出 OPEN中第一個節(jié)點(diǎn) N放入 CLOSED表 中 , 并標(biāo)以順序號 n。n Step6: 擴(kuò)展 N, 生成一組子節(jié)點(diǎn) ,