【正文】 出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因 ? 在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn) A。在 3 3的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖 ? 算符有： – R1: 如果滿足條件 則 空格左移 – R2: 如果滿足條件 則 空格上移 – R3: 如果滿足條件 則 空格右移 – R4: 如果滿足條件 則 空格下移 – 注：條件指有位置并且不重復(fù) ? 沖突解決方法：算符序號 ? f(x)=d(x)+h(x) d(x):節(jié)點(diǎn) x的深度， ? h(x):節(jié)點(diǎn) x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)。在 3 3的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖 ? 算符有： – R1: 如果滿足條件 則 空格左移 – R2: 如果滿足條件 則 空格上移 – R3: 如果滿足條件 則 空格右移 – R4: 如果滿足條件 則 空格下移 – 注：條件指有位置并且不重復(fù) ? 沖突解決方法：算符序號 ? f(x)=d(x)+h(x) d(x):節(jié)點(diǎn) x的深度，深度 =4 ? h(x):節(jié)點(diǎn) x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)。若是，則求得了問題的解，退出。 局部擇優(yōu) A算法例：重排九宮問題 例：重排九宮問題。 ? 搜索過程： OPEN表，令 g(s0)=0 OPEN表為空，則問題無解，退出 OPEN表的第一個節(jié)點(diǎn)（記為 n節(jié)點(diǎn)）取出放入 CLOSED表 n是否為目標(biāo)節(jié)點(diǎn)。 類型： 可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。 一般來說 ， 某節(jié)點(diǎn)中的 “ 不在位 ” 的數(shù)碼個數(shù)越多 ， 說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn) 。求從 S到 T的最小交通費(fèi)用 S A D E B F T C 3 4 4 5 2 5 4 4 3 ? 代價樹的有界深度優(yōu)先搜索（例） dm=4 1 2 3 4 5 13 14 6 7 10 15 16 8 9 11 14 S(0) D1(4) A1(3) B1( 7 ) D2(8) A2(9) E3(6) F3(10) T1(13) C1(11) E2(10) E1(12) 12 D3(14) F1(16) B2(15) F2(14) 3 4 4 4 5 5 5 2 5 4 2 2 4 5 4 3 B3(11) 代價樹搜索的總結(jié) ? 優(yōu)點(diǎn) ? 不足：局限性 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 1（ 0） 3(1) 4(1) 5(1) 九宮問題使用代價的局限性 2（ 1） 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 6(2) 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 7(2) 10(4) 8(3) 9(4) A算法 ? 啟發(fā)性函數(shù) ? A算法 ? A*算法 ? 算法討論 啟發(fā)性函數(shù)的表示 ? 含義：用于估價節(jié)點(diǎn)重要性的函數(shù)稱為估價函數(shù) ? 表示： f(x)=g(x)+h(x) – g(x)是從初始結(jié)點(diǎn) S0到 x實際代價 – h(x)是從 x到目標(biāo)結(jié)點(diǎn) Sg的最佳路徑的估計代價 , 啟發(fā)性信息的函數(shù)描述 。若是，則求得了問題的解，退出。 n，將其子節(jié)點(diǎn) 按代價從小到大放入 OPEN表的首部， 并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（ 2）步。 ? 例 如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價）如圖中數(shù)字所示。 算法討論 ? 存在問題 ? 改進(jìn)方法 動態(tài)規(guī)劃法 ? 基本思想 ? 搜索過程 ? 實例 基本思想 ? 當(dāng)有多條到達(dá)某一公共節(jié)點(diǎn)的路徑，只保留代價最小的路徑 搜索過程 s0放入 OPEN表 ,令 g(s0)=0 OPEN表為空，則問題無解，退出 OPEN表的第一個節(jié)點(diǎn)（記為 n節(jié)點(diǎn)）取出放入 CLOSED表 n是否為目標(biāo)節(jié)點(diǎn)。 n不可擴(kuò)展轉(zhuǎn)（ 2）步。 ? 啟發(fā)性信息 ? 評估函數(shù) 評估函數(shù)的表示 ? 含義：用于估價節(jié)點(diǎn)重要性的函數(shù)稱為估價函數(shù) ? 表示： f(x)=g(x)+h(x) – g(x)是從初始結(jié)點(diǎn) S0到 x實際代價 – h(x)是從 x到目標(biāo)結(jié)點(diǎn) Sg的最佳路徑的估計代價 , 啟發(fā)性信息的函數(shù)描述 。 81 啟發(fā)式搜索：在搜索中加入了 與問題有關(guān)的啟發(fā)性信息 ，用于指導(dǎo) 搜索朝著 最有希望的方向前進(jìn) ，加速問題的求解過程并 找到最優(yōu)解。若是，則求得了問題的解，退出。求從 S到 T的最小交通費(fèi)用 代寬演示 .ppt S A D E B F T C 3 4 4 5 2 5 4 4 3 ? 代價樹的廣度優(yōu)先搜索（例） 1 2 3 4 5 6 7 10 11 12 13 8 9 19 20 21 15 17 18 14 S(0) D1(4) A1(3) B1( 7 ) D2(8) A2(9) E1(6) F1(10) T1(13) C1(11) B2(11) B3(13) E3(10) E2(12) 16 D3(14) F3(16) B4(15) F2(14) C3(17) A3(15) C2(15) 3 4 4 4 5 5 5 2 4 5 4 2 2 4 5 4 4 4 4 3 ? Open表（代價樹的廣度優(yōu)先搜索） 初始 (S(0)) 1 (A1(3), D1(4)) 2 (D1(4), B1(7),D2(8)) 3 (E1(6),B1(7),D2(8),A2(9)) 4 (B1(7),D2(8),A2(9),F1(10),B2(11)) 5 (D2(8),A2(9),F1(10),B2(11),C1(11),E2(12)) 6 (A2(9),F1(10),E3(10),B2(11),C1(11),E2(12)) 7 (F1(10),E3(10),B2(11),C1(11),E2(12),B3(13)) 8 (E3(10),B2(11),C1(11),E2(12),B3(13),T1(13)) 9 (B2(11),C1(11),E2(12),B3(13),T1(13),F2(14),B4(15)) 10 (C1(11),E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15)) 11 (E2(12),B3(13),T1(13),F2(14),B4(15),A3(15),C2(15)) 12 (B3(13),T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16)) 13 (T1(13),F2(14),D3(14),B4(15),A3(15),C2(15),F3(16),C3(17)) 14 T1(13)為目標(biāo)節(jié)點(diǎn)，結(jié)束。 n，將其子節(jié)點(diǎn)放入 OPEN表中，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；計算各個子節(jié)點(diǎn)的代價， 若新出現(xiàn)的節(jié)點(diǎn)是多條路徑都到達(dá)的節(jié)點(diǎn)，則只選代價最小的路徑，其余刪去， 并按各個節(jié)點(diǎn)的代價對表的全部節(jié)點(diǎn)進(jìn)行排序（按從小到大的順），然后轉(zhuǎn)（ 2）步。 n不可擴(kuò)展轉(zhuǎn)（ 2）步。 代價樹的有界深度優(yōu)先搜索過程 OPEN表，令 g(s0)=0 OPEN表為空，則問題無解，退出 OPEN表的第一個節(jié)點(diǎn)（記為 n節(jié)點(diǎn)）取出放入 CLOSED表 n是否為目標(biāo)節(jié)點(diǎn)。 ? 例 如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價）如圖中數(shù)字所示。 d(n)表示節(jié)點(diǎn) n在搜索樹中的深度它說明是用從 S0到 n的路徑上的單位代價表示實際代價 ， W(n)表示節(jié)點(diǎn) n中 “ 不在位 ” 的數(shù)碼個數(shù) ， 作為啟發(fā)信息 。 由于估價函數(shù)中帶有問題自身的啟發(fā)性信息，因此， A算法也被稱為啟發(fā)式搜索算法。 局部擇優(yōu) A算法 ? 基本思想 ： 當(dāng)一個節(jié)點(diǎn)被擴(kuò)展后，按 f(x)對每一個子節(jié)點(diǎn)計算估值，并選擇其中最小的先擴(kuò)展。 n，用估價函數(shù) f(x)計算每個子節(jié)點(diǎn)的估價值，并將其子節(jié)點(diǎn)按估價值從小到大放入 OPEN表的首部 ，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（ 2）步。 ?對初始節(jié)點(diǎn) S0， 由于 d(S0)=0， W(S0)=3， 因此有 f(S0)=0+3=3 2 8 3 1 4