【文章內(nèi)容簡(jiǎn)介】 8 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 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 1 2 5 6 7 3 1 2 3 8 4 7 6 5 目標(biāo) 8 2 3 4 1 8 7 6 5 4 64 寬度優(yōu)先搜索的性質(zhì) ?當(dāng)問(wèn)題有解時(shí)，一定能找到解 ?當(dāng)問(wèn)題為單位耗散值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解 ?方法與問(wèn)題無(wú)關(guān)，具有通用性 ?效率較低 ?屬于圖搜索方法 65 漸進(jìn)式深度優(yōu)先搜索方法 ?目的 – 解決寬度優(yōu)先方法的空間問(wèn)題和回溯方法不能找到最優(yōu)解的問(wèn)題。 ?思想 首先給回溯法一個(gè)比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。 66 啟發(fā)式圖搜索 ?利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。 ?啟發(fā)信息的強(qiáng)度 – 強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解 – 弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解 67 希望： ?引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。 68 基本思想 ?定義一個(gè)評(píng)價(jià)函數(shù) f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展。 69 1，啟發(fā)式搜索算法 A（ A算法） ?評(píng)價(jià)函數(shù)的格式： f(n) = g(n) + h(n) f(n)：評(píng)價(jià)函數(shù) h(n)：?jiǎn)l(fā)函數(shù) 70 符號(hào)的意義 ? g*(n)：從 s到 n的最短路徑的耗散值 ? h*(n)：從 n到 g的最短路徑的耗散值 ? f*(n)=g*(n)+h*(n)：從 s經(jīng)過(guò) n到 g的最短路徑的耗散值 ? g(n)、 h(n)、 f(n)分別是 g*(n)、 h*(n)、 f*(n)的估計(jì)值 71 A算法 1, OPEN:=(s), f(s):=g(s)+h(s)。 2, LOOP: IF OPEN=( ) THEN EXIT(FAIL)。 3, n:=FIRST(OPEN)。 4, IF GOAL(n) THEN EXIT(SUCCESS)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 6, EXPAND(n) →{m i}, 計(jì)算 f(n, mi):=g(n, mi)+h(mi)。 72 A算法（續(xù)） ADD(mj, OPEN), 標(biāo)記 mj到 n的指針； IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標(biāo)記 mk到 n的指針； IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml), 標(biāo)記 ml到 n的指針 , ADD(ml, OPEN)。 7, OPEN中的節(jié)點(diǎn)按 f值從小到大排序； 8, GO LOOP； 73 …... …... …... …... …... mj mk ml n a b 74 Closed表 Open表 75 一個(gè) A算法的例子 定義評(píng)價(jià)函數(shù)： f(n) = g(n) + h(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值 h(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù) 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 76 h計(jì)算舉例 h(n) =4 2 8 3 1 6 4 7 5 1 2 3 4 5 7 6 8 77 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 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 2 3 7 8 4 6 5 s(4) A(6) B(4) C(6) D(5) E(5) F(6) G(6) H(7) I(5) J(7) K(5) L(5) M(7) 目標(biāo) 1 2 3 4 5 6 78 2，最佳圖搜索算法 A*（ A*算法） ?在 A算法中，如果滿足條件： h(n)≤h*(n) 則 A算法稱為 A*算法。 79 A*條件舉例 ? 8數(shù)碼問(wèn)題 – h1(n) = “不在位”的將牌數(shù) – h2(n) = 將牌“不在位”的距離和 2 8 3 1 6 4 7 5 1 2 3 4 5 7 6 8 將牌 1： 1 將牌 2： 1 將牌 6： 1 將牌 8： 2 80 A*算法的性質(zhì) ? A*算法的假設(shè) 設(shè) ni、 nj是任意兩個(gè)節(jié)點(diǎn)，有： C(ni, nj) ? 其中 ?為大于 0的常數(shù) ?幾個(gè)等式 f*(s) = f*(t) = h*(s) = g*(t) = f*(n) 其中 s是初始節(jié)點(diǎn)， t是目標(biāo)節(jié)點(diǎn)， n是 s到 t的最佳路徑上的節(jié)點(diǎn)。 81 A*算法的性質(zhì)（續(xù) 1） 定理 1： 對(duì)有限圖，如果從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則算法 A一定成功結(jié)束。 82 A*算法的性質(zhì)（續(xù) 2） 引理 ： 對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t的路徑，則 A*不結(jié)束時(shí)，在 OPEN表中即使最小的一個(gè) f值也將增到任意大，或有 f(n)f*(s)。 83 A*算法的性質(zhì)（續(xù) 3） 引理 ： A*結(jié)束前， OPEN表中必存在 f(n)≤f*(s)。 存在一個(gè)節(jié)點(diǎn) n， n在 最佳路徑上。 f(n) = g(n) + h(n) = g*(n)+h(n) ≤g*(n)+h*(n) = f*(n) = f*(s) 84 A*算法的性質(zhì)（續(xù) 3） 定理 2： 對(duì)無(wú)限圖，若從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則 A*一定成功結(jié)束。 引理 ： A*如果不結(jié)束，則 OPEN中所有的 n有f(n) f*(s) 引理 ：在 A*結(jié)束前，必存在節(jié)點(diǎn) n，使得 f(n) ≤ f*(s) 所以，如果 A*不結(jié)束，將導(dǎo)致矛盾。 85 A*算法的性質(zhì)（續(xù) 4） 推論 ： OPEN表上任一具有 f(n)f*(s)的節(jié)點(diǎn) n，最終都將被 A*選作擴(kuò)展的節(jié)點(diǎn)。 由定理 2，知 A*一定結(jié)束，由 A*的結(jié)束條件， OPEN表中 f(t)最小時(shí)才結(jié)束。而 f(t) ≥ f*(t) ＝ f*(s) 所以 f(n)f*(s)的 n，均被擴(kuò)展。得證。 86 A*算法的性質(zhì)（續(xù) 5） 定理 3 (可采納性定理 )： 若存在從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑，則 A*必能找到最佳解結(jié)束。 87 可采納性的證明 ? 由定理 2知 A*一定找到一條路徑結(jié)束 ? 設(shè)找到的路徑 s→ t 不是最佳的（ t為目標(biāo)） 則： f(t) = g(t) f*(s) ? 由引理 OPEN中存在 f(n)≤f*(s)的節(jié)點(diǎn)n，所以 f(n) ≤ f*(s) f(t) ? 因此 A*應(yīng)選擇 n擴(kuò)展，而不是 t。與假設(shè) A*選擇 t結(jié)束矛盾。得證。 ? 注意 ： A*的結(jié)束條件 88 A*算法的性質(zhì)（續(xù) 6） 推論 ： A*選作