【正文】 ≤h*(n)。 在該圖中 ， 每個(gè)節(jié)點(diǎn)旁邊的數(shù)字是該節(jié)點(diǎn)的估價(jià)函數(shù)值 。 請(qǐng)用全局擇優(yōu)搜索解決該問(wèn)題 。 A算法 43 例 八數(shù)碼難題 。 A算法 42 全局擇優(yōu)搜索 A算法描述： (1)把初始節(jié)點(diǎn) S0放入 Open表中， f(S0)=g(S0)+h(S0)； (2)如果 Open表為空，則問(wèn)題無(wú)解 ，失敗退出； (3)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。 全局擇優(yōu)： 從 Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。 由于估價(jià)函數(shù)中帶有問(wèn)題自身的啟發(fā)性信息，因此， A算法也被稱為啟發(fā)式搜索算法。 一般來(lái)說(shuō) ， 某節(jié)點(diǎn)中的 “ 不在位 ” 的數(shù)碼個(gè)數(shù)越多 ， 說(shuō)明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn) 。 請(qǐng)計(jì)算初始狀態(tài) S0的估價(jià)函數(shù)值 f(S0) 40 解： 取 g(n)=d(n)， h(n)=W(n)。 啟發(fā)性信息和估價(jià)函數(shù) 2. 估價(jià)函數(shù) 例 八數(shù)碼難題。 估價(jià)函數(shù) f(n)被定義為從初始節(jié)點(diǎn) S0出發(fā) ， 約束經(jīng)過(guò)節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn) Sg的所有路徑中最小路徑代價(jià)的估計(jì)值 。 啟發(fā)性信息的作用 啟發(fā)信息的啟發(fā)能力越強(qiáng) ， 擴(kuò)展的無(wú)用結(jié)點(diǎn)越少 。 36 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 第 4章 搜索策略 37 狀態(tài)空間的啟發(fā)式搜索 啟發(fā)性信息和估價(jià)函數(shù) A算法 A*算法 A*算法應(yīng)用舉例 38 啟發(fā)性信息的概念 啟發(fā)性信息是指那種與具體問(wèn)題求解過(guò)程有關(guān)的 ， 并可指導(dǎo)搜索過(guò)程朝著最有希望方向前進(jìn)的控制信息 。若是，則找到了問(wè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)按邊代價(jià)由小到大放入 Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。 A B C D E 4 3 4 5 2 3 2 4 5 A C1 B1 D1 D2 E1 E2 B2 C2 E3 3 4 3 4 2 3 城市交通圖 城市交通圖的代價(jià)樹 解： 代價(jià)樹如右圖所示。設(shè)有 5個(gè)城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用，即代價(jià)。然后轉(zhuǎn)第 (2)步。若是，則找到了問(wè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)放入 Open表中，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。 代價(jià)樹搜索的目的是為了找到最佳解 ， 即找到一條代價(jià)最小的解路徑 。 32 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 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 6 7 5 4 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4 2 8 1 6 3 7 5 4 S0 1 2 3 4 5 6 八數(shù)碼難題的深度優(yōu)先搜索如右圖 一種改進(jìn)的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為 dm 例 八數(shù)碼難題 33 在代價(jià)樹中 ， 可以用 g(n)表示從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的代價(jià) ， 用 c(n1, n2)表示從父節(jié)點(diǎn) n1到其子節(jié)點(diǎn) n2的代價(jià) 。若是，則得到問(wèn)題的解，成功退出； (5) 若節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第 (2)步； (6) 擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置 指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第 (2)步。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑 。 在 3 3的方格棋盤上 ， 分別放置了表有數(shù)字 8的八張牌 ， 初始狀態(tài) S0， 目標(biāo)狀態(tài) Sg， 如下圖所示 。若是，則得到問(wèn)題的解，成功退出； (5)若節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第 (2)步； (6)擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第 (2)步。 Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。 (6) 如果搜索過(guò)程終止在第 (2)步，即沒有達(dá)到目標(biāo)，且 Open表中已無(wú)可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)束。 (5) 在搜索過(guò)程的第 (4)步，一旦某個(gè)被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則搜索過(guò)程成功結(jié)束。 (4) 在搜索圖中，除初始節(jié)點(diǎn)外，任意一個(gè)節(jié)點(diǎn)都含有且只含有一個(gè)指向其父節(jié)點(diǎn)的指針。 如果發(fā)生第③種情況，除了需要確定該子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。 27 (3) 在第 (6)步針對(duì) M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時(shí)，如果發(fā)生當(dāng)?shù)冖诜N情況，那么，這個(gè) M中的節(jié)點(diǎn)究竟應(yīng)該作為哪一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？一般是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價(jià)來(lái)決定的，哪一條路經(jīng)付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。 以上三種情況是對(duì)一般圖搜索算法而言的。例如，廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點(diǎn)排在前面。 26 算法的幾點(diǎn)說(shuō)明： (1) 上述過(guò)程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過(guò)程的一個(gè)特例。（原生成也擴(kuò)展過(guò)的） (7) 按某種策略對(duì) Open表中的節(jié)點(diǎn)進(jìn)行排序。（新生成的） ② 對(duì)那些原來(lái)已在 G中出現(xiàn)過(guò)，但還沒有被擴(kuò)展的 M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針。若是則得到了問(wèn)題的解，成功退出； (5) 擴(kuò)展節(jié)點(diǎn) n，生成一組子節(jié)點(diǎn)。 一般圖搜索過(guò)程 算法的數(shù)據(jù)結(jié)構(gòu)和符號(hào)約定 Open表：用于存放剛生成的節(jié)點(diǎn) Closed表：用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展的節(jié)點(diǎn) S0：用表示問(wèn)題的初始狀態(tài) G：表示搜索過(guò)程所得到的搜索圖 M：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集。重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供操作的節(jié)點(diǎn)為止。如果把這些本原問(wèn)題從左至右排列起來(lái)，即得到了原始問(wèn)題的解： (1, 1, 1)→(1, 3, 3) (1, 3, 3)→(1, 2, 3) (1, 2, 3)→(1, 2, 2) (1, 2, 2)→(3, 2, 2) (3, 2, 2)→(3, 2, 1) (3, 2, 1)→(3, 3, 1) (3, 3, 1)→(3, 3, 3) 22 ?搜索的基本概念 狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 第 4章 搜索策略 23 狀態(tài)空間的盲目搜索 一般圖搜索過(guò)程 廣度優(yōu)先和深度優(yōu)先搜索 代價(jià)樹搜索 24 狀態(tài)空間搜索的基本思想 先把問(wèn)題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問(wèn)題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。即 (3, 2, 2)→( (3, 3, 3) 其中，子問(wèn)題 (1)和 (3)都是一個(gè)二階梵塔問(wèn)題，它們都還可以再繼續(xù)進(jìn)行分解；子問(wèn)題 (2)是本原問(wèn)題，它已不需要再分解。即 (1, 1, 1)→(1, 2, 2) (2) 把金片 C移到 3號(hào)鋼針上的單金片移動(dòng)問(wèn)題。設(shè)用三元組 (i, j, k) 表示問(wèn)題在任一時(shí)刻的狀態(tài)，用“ → ”表示狀態(tài)的轉(zhuǎn)換。 解： 這個(gè)問(wèn)題也可用狀態(tài)空間法來(lái)解，不過(guò)本例主要用它來(lái)說(shuō)明如何用歸約法來(lái)解決問(wèn)題。 20 例 三階梵塔問(wèn)題。 問(wèn)題歸約求解過(guò)程就實(shí)際上就是生成解樹，即證明原始節(jié)點(diǎn)是可解節(jié)點(diǎn)的過(guò)程。在該圖中，節(jié)點(diǎn) P為原始問(wèn)題節(jié)點(diǎn)，用 t標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)。在解樹中一定包含初始節(jié)點(diǎn)。 ③ 對(duì)“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個(gè)為不可解節(jié)點(diǎn)，則該與節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 同樣，可用類似的方法定義 不可解節(jié)點(diǎn)： ① 不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 ② 對(duì)“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)?？梢?，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不一定是終止節(jié)點(diǎn)。 即變換所得到的子問(wèn)題的“或”與原問(wèn)題 P等價(jià)。 即分解所得到的子問(wèn)題的“與”與原問(wèn)題 P等價(jià)。不難看出，由初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài)的操作序列為： {Goto(b), Pushbox(c), Climbbox, Grasp} 15 猴子摘香蕉問(wèn)題的解 (a,b,0,0) (b,b,0,0) (c,c,0,0) (b ,b,1,0) (c,c,1,0) (a,a,0,0) (c,c,1,1) 初始狀態(tài) Goto(b) Goto(b) Pushbox(c) Grasp 目標(biāo)狀態(tài) 猴子摘香蕉問(wèn)題的狀態(tài)空間圖 解序列為： {Goto(b), Pushbox(c), Climbbox, Grasp} Pushbox(c) Climbbox Climbbox Pushbox(c) Pushbox(a) Pushbox(a) 16 基本思想 當(dāng)一問(wèn)題較復(fù)雜時(shí)，可通過(guò)分解或變換，將其轉(zhuǎn)化為一系列較簡(jiǎn)單的子問(wèn)題，然后通過(guò)對(duì)這些子問(wèn)題的求解來(lái)實(shí)現(xiàn)對(duì)原問(wèn)題的求解。其中： w表示猴子的水平位置； x表示箱子的水平位置； y表示猴子是否在箱子上，當(dāng)猴子在箱子上時(shí)， y取1，否則 y取 0； z表示猴子是否拿到香蕉，當(dāng)拿到香蕉時(shí) z取 1，否則 z取 0。 在討論謂詞邏輯知識(shí)表示時(shí)，我們?cè)岬竭^(guò)這一問(wèn)題，現(xiàn)在用狀態(tài)空間法來(lái)解決這一問(wèn)題。 12 操作的表示： 用符號(hào) Pij表示從左岸到右岸的運(yùn)人操作 用符號(hào) Qij表示從右岸到左岸的操作 其中： i表示 船上的修道士人數(shù) j表示 船上的野人數(shù) 操作集 本問(wèn)題有 10種操作可供選擇： F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20} 下面以 P01和 Q01為例來(lái)說(shuō)明這些操作的條件和動(dòng)作。 每個(gè)操作都應(yīng)當(dāng)滿足如下條件： 一是 船至少有一個(gè)人（ m或 c）操作，離開岸邊的 m和 c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的 m和 c的增加數(shù)目； 二是 每次操作船上人數(shù)不得超過(guò) 2個(gè)； 三是 操作應(yīng)保證不產(chǎn)生非法狀態(tài)。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (6/11) 11 這 32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)， 有意義的狀態(tài)只有 16種： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1,