【正文】 請(qǐng)計(jì)算解樹(shù)的代價(jià) 。 最優(yōu)解樹(shù)是指代價(jià)最小的那棵解樹(shù)。 (6) 搜索成功，得到由 4號(hào)節(jié)點(diǎn)即 tt t3節(jié)點(diǎn)構(gòu)成的解樹(shù)。 ③ 轉(zhuǎn)第 (2)步。調(diào)用不可解標(biāo)記過(guò)程 … 。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹(shù)的廣度優(yōu)先搜索 搜索過(guò)程為： (1) 先擴(kuò)展 1號(hào)節(jié)點(diǎn)，生成 2號(hào)節(jié)點(diǎn)和 3號(hào)節(jié)點(diǎn)。 其搜索算法如下： (1)把初始節(jié)點(diǎn) S0放入 Open表中； (2)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (3)如果節(jié)點(diǎn) n可擴(kuò)展，則做下列工作： ① 擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； 與 /或樹(shù)的廣度優(yōu)先和深度優(yōu)先搜索 1. 廣度優(yōu)先搜索 63 ② 考察這些子節(jié)點(diǎn)中有否終止節(jié)點(diǎn) 。 對(duì) A*算法 ， 首先需要確定估價(jià)函數(shù) 。 證明： 設(shè) A*正要擴(kuò)展節(jié)點(diǎn) n，而節(jié)點(diǎn)序列 S0=n0, n1, … ,n k=n 是由初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的最佳路徑。既然節(jié)點(diǎn) n沒(méi)有被 A1 *擴(kuò)展，則有 f1(n)≥f*(S0) 即 g1(n)+h1(n)≥f*(S0)。 下面通過(guò)一個(gè)定理來(lái)描述這一特性。 證明： 令 n是由 A*選作擴(kuò)展的任一節(jié)點(diǎn)，因此 n不會(huì)是目標(biāo)節(jié)點(diǎn)，且搜索沒(méi)有結(jié)束。 證明： 證明過(guò)程分以下兩步進(jìn)行： 先證明 A*算法一定能夠終止在某個(gè)目標(biāo)節(jié)點(diǎn)上。)≤g*(n39。在最佳路徑上，故有 g(n39。 A*算法 1. A*算法的可納性 (2/6) 48 引理 在 A*算法終止前的任何時(shí)刻， Open表中總存在節(jié)點(diǎn) n’ ，它是從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn)的最佳路徑上的一個(gè)節(jié)點(diǎn)，且滿(mǎn)足 f(n’ )≤ f*(S0)。 證明： 首先證明算法必然會(huì)結(jié)束。 解： 該問(wèn)題的全局擇優(yōu)搜索樹(shù)如下圖所示 。 類(lèi)型： 可根據(jù)搜索過(guò)程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。 它的一般形式為： f(n)=g(n)+h(n) 其中， g(n)是從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的實(shí)際代價(jià)； h(n)是從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn) Sg的最優(yōu)路徑的估計(jì)代價(jià)。其中，紅線(xiàn)為最優(yōu)解，其代價(jià)為 8 35 代價(jià)樹(shù)搜索 代價(jià)樹(shù)的深度優(yōu)先搜索算法： (1) 把初始節(jié)點(diǎn) S0放入 Open表中，置 S0的代價(jià) g(S0)=0； (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)。 代價(jià)樹(shù)搜索 1. 代價(jià)樹(shù)的廣度優(yōu)先搜索 代價(jià)樹(shù)的廣度優(yōu)先搜索算法： (1) 把初始節(jié)點(diǎn) S0放入 Open表中，置 S0的代價(jià) g(S0)=0； (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)到目標(biāo)節(jié)點(diǎn)路徑上的所有操作就構(gòu)成了該問(wèn)題的解，而路徑由第 (6)步所形成的指向父節(jié)點(diǎn)的指針來(lái)確定。對(duì)于盲目搜索，由于其狀態(tài)空間是樹(shù)狀結(jié)構(gòu)，因此不會(huì)出現(xiàn)后兩種情況，每個(gè)節(jié)點(diǎn)經(jīng)擴(kuò)展后生成的子節(jié)點(diǎn)都是第一次出現(xiàn)的節(jié)點(diǎn)，不必檢查并修改指向父節(jié)點(diǎn)的指針。（原生成但未擴(kuò)展的） ③ 對(duì)于那些先前已在 G中出現(xiàn)過(guò)，并已經(jīng)擴(kuò)展了的 M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。若出現(xiàn)，則搜索成功，找到了問(wèn)題的解；若沒(méi)出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 為了能夠解決這一問(wèn)題，首先需要定義該問(wèn)題的形式化表示方法。 例如，右圖給出的與或樹(shù)中，用紅 線(xiàn)表示的子樹(shù)是一個(gè)解樹(shù)。 (5) 可解節(jié)點(diǎn)與不可解節(jié)點(diǎn) 在與 /或樹(shù)中，滿(mǎn)足以下三個(gè)條件之一的節(jié)點(diǎn)為 可解節(jié)點(diǎn)： ① 任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (9/11) 14 所有可能的狀態(tài)為 S0: (a, b, 0, 0) 初始狀態(tài) S1: (b, b, 0, 0) S2: (c, c, 0, 0) S3: (c, c, 1, 0) S4: (c, c, 1, 1) 目標(biāo)狀態(tài) 允許的操作為 Goto(u)：猴子走到位置 u，即 (w, x, 0, 0)→(u, x, 0, 0) Pushbox(v): 猴子推著箱子到水平位置 v，即 (x, x, 0, 0)→(v, v, 0, 0) Climbbox: 猴子爬上箱子，即 (x, x, 0, 0)→(x, x, 1, 0) Grasp；猴子拿到香蕉，即 (c, c, 1, 0 )→(c, c, 1, 1) 這個(gè)問(wèn)題的狀態(tài)空間圖如下圖所示。 操作 是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。在這個(gè)問(wèn)題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。共有 12種操作，它們分別是： A(1, 2) A(1, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2) B(1, 2) B(1, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2) 根據(jù)上述 9種可能的狀態(tài)和 12種操作，可構(gòu)成二階梵塔問(wèn)題的狀態(tài)空間圖，如下圖所示。在狀態(tài)空間圖中，節(jié)點(diǎn)表示問(wèn)題的狀態(tài)，有向邊表示操作。 啟發(fā)式搜索：在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。 按問(wèn)題的表示方式： 狀態(tài)空間搜索：用狀態(tài)空間法來(lái)求解問(wèn)題所進(jìn)行的搜索 與或樹(shù)搜索：用問(wèn)題歸約法來(lái)求解問(wèn)題時(shí)所進(jìn)行的搜索 3 狀態(tài)空間法 1. 狀態(tài)空間表示方法 狀態(tài) (State)： 是表示問(wèn)題求解過(guò)程中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)，它可形式地表示為： Sk={Sk0, Sk1, …} 當(dāng)對(duì)每一個(gè)分量都給以確定的值時(shí)，就得到了一個(gè)具體的狀態(tài)。 4 狀態(tài)空間法求解問(wèn)題的基本過(guò)程： 首先為問(wèn)題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法； 然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止； 此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問(wèn)題的一個(gè)解。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (3/11) 8 (3,3) (1,3) (1,2) (2,2) 二階梵塔的狀態(tài)空間圖 從初始節(jié)點(diǎn) (1, 1)到目標(biāo)節(jié)點(diǎn) (2, 2)及 (3, 3)的任何一條路徑都是問(wèn)題的一個(gè)解。從而可用一個(gè)三元組來(lái)表示狀態(tài) S=(m, c, b) 其中， m表示左岸的修道士人數(shù)， c表示左岸的野人數(shù)， b表示左岸的船數(shù)。 每個(gè)操作都應(yīng)當(dāng)滿(mǎn)足如下條件： 一是 船至少有一個(gè)人（ m或 c）操作，離開(kāi)岸邊的 m和 c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的 m和 c的增加數(shù)目； 二是 每次操作船上人數(shù)不得超過(guò) 2個(gè)； 三是 操作應(yīng)保證不產(chǎn)生非法狀態(tài)。不難看出，由初始狀態(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)題的求解。 ② 對(duì)“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)。在該圖中，節(jié)點(diǎn) P為原始問(wèn)題節(jié)點(diǎn)，用 t標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)。設(shè)用三元組 (i, j, k) 表示問(wèn)題在任一時(shí)刻的狀態(tài)，用“ → ”表示狀態(tài)的轉(zhuǎn)換。重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒(méi)有可供操作的節(jié)點(diǎn)為止。（原生成也擴(kuò)展過(guò)的） (7) 按某種策略對(duì) Open表中的節(jié)點(diǎn)進(jì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)。 (6) 如果搜索過(guò)程終止在第 (2)步，即沒(méi)有達(dá)到目標(biāo)，且 Open表中已無(wú)可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)束。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑 。若是，則找到了問(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)的指針。若是，則找到了問(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)的指針。 啟發(fā)性信息和估價(jià)函數(shù) 2. 估價(jià)函數(shù) 例 八數(shù)碼難題。 全局擇優(yōu)： 從 Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。 在該圖中 ， 每個(gè)節(jié)點(diǎn)旁邊的數(shù)字是該節(jié)點(diǎn)的估價(jià)函數(shù)值 。 由于搜索圖為有限圖，如果算法能找到解，則成功結(jié)束；如果算法找不到解，則必然會(huì)由于 Open表變空而結(jié)束。 證明： 設(shè)從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) t的一條最佳路徑序列為 S0= n0, n1, … , n k=Sg 算法開(kāi)始時(shí)，節(jié)點(diǎn) S0在 Open表中，當(dāng)節(jié)點(diǎn) S0離開(kāi) Open表進(jìn)入 Closed表時(shí)，節(jié)點(diǎn) n1進(jìn)入 Open表。)=g*(n39。)+h*(n39。 由定理 ，無(wú)論是對(duì)有限圖還是無(wú)限圖， A*算法都能夠找到某個(gè)目標(biāo)節(jié)點(diǎn)而結(jié)束。由引理 ，在 Open表中有滿(mǎn)足 f(n39。 定理 設(shè)有兩個(gè) A*算法 A1*和 A2*，它們有 A1*: f1(n)=g1(n)+h1(n) A2*: f2(n)=g2(n)+h2(n) 如果 A2*比 A1*有更多的啟發(fā)性信息，即對(duì)所有非目標(biāo)節(jié)點(diǎn)均有 h2(n)h1(n) 則在搜索過(guò)程中，被 A2*擴(kuò)展的節(jié)點(diǎn)也必然被 A1*擴(kuò)展，即 A1*擴(kuò)展的節(jié)點(diǎn)不會(huì)比 A2*擴(kuò)展的節(jié)點(diǎn)少，亦即 A2*擴(kuò)展的節(jié)點(diǎn)集是 A1*擴(kuò)展的節(jié)點(diǎn)集的子集。但由于 d=k時(shí)， A2 *擴(kuò)展的節(jié)點(diǎn) A1 *也一定擴(kuò)展，故有 g1(n)≤g2(n) 因此有 h1(n)≥f*(S0)g2(n) 另一方面，由于 A2 *擴(kuò)展了 n，因此有 f2(n)≤f*(0) 即 g2(n)+h2(n)≤f*(S0)，亦即 h2(n)≤f*(S0)g2