【正文】 索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility)1968 ★o 1)定義n 在 存在 從 初始狀態(tài) 節(jié)點(diǎn)到 目標(biāo)狀態(tài) 節(jié)點(diǎn) 解答路徑 的情況下，若一個(gè)搜索法 總能找到最短（代價(jià)最?。┑慕獯鹇窂?，則稱該 狀態(tài)空間 中的 搜索算法 具有可采納性，也叫最優(yōu)性 。n 如， 寬度優(yōu)先 的搜索算法是 可采納的 ，只是搜索 效率不高 。o 2) A算法的可采納性 ——定義 f*(n)=g*(n)+h*(n)n n搜索圖 G中 最短解答路徑 的節(jié)點(diǎn)；n f*(n) s經(jīng)節(jié)點(diǎn) n到 ng的 實(shí)際 最短解答路徑 的路徑代價(jià)；n g*(n)該路徑 前段 （從 s到 n）的路徑代價(jià)；n h*(n)該路徑 后段 （從 n到 ng）的路徑代價(jià)；2023/5/15 133啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility) ★o 3) 評(píng)價(jià)函數(shù) f與 f*的比較n f(n)、 g(n)、 h(n)分別是f*(n)、 g*(n)、 h*(n)的 近似值（估計(jì)值）n 理想情況下：o 若 g(n)=g*(n)、 h(n)=h*(n)，o 則搜索過(guò)程中， 每次都正確選擇，o 不擴(kuò)展任何無(wú)關(guān)的節(jié)點(diǎn) 。n 實(shí)際情況： 設(shè)計(jì)接近 f*的 f是很困難的o 在算法執(zhí)行過(guò)程中， o g(n)容易從已經(jīng)生成的搜索樹(shù)中計(jì)算出來(lái)Sn 搜索圖 Gng2023/5/15 134啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility) ★o 3) 評(píng)價(jià)函數(shù) f與 f*的比較n 理想情況下：o 若 g(n)=g*(n)、 h(n)=h*(n)， 不擴(kuò)展無(wú)關(guān)的節(jié)點(diǎn)n 實(shí)際情況：o 設(shè)計(jì)接近 f*的 f是很困難的n 在算法執(zhí)行過(guò)程中， n g(n)容易從已經(jīng)生成的搜索樹(shù)中計(jì)算出來(lái)，比如就以節(jié)點(diǎn)深度 d(n)當(dāng)做 g(n),且有 g(n)=g*(n)o h(n)盡可能 靠近 h*(n) ——A算法的關(guān)鍵 。2023/5/15 135啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility)o 4)改進(jìn)啟發(fā)式函數(shù) ——八數(shù)碼游戲n f(n)=d(n)+w(n),其中n w(n)表示 錯(cuò)位的棋牌個(gè)數(shù) ，不夠貼切，錯(cuò)誤的擴(kuò)展了節(jié)點(diǎn) d；n p(n)節(jié)點(diǎn) n與目標(biāo)狀態(tài)節(jié)點(diǎn)比較， 錯(cuò)位棋牌在不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和 ；n p(n)比 w(n)更接近于 h*(n)p(n)不僅考慮了棋牌的錯(cuò)位因素， 還考慮了錯(cuò)位的距離（移動(dòng)距離）2023/5/15 136啟發(fā)式搜索啟發(fā)式搜索——4)改進(jìn)啟發(fā)式函數(shù) —— 八數(shù)碼游戲n f(s)計(jì)算實(shí)例初始布局 s目標(biāo)布局 ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)0 4 4 p(s):錯(cuò)位棋牌移動(dòng)距離d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)0 5 5 1 1 1 2 2023/5/15 137初始化OPEN:={s5} CLOSE:={} 目標(biāo)布局 ng2023/5/15 138循環(huán) 1CLOSE:={s5} OPEN:={a b c} a7b5c7} b5 a7 c7}目標(biāo)布局 ng2023/5/15 139循環(huán) 2CLOSE:={s5 b5} OPEN:={a7 c7 d e i} d7e5i7} OPEN:={e5 a7 c7d7目標(biāo)布局 ng2023/5/15 140循環(huán) 3CLOSE:={s5 b5 e5} OPEN:={a7 c7 d7 i7 l m} l5 m7} OPEN:={l5 a7 c7 d7 i7目標(biāo)布局 ng2023/5/15 141CLOSE:={s5,b5,e5,l5} 循環(huán) 4OPEN:={a7 c7 d7 i7 m7 n} n5} OPEN:={n5 a7 c7 d7 i7 m7} 目標(biāo)布局 ng2023/5/15 142CLOSE:={s5,b5,e5,l5,n5} 循環(huán) 5OPEN:={a7 c7 d7 i7 m7 o g} o7 g5} OPEN:={g5 a7 c7 d7 i7m7 o7目標(biāo)布局 ng2023/5/15 143循環(huán) 6成功結(jié)束最理想搜索圖 G目標(biāo)布局 ng2023/5/15 144避免了錯(cuò)誤選擇2023/5/15 145啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility)o 5) A*算法 定義 ★ ：o 在 A算法 中，規(guī)定 h(n)≤h*(n)。o 經(jīng)如此限制以后的 A算法 就是 A*算法 。n A*算法是 可采納的 ， 即總能搜索到 最短解答路徑n 【 回顧： 八數(shù)碼游戲的 h(n)】o w(n)錯(cuò)位的棋牌個(gè)數(shù)o p(n)錯(cuò)位棋牌在不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和 ；o 上述兩者 均是可采納的 。 (想想為什么 )2023/5/15 146啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility)o 5) A*算法 定義：o 在 A算法 中，規(guī)定 h(n)≤h*(n)。o 經(jīng)如此限制以后的 A算法 就是 A*算法 。n A*算法是 可采納的 ， 即總能搜索到 最短解答路徑n 證明： 【 《 人工智能 上冊(cè) 》 陸汝 鈐鈐 P248】o 1）如果存在一條從初始狀態(tài)到目標(biāo)狀態(tài)的解答路徑，則 一定存在一條最短解答通路 ；o 2）設(shè) 狀態(tài) n’是最短解答路徑上的一個(gè)狀態(tài) ，那么經(jīng)過(guò)有限步后， n’必然會(huì)成為 OPEN表的第一個(gè)節(jié)點(diǎn)；o 3）因?yàn)?最短解答路徑只有有限個(gè)節(jié)點(diǎn) n’，所以有限步后算法必然因到達(dá)目標(biāo)狀態(tài) ng。這就是最優(yōu)解。o 證明完畢。2023/5/15 147啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility)o 5)滿足可采納性條件的算法 ——A*算法n 證明：o 2）設(shè) 狀態(tài) n’是最短解答路徑上的一個(gè)狀態(tài) ，那么經(jīng)過(guò)有限步后，n’必然會(huì)成為 OPEN表的第一個(gè)節(jié)點(diǎn)；o f(n’)=g(n’)+h(n’)o ∵ 根據(jù)假設(shè)， n’在最短解答路徑上o ∴ 經(jīng)過(guò)有限步驟后， g(n’)= g*(n’)o ∴ f(n’)=g*(n’)+h(n’)o ∵ h(n)≤h*(n)o ∴ f(n’)=g*(n’)+h(n’) ≤ g*(n’)+h*(n’)=f*(n’)o ∵ f*(n’)= f*(ng)o ∴ f(n’) ≤f*(ng)2023/5/15 148啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility)o 5)滿足可采納性條件的算法 ——A*算法n 證明：o 2）設(shè) 狀態(tài) n’是最短解答路徑上的一個(gè)狀態(tài) ，那么經(jīng)過(guò)有限步后， n’必然會(huì)成為 OPEN表的第一個(gè)節(jié)點(diǎn)；o 設(shè) OPEN表中 n’之前的節(jié)點(diǎn)只有有限個(gè)，設(shè)為 N個(gè)，其中估計(jì)值最小者為 a1，并稱之為 第一代節(jié)點(diǎn) ；由第一代節(jié)點(diǎn)生成的節(jié)點(diǎn)稱為 第二代節(jié)點(diǎn) ，其中估計(jì)值最小者為 a2；o a2≥a1+e(其中， e0，表示每擴(kuò)展一次起碼的代價(jià) )o 擴(kuò)展 j代后， aj ≥a1+(j1)eo 當(dāng) j足夠大時(shí)一定有 aj f*(ng)o ∵ f(n’) ≤f*(ng)且 OPEN表中 n’之前的節(jié)點(diǎn)經(jīng)過(guò) j次擴(kuò)展后的最小估計(jì)值 aj f*(ng) ≥f(n’) o ∴ 經(jīng)過(guò)有限步后， n’必然會(huì)成為 OPEN表的第一個(gè)節(jié)點(diǎn)2023/5/15 149啟發(fā)式搜索啟發(fā)式搜索——（ 2）啟發(fā)式函數(shù)的強(qiáng)弱及其影響 ★o h(n)接近 h*(n)的程度 ——衡量啟發(fā)式函數(shù)的強(qiáng)弱n h(n)h*(n)且 差距較大 時(shí)， OPEN表中節(jié)點(diǎn)排序的誤差較大 ， h(n)過(guò)弱 ，產(chǎn)生較大的搜索圖；n h(n)h*(n)， h(n)過(guò)強(qiáng) ， A算法失去可采納性 ，不能確保找到最短解答路徑；n h(n)=h*(n)是最理想 的， OPEN表中節(jié)點(diǎn)排序沒(méi)有誤差 ， 可以確保產(chǎn)生最小的搜索圖，搜索到最短解答路徑；o 無(wú)法設(shè)計(jì)n A*算法搜索問(wèn)題解答的關(guān)鍵oh(n)在滿足 h(n) ≤ h*(n)的條件下，越大越好！2023/5/15 150啟發(fā)式搜索啟發(fā)式搜索——（ 2）啟發(fā)式函數(shù)的強(qiáng)弱及其影響 ★o 定理：解決同一問(wèn)題的兩個(gè) A*算法 A1和 A2，n 若 h1(n) ≤ h2(n) ≤ h*(n)且 g1(n)=g2(n)n 則 t(A1) ≥ t(A2)n 其中， h h2分別是算法 A A2的啟發(fā)式函數(shù)， t指示相應(yīng)算法到達(dá)目標(biāo)狀態(tài)時(shí) 搜索圖含的節(jié)點(diǎn)總數(shù) 。n 【 證明： 《 人工智能 上冊(cè) 》 陸汝鈐 P250） 】o 八數(shù)碼游戲： w(n)≤p(n) ≤ h*(n)o p(n)擴(kuò)展出的節(jié)點(diǎn)總數(shù) ≤ t(w(n))2023/5/15 151啟發(fā)式搜索啟發(fā)式搜索——（ 2）設(shè)計(jì) h(n)的實(shí)用考慮 ★o 和寬度優(yōu)先和深度優(yōu)先的關(guān)系n 若 h(n)≡0, 則意味著先進(jìn)入 OPEN表的節(jié)點(diǎn)會(huì)優(yōu)先被考察和擴(kuò)展，因?yàn)榧词共灰?d(n)作為 g(n), 通常先進(jìn)入OPEN表的節(jié)點(diǎn) n也具有較小的 g(n)值n 若 g(n)≡0,則導(dǎo)致后進(jìn)入 OPEN表的節(jié)點(diǎn)會(huì)優(yōu)先被考察和擴(kuò)展，因?yàn)楹筮M(jìn)入 OPEN表的節(jié)點(diǎn) n往往更接近于目標(biāo)狀態(tài)，即 h(n)值較小，從而使搜索過(guò)程接近于深度優(yōu)先的搜索策略 2023/5/15 152啟發(fā)式搜索啟發(fā)式搜索——（ 2）設(shè)計(jì) h(n)的實(shí)用考慮o 為更有效地搜索解答 ，可使用評(píng)價(jià)函數(shù) f(n) = g(n) + wh(n)， w用作加權(quán) n 在搜索圖的 淺層 （上部），可讓 w取較大值 ，以使 g(n)所占比例很小，從而突出啟發(fā)式函數(shù)的作用，加速向 縱深方向 搜索 n 一旦搜索到 較深 的層次，又讓 w取較小值 ，以使g(n)所占比例很大，并確保 wh(n)≤h* (n),從而引導(dǎo)搜索向橫廣方向發(fā)展，尋找到較短的解答路徑。 2023/5/15 153迭代加深迭代加深 A*算法算法 o 由于 A*算法把所有生成的節(jié)點(diǎn)保存在內(nèi)存中，所以 A*算法在耗盡計(jì)算時(shí)間之前一般早已經(jīng)把空間耗盡了。o 目前開(kāi)發(fā)了一些新的算法，它們的目的是為了 克服空間問(wèn)題 。o 但一般不滿足最優(yōu)性或完備性，如迭代加深 A*算法 IDA*、簡(jiǎn)化內(nèi)存受限 A*算法 SMA*等。o 下面簡(jiǎn)單介紹 IDA*算法。 2023/5/15 154o 迭代加深搜索算法，它以 深度優(yōu)先 的方式在有限制的深度內(nèi)搜索目標(biāo)節(jié)點(diǎn)。o 在每個(gè)深度上，該算法在每個(gè)深度上檢查目標(biāo)節(jié)點(diǎn)是否出現(xiàn)，如果出現(xiàn)則停止，否則深度加 1繼續(xù)搜索。o 而 A*算法是選擇具有最小估價(jià)函數(shù)值的節(jié)點(diǎn)擴(kuò)展。2023/5/15 155o 迭代加深 A* 搜索算法 IDA*是上述兩種算法的結(jié)合 。o 這里啟發(fā)式函數(shù)用做深度的限制，而不是選擇擴(kuò)展節(jié)點(diǎn)的排序。2023/5/15 156迭代加深 A*算法Procedure IDA*算法Begin (1) 初始化當(dāng)前的深度限制 c=1 (2) 把初始節(jié)點(diǎn)壓入棧 。 并假定 (3) While 棧不空橋 do Begin 彈出棧頂元素 n If n=goal, Then 結(jié)束 , 返回 n以及從初始節(jié)點(diǎn)到 n的路徑 Else do Begin For n 的每個(gè)子節(jié)點(diǎn) If , Then 把 壓入棧 Else End for End End While (4) If 棧為空并且 , Then 停止并退出 (5) If 棧為空并且