【正文】 2023/5/15 156迭代加深 A*算法Procedure IDA*算法Begin (1) 初始化當(dāng)前的深度限制 c=1 (2) 把初始節(jié)點(diǎn)壓入棧 。2023/5/15 155o 迭代加深 A* 搜索算法 IDA*是上述兩種算法的結(jié)合 。o 在每個(gè)深度上，該算法在每個(gè)深度上檢查目標(biāo)節(jié)點(diǎn)是否出現(xiàn)，如果出現(xiàn)則停止，否則深度加 1繼續(xù)搜索。o 下面簡(jiǎn)單介紹 IDA*算法。o 目前開發(fā)了一些新的算法，它們的目的是為了 克服空間問題 。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)值較小，從而使搜索過程接近于深度優(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ā)展，尋找到較短的解答路徑。o 證明完畢。n A*算法是 可采納的 ， 即總能搜索到 最短解答路徑n 證明： 【 《 人工智能 上冊(cè) 》 陸汝 鈐鈐 P248】o 1）如果存在一條從初始狀態(tài)到目標(biāo)狀態(tài)的解答路徑，則 一定存在一條最短解答通路 ；o 2）設(shè) 狀態(tài) n’是最短解答路徑上的一個(gè)狀態(tài) ，那么經(jīng)過有限步后， n’必然會(huì)成為 OPEN表的第一個(gè)節(jié)點(diǎn)；o 3）因?yàn)?最短解答路徑只有有限個(gè)節(jié)點(diǎn) n’，所以有限步后算法必然因到達(dá)目標(biāo)狀態(tài) ng。 (想想為什么 )2023/5/15 146啟發(fā)式搜索啟發(fā)式搜索——（（ 1）搜索算法的可采納性）搜索算法的可采納性 (Admissibility)o 5) A*算法 定義：o 在 A算法 中，規(guī)定 h(n)≤h*(n)。o 經(jīng)如此限制以后的 A算法 就是 A*算法 。n 實(shí)際情況： 設(shè)計(jì)接近 f*的 f是很困難的o 在算法執(zhí)行過程中， o g(n)容易從已經(jīng)生成的搜索樹中計(jì)算出來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ò)展無關(guān)的節(jié)點(diǎn)n 實(shí)際情況：o 設(shè)計(jì)接近 f*的 f是很困難的n 在算法執(zhí)行過程中， n g(n)容易從已經(jīng)生成的搜索樹中計(jì)算出來，比如就以節(jié)點(diǎn)深度 d(n)當(dāng)做 g(n),且有 g(n)=g*(n)o h(n)盡可能 靠近 h*(n) ——A算法的關(guān)鍵 。n 如， 寬度優(yōu)先 的搜索算法是 可采納的 ，只是搜索 效率不高 。 2023/5/15 131啟發(fā)式搜索啟發(fā)式搜索——（理解）實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵因素（理解）o 實(shí)現(xiàn)啟發(fā)式搜索應(yīng)考慮的關(guān)鍵因素 ★ ：n （ 1）搜索算法的 可采納性 (Admissibility)?，F(xiàn)在，在節(jié)點(diǎn) S、 R、N中，節(jié)點(diǎn) S的估價(jià)函數(shù)值最小，所以下一步就會(huì)選擇 S節(jié)點(diǎn)擴(kuò)展?，F(xiàn)在，在節(jié)點(diǎn) P、 R、 N中，節(jié)點(diǎn) P具有最小的估價(jià)函數(shù)值，所以選擇節(jié)點(diǎn) P擴(kuò)展。在第 1步，得到兩個(gè)節(jié)點(diǎn) M和N，其估價(jià)函數(shù)值都為 1+8=9，因此可以任選一個(gè)節(jié)點(diǎn)擴(kuò)展。則給出下面的啟發(fā)式函數(shù)： 2023/5/15 128o h(n) = 2 如果 0 x 4并且 0 y 3 = 4 如果 0 x 4或者 0 y 3 = 8 如果 x = 0并且 y = 3 或者 x =4 并且 y= 0 =10 如果 x = 0 并且 y = 0 或者 x = 4并且 y = 3o 假定 g (n)表示搜索樹中搜索的深度，則根據(jù)圖搜索策略得下圖的搜索空間。 根節(jié)點(diǎn)深度 =0第第 n1層節(jié)點(diǎn)層節(jié)點(diǎn) dn1第第 n層節(jié)點(diǎn)層節(jié)點(diǎn) dn= dn1+1搜索圖 G2023/5/15 116啟發(fā)式搜索啟發(fā)式搜索——（算法（ 掌握掌握 ））啟發(fā)式算法啟發(fā)式算法 A實(shí)例實(shí)例 ———— 八數(shù)碼游戲八數(shù)碼游戲o 1)設(shè)計(jì)評(píng)價(jià)函數(shù) f(n)n f(n)計(jì)算實(shí)例初始布局 s目標(biāo)布局 ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)h(n): nng的最小路徑代價(jià) g(n):sn的最小路徑代價(jià) f(n):snng的最小路徑代價(jià) 0 4 4 注： W(S)不考慮空格2023/5/15 117初始化OPEN:={s4} CLOSE:={} 目標(biāo)布局 ng2023/5/15 118循環(huán) 1CLOSE:={s4} OPEN:={a b c} a6b4c6} b4a6目標(biāo)布局 ng2023/5/15 119循環(huán) 2CLOSE:={s4 b4} OPEN:={a6 c6 d e i} d5e5i6} OPEN:={d5 e5 a6 c6目標(biāo)布局 ng2023/5/15 120循環(huán) 3CLOSE:={s4 b4 d5} OPEN:={e5 a6 c6 i6 j k} OPEN:={e5 a6 c6 i6 j7 k6} OPEN:={e5k6j7} 目標(biāo)布局 ng2023/5/15 121循環(huán) 4CLOSE:={s4,b4,d5,e5} OPEN:={a6 c6 i6 k6 j7 l m} l5m7} OPEN:={l5 a6 c6 i6 k6 j7目標(biāo)布局 ng2023/5/15 122CLOSE:={s4,b4,d5,e5,l5} 循環(huán) 5OPEN:={a6 c6 i6 k6 j7 m7 n} n5} OPEN:={n5 a6 c6 i6 k6 j7m7} 目標(biāo)布局 ng2023/5/15 123循環(huán) 6CLOSE:={s4,b4,d5,e5,l5,n5} OPEN:={a6 c6 i6 k6 j7 m7 o g} o7g5} OPEN:={g5 a6 c6 i6 k6 j7 m7 o7目標(biāo)布局 ng2023/5/15 124循環(huán) 7成功結(jié)束目標(biāo)布局 ng2023/5/15 125最理想搜索圖 G2023/5/15 126判斷失誤2023/5/15 127 例 2 給定 4L和 3L的水壺各一個(gè)，水壺上沒有刻度，可以向水壺中加水。此過程生成一個(gè)明確的圖 G(搜索圖）和一個(gè) G的子集 T(搜索樹）。 對(duì)已在 CLOSE表上的每個(gè)M成員，作與第 2類同樣的處理，并把這些子結(jié)點(diǎn)從 CLOSE表移出，重新加入 OPEN表。對(duì)已經(jīng)在OPEN表上的每一個(gè) M成員，比較子節(jié)點(diǎn) ni經(jīng)由新、老父節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值 f(n,ni)、 f(ni)。 n為一目標(biāo)節(jié)點(diǎn)，則有解成功退出，此解是追蹤圖 G中沿著指針從 n到 S這條路徑而得到的；2023/5/15 112 G中出現(xiàn)過的M成員（全新結(jié)點(diǎn)）設(shè)置一個(gè)通向 n的指針。o 如何用評(píng)價(jià)函數(shù)來實(shí)現(xiàn) A算法 ? （ 掌握！ ） 2023/5/15 108啟發(fā)式搜索啟發(fā)式搜索——（算法（ 掌握掌握 ））o A算法 的設(shè)計(jì)與 一般圖搜索 相同，劃分為二個(gè)階段 ★ ：n 初始化 o 建立只包含初始狀態(tài)節(jié)點(diǎn) s的搜索圖 G:={s}o OPEN:={s}o CLOSE:={} n 搜索循環(huán)o MOVEFIRST(OPEN)取出 OPEN表首 的節(jié)點(diǎn) n o ⑥ 擴(kuò)展出 n的子節(jié)點(diǎn) ,插入搜索圖 G和 OPEN表 o ⑦ 適當(dāng)?shù)臉?biāo)記和修改指針（ 子節(jié)點(diǎn) ?父節(jié)點(diǎn) ）o ⑧ 排序 OPEN表（ 評(píng)價(jià)函數(shù) f(n)的值排序）n 通過循環(huán)地執(zhí)行該算法，搜索圖會(huì)因不斷有新節(jié)點(diǎn)加入而逐步長(zhǎng)大，直到搜索到目標(biāo)節(jié)點(diǎn)。2023/5/15 102 啟發(fā)式搜索啟發(fā)式搜索 ★一般圖搜索算法o 常用的簡(jiǎn)單方式：n 深度優(yōu)先n 寬度優(yōu)先n 【 缺點(diǎn)：節(jié)點(diǎn)排序的盲目性 】o 在白白 搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn) 后才碰到解答， 效率低o 提高 一般圖搜索 效率 的關(guān)鍵 ★n 優(yōu)化 OPEN表中節(jié)點(diǎn)的排序方式盲目搜索2023/5/15 103125634最理想情況：每次排序后 OPEN表表首元素 n總在解答路徑上2023/5/15 104啟發(fā)式搜索啟發(fā)式搜索o 啟發(fā)式知識(shí) 指導(dǎo) OPEN表排序 的 一般圖搜索 ：n 全局排序 ——對(duì) OPEN表中的 所有節(jié)點(diǎn)排序 ，使 最有希望 的節(jié)點(diǎn)排在表首。但對(duì)空間要求和深度優(yōu)先搜索一樣是適中的。它結(jié)合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點(diǎn)。o 寬度優(yōu)先搜索 需要指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復(fù)雜度和最大搜索深度呈線性關(guān)系。 End End whild (4)深度限制加 1,并返回 2。 (3)While棧不空并且深度在給定的深度限制之內(nèi) do Begin 彈出棧頂元素； If棧頂元素 =goal,返回并結(jié)束 。 2023/5/15 98 Procedure IterativedeepeningBegin(1)設(shè)置當(dāng)前深度限制 =1。 2023/5/15 97o 迭代加深搜索看起來會(huì)很浪費(fèi)，因?yàn)楹芏喙?jié)點(diǎn)都可能擴(kuò)展多次。o 如果根節(jié)點(diǎn)不是目標(biāo)，則深度加 1，通過典型的深度優(yōu)先算法，生成深度為 1的樹。2023/5/15 96o 迭代加深搜索 ，試圖嘗試所有可能的深度限制：n 首先深度為 0，n 然后深度為 1，n 然后為 2，等等。（ 3）有界深度搜索的主要問題是 深度限制值 dm的選取 。2023/5/15 94（ 2） 深度限制 dm不能太大 。 當(dāng)問題有解，且解的路徑長(zhǎng)度小于或等于 dm時(shí)，則搜索過程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。然后轉(zhuǎn)第 (2)步。 (7)擴(kuò)展節(jié)點(diǎn) n。 (5)如果節(jié)點(diǎn) n的深度 d(n)= dm，則轉(zhuǎn)第 (2)步 。(4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。 (3)把 OPEN表中的第一個(gè)節(jié)點(diǎn)取出放入 CLOSE表中。2023/5/15 92(1)把初始節(jié)點(diǎn) S0放入 OPEN表中，置 S0的深度 d(S0)=0。 ?節(jié)點(diǎn)排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識(shí)去指導(dǎo)排序，往往會(huì)在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解答，所以也稱為 盲目搜索 。 ?寬度優(yōu)先 —— 確保搜索到 最短的解答路徑 。這樣一來對(duì)于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個(gè)答案，要么最后找到一個(gè)答案，但路徑很長(zhǎng)而且不是最優(yōu)的答案。 主要問題是可能 搜索到了錯(cuò)誤的路徑上 。o 深度優(yōu)先搜索的存儲(chǔ)器要求是深度約束的線性函數(shù)。 假定限制值為 5。基于棧實(shí)現(xiàn)的深度優(yōu)先搜索算法： 2023/5/15 85 例 卒子穿陣問題 : 要求一卒子從頂部通過圖所示的列陣到達(dá)底部。若是，則求得了問題的解，成功并退出。2023/5/15 84(1)把初始節(jié)點(diǎn) S0放入 OPEN表； (2)如果 OPEN表為空，則問題無解，失敗并退出。?為保證找到解，應(yīng)選擇適當(dāng)?shù)?深度界限 ，或者采取不斷加大深度界限的辦法，反復(fù)搜索，直到找到解。 2023/