【正文】 該子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。 (5) 在搜索過程的第 (4)步，一旦某個(gè)被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則搜索過程成功結(jié)束。 Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。 在 3 3的方格棋盤上 ， 分別放置了表有數(shù)字 8的八張牌 ， 初始狀態(tài) S0， 目標(biāo)狀態(tài) Sg， 如下圖所示 。若是，則得到問題的解，成功退出； (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)步。 代價(jià)樹搜索的目的是為了找到最佳解 ， 即找到一條代價(jià)最小的解路徑 。然后轉(zhuǎn)第 (2)步。 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à)樹如右圖所示。 36 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 第 4章 搜索策略 37 狀態(tài)空間的啟發(fā)式搜索 啟發(fā)性信息和估價(jià)函數(shù) A算法 A*算法 A*算法應(yīng)用舉例 38 啟發(fā)性信息的概念 啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的 ， 并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息 。 估價(jià)函數(shù) f(n)被定義為從初始節(jié)點(diǎn) S0出發(fā) ， 約束經(jīng)過節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn) Sg的所有路徑中最小路徑代價(jià)的估計(jì)值 。 請(qǐng)計(jì)算初始狀態(tài) S0的估價(jià)函數(shù)值 f(S0) 40 解： 取 g(n)=d(n)， h(n)=W(n)。 由于估價(jià)函數(shù)中帶有問題自身的啟發(fā)性信息，因此， A算法也被稱為啟發(fā)式搜索算法。 A算法 42 全局擇優(yōu)搜索 A算法描述： (1)把初始節(jié)點(diǎn) S0放入 Open表中， f(S0)=g(S0)+h(S0)； (2)如果 Open表為空，則問題無解 ，失敗退出； (3)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。 請(qǐng)用全局擇優(yōu)搜索解決該問題 。且 f*(n)=g*(n)+h*(n) A*算法 對(duì) A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的 g(n)和h(n)分別提出如下限制： 第一， g(n)是對(duì)最小代價(jià) g*(n)的估計(jì)，且 g(n)0； 第二， h(n)是最小代價(jià) h*(n)的下界，即對(duì)任意節(jié)點(diǎn) n均有h(n)≤h*(n)。 定理 對(duì)有限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則算法A*一定成功結(jié)束。 然后證明算法一定會(huì)成功結(jié)束。 證明： 設(shè) d*(n)是 A*生成的從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的最短路經(jīng)長(zhǎng)度，由于搜索圖中每條邊的代價(jià)都是一個(gè)正數(shù)，令這些正數(shù)中的最小的一個(gè)數(shù)是 e，則有 g*(n)≥d*(n) e 因?yàn)?g*(n)是最佳路徑的代價(jià)，故有 g(n)≥g*(n)≥d*(n) e 又因?yàn)?h(n)≥0，故有 f(n)=g(n)+h(n)≥g(n)≥d*(n) e 如果 A*算法不終止的話，從 Open表中選出的節(jié)點(diǎn)必將具有任意大的 d*(n)值，因此，也將具有任意大的 f值。設(shè)這些節(jié)點(diǎn)中排在最前面的節(jié)點(diǎn)為 n39。) 由于 n39。)=g*(n39。)，故有 f(n39。) 因?yàn)樵谧罴崖窂缴系乃泄?jié)點(diǎn)的 f*值都應(yīng)相等，因此有 f(n39。 (證明略 ) 下面給出 A*算法的可納性 A*算法 1. A*算法的可納性 (4/6) 50 A*算法 1. A*算法的可納性 (5/6) 定理 A*算法是可采納的，即若存在從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg的路徑，則 A*算法必能結(jié)束在最佳路徑上。（反證法） 假設(shè) A*算法未能終止在最佳路徑上，而是終止在 某個(gè)目標(biāo)節(jié)點(diǎn) t處，則有 f(t)=g(t)f*(S0) 但由引理 ，在 A*算法結(jié)束前，必有最佳路徑上的一個(gè)節(jié)點(diǎn) n39。 51 推論 在 A*算法中，對(duì)任何被擴(kuò)展的節(jié)點(diǎn) n，都有f(n)≤f*(S0)。若 n=n39。 h(n)的值越大，說明它攜帶的啟發(fā)性信息越多， A*算法搜索時(shí)擴(kuò)展的節(jié)點(diǎn)就越少，搜索效率就越高。 (2) 假設(shè)對(duì) A2 *中 d(n)=k的任意節(jié)點(diǎn) n結(jié)論成立，即 A1 *也擴(kuò)展了這些節(jié)點(diǎn)。因此， n必定在A1 *的 Open表中。 對(duì)已在 Open表中的子節(jié)點(diǎn)，需要決定是否調(diào)整指向其父節(jié)點(diǎn)的指針； 對(duì)已在 Closed表中的子節(jié)點(diǎn)，除需要決定是否調(diào)整其指向父節(jié)點(diǎn)的指針外，還需要決定是否調(diào)整其子節(jié)點(diǎn)的后繼節(jié)點(diǎn)的父指針。 A*算法 3. h(n)的單調(diào)限制 (1/3) 55 定理 如果 h滿足單調(diào)條件，則當(dāng) A*算法擴(kuò)展節(jié)點(diǎn) n時(shí)，該節(jié)點(diǎn)就已經(jīng)找到了通往它的最佳路徑，即 g(n)=g*(n)。如果 h(n)不滿足單調(diào)性限制，則它們不一定成立。 解：用 m表示左岸的修道士人數(shù) ， c表示左岸的野人數(shù) ， b表示左岸的船數(shù) ， 用三元組 (m, c, b)表示問題的狀態(tài) 。 MC問題的搜索過程如下圖所示。 與 /或樹的一般搜索 62 與 /或樹的廣度優(yōu)先搜索與狀態(tài)空間的廣度優(yōu)先搜索的主要差別是，需要在搜索過程中需要多次調(diào)用可解標(biāo)識(shí)過程或不可解標(biāo)識(shí)過程。 ③ 轉(zhuǎn)第 (2)步。 64 例 設(shè)有下圖所示的與 /或樹，節(jié)點(diǎn)按標(biāo)注順序進(jìn)行擴(kuò)展，其中表有 t t t3的節(jié)點(diǎn)是終止節(jié)點(diǎn)， A、 B、 C為不可解的端節(jié)點(diǎn)。由于 t1為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，不能確定 3號(hào)節(jié)點(diǎn)是否可解。 (4) 擴(kuò)展節(jié)點(diǎn) A，由于 A是端節(jié)點(diǎn)，因此不可擴(kuò)展。 65 與 /或樹的深度優(yōu)先搜索和與 /或樹的廣度優(yōu)先搜索過程基本相同，其主要區(qū)別在于 Open表中節(jié)點(diǎn)的排列順序不同。 如果初始解節(jié)點(diǎn) S0能夠被標(biāo)記為可解節(jié)點(diǎn) ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點(diǎn) ， 則從 Open表中刪去具有可解先輩的節(jié)點(diǎn) 。 ③ 轉(zhuǎn)第 (2)步。由于 t1為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，不能確定 3號(hào)節(jié)點(diǎn)是否可解。由于 t2為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 2號(hào)節(jié)點(diǎn)為可解，再往上又可標(biāo)記 1號(hào)節(jié)點(diǎn)為可解。 算法的每一步都試圖找到一個(gè)最有希望成為最優(yōu)解樹的子樹。 (3)若 n為與節(jié)點(diǎn)，且子節(jié)點(diǎn)為 n1, n2, … ,n k，則 n的代價(jià)可用和代價(jià)法或最大代價(jià)法。 在此與或樹中 ， t t t t4為終止節(jié)點(diǎn)； E、 F是端節(jié)點(diǎn)；邊上的數(shù)字是該邊的代價(jià) 。 定義 希望解樹 (1) 初始節(jié)點(diǎn) S0在希望樹 T (2) 如果 n是具有子節(jié)點(diǎn) n1, n2, … , n k的或節(jié)點(diǎn)，則 n的某個(gè)子節(jié)點(diǎn) ni在希望樹 T中的充分必要條件是 (3) 如果 n是與節(jié)點(diǎn)，則 n的全部子節(jié)點(diǎn)都在希望樹 T中。 解：先計(jì)算左邊的解樹 按和代價(jià)： h(S0)=2+4+6+2=14 按最大代價(jià)： h(S0)=(2+6)+2=10 再計(jì)算右邊的解樹 按和代價(jià)： h(S0)=1+5+3+2=11 按最大代價(jià)： h(S0)=(1+5)+2=8 S0 2 A B t1 C t2 D t3 E t4 F 與 /或樹的代價(jià) 2 4 6 2 3 1 5 72 希望樹是 指搜索過程中最有可能成為最優(yōu)解樹的那棵樹。 (5)根節(jié)點(diǎn)的代價(jià)即為解樹的代價(jià)。 它涉及到解樹的代價(jià)與希望樹。由于 t3為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 3號(hào)節(jié)點(diǎn)為可解節(jié)點(diǎn)，但不能標(biāo)記 1號(hào)為可解。 (4) 擴(kuò)展 2號(hào)節(jié)點(diǎn)，生成 A節(jié)點(diǎn)和 4號(hào)節(jié)點(diǎn)。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 搜索過程為： (1) 先擴(kuò)展 1號(hào)節(jié)點(diǎn)，生成 2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn)。 (5)如果節(jié)點(diǎn) n不可擴(kuò)展，則作下列工作： ① 標(biāo)記節(jié)點(diǎn) n為不可解節(jié)點(diǎn)； ② 應(yīng)用不可解標(biāo)記過程對(duì)節(jié)點(diǎn) n的先輩中不可解解的節(jié)點(diǎn)進(jìn)行標(biāo)記 。 與 /或樹的深度優(yōu)先搜索也可以帶有深度限制 dm，其搜索算法如下： (1)把初始節(jié)點(diǎn) S0放入 Open表中； (2)把 Open表第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (3)如果節(jié)點(diǎn) n的深度等于 dm，則轉(zhuǎn)第 (5)步的第 ① 點(diǎn)； (4)如果節(jié)點(diǎn) n可擴(kuò)展，則做下列工作： ① 擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； 與 /或樹的廣度優(yōu)先和深度優(yōu)先搜索 2. 深度優(yōu)先搜索 66 ② 考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn) 。 (5) 擴(kuò)展 4號(hào)節(jié)點(diǎn)，生成 t2節(jié)點(diǎn)和 B節(jié)點(diǎn)。由于 t3為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 1號(hào)節(jié)點(diǎn)為可解節(jié)點(diǎn)。 (2) 擴(kuò)展 2號(hào)節(jié)點(diǎn)，生成 A節(jié)點(diǎn)和4號(hào)節(jié)點(diǎn)。 如果初始解節(jié)點(diǎn) S0也被標(biāo)記為不可解節(jié)點(diǎn) ， 則搜索失敗 ， 表明原始問題無解 ， 退出搜索過程；如果不能確定 S0為不可解節(jié)點(diǎn) ， 則從 Open表中刪去具有不可解先輩的節(jié)點(diǎn) 。 若有 ， 則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn) ， 并用可解標(biāo)記過程對(duì)其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解解節(jié)點(diǎn)進(jìn)行標(biāo)記 。其一般搜索過程如下： (1) 把原始問題作為初始節(jié)點(diǎn) S0，并把它作為當(dāng)前節(jié)點(diǎn)； (2) 應(yīng)用分解或等價(jià)變換操作對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展； (3) 為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； (4) 選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第 (2)步和第 (3)步，在此期間需要多次調(diào)用可解標(biāo)記過程或不可解標(biāo)記過程，直到初始節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。 設(shè) g(n)=d(n)，h(n)=m+c2b， 則有 f(n)=g(n)+h(n)=d(n)+m+c2b 其中， d(n)為節(jié)點(diǎn)的深度。 A*算法 3. h(n)的單調(diào)限制 (3/3) 57 例 八數(shù)碼難題。其中， ni是這個(gè)序列中最后一個(gè)位于Closed表中的節(jié)點(diǎn)，則上述節(jié)點(diǎn)序列中的 ni+1節(jié)點(diǎn)必定在 Open表中，則有 g*(ni)+h(ni)≤g*(ni) +c(ni, ni+1) +h(ni+1) 由于節(jié)點(diǎn) ni和 ni+1都在最佳路徑上，故有 g*( ni+1)=g*(ni)+c(ni, ni+1) 所以 g*(ni)+h(ni)≤g*( ni+1) +h(ni+1) 一直推導(dǎo)下去可得 g*( ni+1)+h(ni+1)≤g*( nk) +h(nk) 由于節(jié)點(diǎn) ni+1在最佳路徑上，故有 f( ni+1)≤g*( n) +h(n) 因?yàn)檫@時(shí) A*擴(kuò)展節(jié)點(diǎn) n而不擴(kuò)展節(jié)點(diǎn) ni+1，則有 f(n)=g(n)+h(n)≤f( ni+1)≤g*(n)+h(n) 即 g(n)≤g*(n) 但是 g*(n)是最小代價(jià)值，應(yīng)當(dāng)有 g(n)≥g*(n) 所以有 g(n)=g*(n) A*算法 3. h(n)的單調(diào)限制 (2/3) 56 定理 如果 h(n)滿足單調(diào)限制，則 A*算法擴(kuò)展的節(jié)點(diǎn)序列的 f 值是非遞減的，即 f(ni)≤f(ni+1)。 定義 如果啟發(fā)函數(shù)滿足以下兩個(gè)條件 : (1) h(Sg)=0。但由于 d=k時(shí)， A2