【正文】 點(diǎn)ni和 nj，其中 nj是 ni的子節(jié)點(diǎn)，滿足 h(ni) h(nj) ≤ c(ni, nj) h(t) = 0(t為目標(biāo)節(jié)點(diǎn)） 或 h(ni) ≤ c(ni, nj) + h(nj) h(t) = 0 則稱 h是單調(diào)的。 nj h(nj) h(ni) ni c(ni,nj) h(n) t 實(shí)例證明：例 1修改 h(n) s(10) A(1) B(5) C(8) G 目標(biāo) 6 3 1 1 1 8 C(9) B(8) A(7) G(0) s(10) A(1) B(5) C(8) G 目標(biāo) 6 3 1 1 1 8 一個(gè)例子 (修改后 h(n) )： OPEN表 CLOSED表 s(10) s(10) SC(10) SB(11) SA(13) SC(10) s(10) SCB(10) SB(11) SA(13) SCBA(10) SB(11) SA(13) SCBAG(11) SB(11) SA(13) SCBAG(11) SCB(10) SC(10) s(10) SCBA(10) SCB(10) SC(10) s(10) C(9) A(7) B(8) 理論證明 定理 如果 h滿足單調(diào)條件，則當(dāng) A*算法擴(kuò)展節(jié)點(diǎn) n時(shí)，該節(jié)點(diǎn)就已經(jīng)找到了通往它的最佳路徑，即 g(n)=g*(n)。 ? 在 h(n)滿足單調(diào)性限制下的 A*算法常被稱為改進(jìn)的 A*算法。 例 2：修改 h(n) S A D B T C 11 1 9 1 6 3 1 4 6 18 1 h=20 h=14 h=8 h=1 h=4 h=19 h=18 h=17 h=16 h=0 總結(jié)：實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵 ? 算法的完備性 ? 算法的可采納性 ? 啟發(fā)函數(shù)強(qiáng)弱對(duì)結(jié)果的影響 算法的完備性 對(duì)于一類 可解的 問(wèn)題和一個(gè)搜索過(guò)程，如果運(yùn)用該搜索過(guò)程 一定能求得該類問(wèn)題得解 ，則稱該搜索過(guò)程為完備的，否則為不完備的。 算法的可采納性 可納性的含義： 對(duì)任一狀態(tài)空間圖，當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在 時(shí)，如果搜索算法總能在 有限步驟內(nèi) 找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的 最佳路徑 ，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。 啟發(fā)函數(shù)強(qiáng)弱對(duì)結(jié)果的影響 1 ? 啟發(fā)函數(shù)強(qiáng)弱的衡量： h(n)接近 h*(n)的程度 ? 理想情況： h(n)＝ h*(n)， ? 實(shí)際上 : h(n)=h*(n) (越接近越好 ) ? 原因： A*算法的搜索效率很大程度上取決于估價(jià)函數(shù) h(n)。一般來(lái)說(shuō)，在滿足 h(n) ≤h*(n)的前提下， h(n)的值越大越好。 h(n)的值越大，說(shuō)明它攜帶的啟發(fā)性信息越多， A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少，搜索效率就越高。 啟發(fā)函數(shù)強(qiáng)弱對(duì)結(jié)果的影響 2 ? h(n)滿足單調(diào)性限制下的 A*算法更好 ? 原因： 能夠保證，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)就已經(jīng)找到了通往這個(gè)節(jié)點(diǎn)的最佳路徑。 ? 在 h(n)滿足單調(diào)性限制下的 A*算法常被稱為改進(jìn)的 A*算法。 ? 基本思想 ? 圖搜索分類 狀態(tài)空間搜索的基本思想 ? 先把問(wèn)題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問(wèn)題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。 ? 若出現(xiàn)，則搜索成功，找到了問(wèn)題的解； ? 若沒(méi)出現(xiàn)，則 再按照某種搜索策略 從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 ? 重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒(méi)有可供操作的節(jié)點(diǎn)為止。 圖搜索分類 ? 無(wú)信息搜索 – 搜索按預(yù)定的規(guī)則進(jìn)行，不使用與問(wèn)題有關(guān)的啟發(fā)式信息 ? 啟發(fā)式搜索 – 搜索中使用與問(wèn)題有關(guān)的啟發(fā)式信息 ,并以這些啟發(fā)式信息指導(dǎo)搜索過(guò)程 (可以提高效率 ) 本章小結(jié) ? 搜索策略 ? 狀態(tài)空間搜索 ? 無(wú)信息搜索 ? 啟發(fā)式搜索 ? 搜索方法的關(guān)系 ? 參考第 , 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 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 1 3 4 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 寬度優(yōu)先搜索圖 22 2 3 4 1 8 5 7 6 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 4 8 1 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 5 7 4 6 2 8 1 4 3 7 6 5 2 4 8 1 3 7 6 5 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4 8 3 4 2 1 7 6 5 8 1 3 2 4 7 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 3 7 8 4 6 1 5 2 8 3 7 4 6 1 5 2 8 3 7 1 6 5 4 解的路徑： 1－ 3－ 8－ 16－ 26 2 8 3 1 4 7 6 5 2 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 2 8 3 1 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 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 1 3 4 5 6 7 8 9 10 2 深度優(yōu)先搜索圖 8 3 4 2 1 7 6 5 11 8 3 4 2 1 7 6 5 8 3 4 2 1 5 7 6 8 3 4 2 1 7 6 5 8 4 2 3 1 7 6 5 8 3 4 2 6 1 7 5 3 4 8 2 1 7 6 5 8 3 4 7 2 1 6 5 12 13 14 19 18 15 16 3 4 8 2 1 7 6 5 17 深度優(yōu)先搜索圖（續(xù)） 2 8 3 1 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 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 1 3 4 5 6 7 14 8 11 16 9 10 12 13 17 有界深度優(yōu)先搜索圖 dm=4 go2 2 解的路徑： 1－ 3－ 14－ 16－ 17 演講完畢，謝謝觀看！