【正文】 1 2 3 8 4 7 6 5 15(6) （例 2續(xù)） 11(5) 解的路徑： 12681011141618 14(6) 1 3 8 2 4 7 6 5 17(8) 1 3 8 2 4 7 6 5 16(7) 8 1 3 2 4 7 6 5 8 1 3 2 6 4 7 5 12(5) 13(5) 18(8) 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 換一條路徑 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) 算法討論 ? 存在的問(wèn)題 ? 解決方法 代價(jià)樹(shù)的有界深度優(yōu)先搜索 ? 基本思想 ? 搜索過(guò)程 ? 實(shí)例 基本思想 ? 當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按 f(x)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估值，并選擇其中最小的先擴(kuò)展。 n，將其子節(jié)點(diǎn) 按代價(jià)從小到大放入 OPEN表的首部， 并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（ 2）步。若是，則求得了問(wèn)題的解，退出。 ? 例 如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。 n不可擴(kuò)展轉(zhuǎn)（ 2）步。 算法討論 ? 存在問(wèn)題 ? 改進(jìn)方法 動(dòng)態(tài)規(guī)劃法 ? 基本思想 ? 搜索過(guò)程 ? 實(shí)例 基本思想 ? 當(dāng)有多條到達(dá)某一公共節(jié)點(diǎn)的路徑，只保留代價(jià)最小的路徑 搜索過(guò)程 s0放入 OPEN表 ,令 g(s0)=0 OPEN表為空，則問(wèn)題無(wú)解，退出 OPEN表的第一個(gè)節(jié)點(diǎn)（記為 n節(jié)點(diǎn)）取出放入 CLOSED表 n是否為目標(biāo)節(jié)點(diǎn)。 ? 例 如圖是八城市間的交通圖，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示。 n不可擴(kuò)展轉(zhuǎn)（ 2）步。 – 表示： g(x)表示從初始節(jié)點(diǎn) s0到節(jié)點(diǎn) x的代價(jià) – 例 : g(A)=g(s0)+c(s0,A)=0+2=2 g(C)=g(A)+c(A,C)=2+4=6 ? 代價(jià)樹(shù)：邊上標(biāo)有代價(jià)的搜索樹(shù) s0 A C B 3 2 4 s0 A B C 2 3 4 代價(jià)驅(qū)動(dòng)的搜索策略 ? 代價(jià)樹(shù)的廣度優(yōu)先搜索 ? 動(dòng)態(tài)規(guī)劃法（改進(jìn)的代價(jià)樹(shù)廣度優(yōu)先搜索 ) ? 代價(jià)樹(shù)的深度優(yōu)先搜索 代價(jià)樹(shù)的廣度優(yōu)先搜索 ? 基本思想 ? 搜索過(guò)程 ? 實(shí)例 ? 存在問(wèn)題 ? 解決方法 (動(dòng)態(tài)規(guī)劃法） 基本思想 ? open表的節(jié)點(diǎn)順序按的節(jié)點(diǎn)代價(jià)排列（從小到大） 搜索過(guò)程 s0放入 OPEN表 ,令 g(s0)=0 OPEN表為空，則問(wèn)題無(wú)解，退出 OPEN表的第一個(gè)節(jié)點(diǎn)（記為 n節(jié)點(diǎn)）取出放入 CLOSED表 n是否為目標(biāo)節(jié)點(diǎn)。 ? 啟發(fā)性信息 ? 評(píng)估函數(shù) 評(píng)估函數(shù)的表示 ? 含義：用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱(chēng)為估價(jià)函數(shù) ? 表示： f(x)=g(x)+h(x) – g(x)是從初始結(jié)點(diǎn) S0到 x實(shí)際代價(jià) – h(x)是從 x到目標(biāo)結(jié)點(diǎn) Sg的最佳路徑的估計(jì)代價(jià) , 啟發(fā)性信息的函數(shù)描述 。 ? 搜索技術(shù)的應(yīng)用－智能搜索引擎 ? 啟發(fā)式搜索涉及的基本概念 ? 基本的啟發(fā)式搜索方法 – 代價(jià)樹(shù)的廣度優(yōu)先搜索 – 動(dòng)態(tài)規(guī)劃法（改進(jìn)的代價(jià)樹(shù)廣度優(yōu)先搜索 ) – 代價(jià)樹(shù)的深度優(yōu)先搜索 (局部?jī)?yōu)先搜索 ) – 代價(jià)樹(shù) 有界深度優(yōu)先搜索 – 局部擇優(yōu) A算法 – A算法 (全局優(yōu)先搜索 ) 啟發(fā)式搜索概念 ? 啟發(fā)式搜索與無(wú)信息搜索 無(wú)信息（盲目）搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中 獲得的中間信息并不改變控制策略。 81 啟發(fā)式搜索：在搜索中加入了 與問(wèn)題有關(guān)的啟發(fā)性信息 ，用于指導(dǎo) 搜索朝著 最有希望的方向前進(jìn) ，加速問(wèn)題的求解過(guò)程并 找到最優(yōu)解。 ? 例 重排九宮問(wèn)題 f(x)=d(x)+h(x) 代價(jià)的計(jì)算 ? 邊代價(jià)：從父節(jié)點(diǎn)到子節(jié)點(diǎn)的代價(jià) – 表示： c(x1,x2)表示從父節(jié)點(diǎn) x1到子節(jié)點(diǎn) x2的代價(jià) – 例： c(s0,A)=2 c(A,C)=4 ? 代價(jià)：從一個(gè)節(jié)點(diǎn)經(jīng)過(guò)一條支路到另一個(gè)節(jié)點(diǎn)所支付的代價(jià)。若是，則求得了問(wèn)題的解，退出。 n，將其子節(jié)點(diǎn)放入 OPEN表中，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針； 計(jì)算各個(gè)子節(jié)點(diǎn)的代價(jià)，并按各個(gè)節(jié)點(diǎn)的代價(jià)對(duì)表的全部節(jié)點(diǎn)進(jìn)行排序（按從小到大的順序）， 然后轉(zhuǎn)（ 2）步。求從 S到 T的最小交通費(fèi)用 代寬演示 .ppt S A D E B F T C 3 4 4 5 2 5 4 4 3 ? 代價(jià)樹(shù)的廣度優(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表（代價(jià)樹(shù)的廣度優(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é)束。若是，則求得了問(wèn)題的解，退出。 n，將其子節(jié)點(diǎn)放入 OPEN表中，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針；計(jì)算各個(gè)子節(jié)點(diǎn)的代價(jià)， 若新出現(xiàn)的節(jié)點(diǎn)是多條路徑都到達(dá)的節(jié)點(diǎn)，則只選代價(jià)最小的路徑，其余刪去， 并按各個(gè)節(jié)點(diǎn)的代價(jià)對(duì)表的全部節(jié)點(diǎn)進(jìn)行排序（按從小到大的順），然后轉(zhuǎn)（ 2）步。求從 S到 T的最小交通費(fèi)用 動(dòng)態(tài)規(guī)劃 .ppt S A D E B F T C 3 4 4 5 2 5 4 4 3 ? 動(dòng)態(tài)規(guī)劃法（例） 1 2 3 4 5 6 7 10 11 8 9 14 S(0) D1(4) A1(3) B1( 7 ) D2(8) A2(9) E1(6) F1(10) T1(13) C1(11) E2(12) 3 4 4 4 5 5 5 5 4 2 3 B2(11) ? Open表（ 動(dòng)態(tài)規(guī)劃法） 初始 (S(0)) 1 (A1(3), D1(4)) 2 (D1(4), B1(7),D2(8)) （刪除） 3 (E1(6),B1(7),A2(9)) 4 (B1(7),F1(10),B2(11) ) 5 (F1(10),C1(11),E2(12) ) 6 (C1(11),T1(13)) 7 (T1(13)) 8 結(jié)束 代價(jià)樹(shù)的深度優(yōu)先搜索 ? 基本思想 ? 搜索過(guò)程 ? 實(shí)例 ? 算法討論 ? 基本思想 ： 在剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，即表的首部存放剛擴(kuò)展的所有子節(jié)點(diǎn)（按代價(jià)從小到大排序） ? 搜索過(guò)程： OPEN表，令 g(s0)=0 OPEN表為空，則問(wèn)題無(wú)解，退出 OPEN表的第一個(gè)節(jié)點(diǎn)（記為 n節(jié)點(diǎn)）取出放入 CLOSED表 n是否為目標(biāo)節(jié)點(diǎn)。