【文章內(nèi)容簡介】 Sg 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 1（ 3） 3(4) 4(5) 5(5) 7(6) 局部擇優(yōu) A算法，例 2（ 4） 6(5) 8 3 2 1 4 7 6 5 9(8) 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 10(7) 8(6) 8 1 3 2 4 7 6 5 1 3 8 2 4 7 6 5 8 1 3 7 2 4 6 5 1 2 3 8 4 7 6 5 15(10) 局部擇優(yōu) A算法，例 (續(xù)） 11(8) 解的路徑： 12681011141618 14(9) 1 3 8 2 4 7 6 5 17(10) 1 3 8 2 4 7 6 5 16(8) 8 1 3 2 4 7 6 5 8 1 3 2 6 4 7 5 12(9) 13(9) 18(8) 算法討論 ? 局部擇優(yōu) A算法存在的問題 ? 解決方法 限界局部擇優(yōu) A算法法 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）步。 d(n)=規(guī)定深度 THEN GO (2) n，用估價函數(shù) f(x)計算每個子節(jié)點(diǎn)的估價值，并將 其子節(jié)點(diǎn)按估價值從小到大放入 OPEN表的首部 ，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)（ 2）步。 限界局部擇優(yōu)：重排九宮問題 例：重排九宮問題。在 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ù)。 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 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 1（ 3） 3(4) 4(5) 5(5) 7(6) 限界局部擇優(yōu)搜索（例） d=4 2（ 4） 6(5) 8 3 2 1 4 7 6 5 9(9) 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 10(8) 8(6) 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 14(4) 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 2 8 3 7 1 4 6 5 11(8) 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 12(9) 13(10) 15(6) 18(6) 16(4) 17(4) ? Open表的變化 (限界局部擇優(yōu)搜索法） 初始 (1(3)) 1 (2(4),3(4),4(5),5(5)) 2 (6(5),7(6), 3(4),4(5),5(5)) 3 (8(6), 7(6), 3(4),4(5),5(5)) 4 (10(8),9(9), 7(6), 3(4),4(5),5(5)) d=4 5 ( 7(6), 3(4),4(5),5(5)) d=2 6 (11(8), 3(4),4(5),5(5)) d=3 7 ( 12(9),13(10), 3(4),4(5),5(5)) d=4 8 ( 3(4),4(5),5(5)) d=1 9 ( 14(4),15(6), 4(5),5(5)) d=2 7 (16(4), 15(10), 3(4),4(5),5(5)) d=3 8 (17(4),18(6), 15(10), 3(4),4(5),5(5)) d=4 9 17(4)為目標(biāo)節(jié)點(diǎn)，結(jié)束 算法討論 ? 局部擇優(yōu)搜索方法評價 ? 與深度優(yōu)先搜索比較 ? 缺陷 全局擇優(yōu)搜索 A算法描述 (1)把初始節(jié)點(diǎn) S0放入 Open表中， f(S0)=g(S0)+h(S0)； (2)如果 Open表為空，則問題無解 ，失敗退出； (3)把 Open表的第一個節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到問題的解，成功退出； (5)若節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第 (2)步； (6)擴(kuò)展節(jié)點(diǎn) n，生成其子節(jié)點(diǎn) ni(i=1, 2, …) ，計算每一個子節(jié)點(diǎn)的估價值 f(ni)(i=1, 2, …) ，并為每一個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后將這些子節(jié)點(diǎn)放入 Open表中； (7)根據(jù)各節(jié)點(diǎn)的估價函數(shù)值， 對 Open表中的全部節(jié)點(diǎn)按從小到大的順序重新進(jìn)行排序； (8)轉(zhuǎn)第 (2)步。 例：重排九宮問題 例：重排九宮問題。在 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ù)。 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 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 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1（ 3） 3(4) 4(5) 5(5) 7(6) A算法（例） 2（ 4） 解的路徑： 1－ 3－ 8－ 10－ 11 6(5) 8(4) 9(6) 10(4) 1 2 3 7 8 4 6 5 11(4) 12(6) ? Open表的變化 (A算法） 初始 (1(3)) 1 (2(4),3(4),4(5),5(5)) 2 (3(4),4(5),5(5) ,6(5),7(6)) 3 (8(4), 4(5),5(5) ,6(5), 7(6) ,9(6) ) 4 (10(4),4(5),5(5) ,6(5), 7(6) ,9(6) ) 5 (11(4),4(5),5(5) ,6(5), 7(6) ,9(6) ,12(6)) 6 11(4)為目標(biāo)節(jié)點(diǎn)，結(jié)束 算法討論 ? 全局擇優(yōu)搜索 A算法評價： ? 如何找到最優(yōu)解 . 目標(biāo) ?尋找最佳全局搜索算法 A* –A*算法總能找到最優(yōu)解 – 使擴(kuò)展結(jié)點(diǎn)數(shù)盡量少 ? 方法： 對啟發(fā)式函數(shù)進(jìn)行限制 目標(biāo) 1：算法的可采納性 ? 在問題有解的情況下，若一個搜索過程總能找到最優(yōu)解，則稱該算法具有可采納性。 ? 可采納性的衡量： f*(n)=g*(n)+h*(n) ? 例 重排九宮問題 f(x)=d(x)+h(x) ? h1(x)=0 ? h2(x):錯位棋牌的個數(shù) ? h3(x):每個將