【正文】 若用和代價(jià)法，則其計(jì)算公式為： 若用最大代價(jià)法，則其計(jì)算公式為： (4)若 n是端節(jié)點(diǎn)，但又不是終止節(jié)點(diǎn)，則 n不可擴(kuò)展，其代價(jià)定義為h(n)=∝ 。 67 對(duì)上例， 若按有界深度優(yōu)先，且 設(shè) dm=4，則其節(jié)點(diǎn)擴(kuò)展順序?yàn)椋?， 3， 5， 2， 4。 (6) 擴(kuò)展 5號(hào)節(jié)點(diǎn)，生成 t3節(jié)點(diǎn)和 C節(jié)點(diǎn)。 A*算法應(yīng)用舉例 59 (3,3,1) h=4 f=4 (3,2,0) (3,1,0) (2,2,0) (3,2,1) (2,1,0) (3,0,0) (2,2,1) (3,1,1) (0,2,0) (1,1,0) (0,3,1) (0,1,0) (0,2,1) (0,0,0) h=5 f=6 h=3 f=5 h=3 f=6 h=3 f=6 h=2 f=6 h=2 f=7 h=1 f=7 h=1 f=8 h=0 f=8 傳教士和野人問題的搜索圖 問題狀態(tài)： (m,c,b) 估價(jià)函數(shù)： h(n)=m+c2b h=4 f=5 h=4 f=5 h=2 f=6 h=2 f=7 60 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 61 與 /或樹的搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。 如果能夠保證，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)就已經(jīng)找到了通往這個(gè)節(jié)點(diǎn)的最佳路徑，就沒有必要再去作上述檢查 為滿足這一要求，我們需要對(duì)啟發(fā)函數(shù) h(n)增加單調(diào)性限制。則有 f(n)≤f*(S0)；否則，選擇 n擴(kuò)展，必有 f(n) ≤f(n39。)≤f*(S0) A*算法 1. A*算法的可納性 (3/6) 49 定理 對(duì)無限圖，若從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則 A*算法必然會(huì)結(jié)束。則有 f(n39。 即滿足上述兩條限制的 A算法稱為 A*算法。 它說明是用從 S0到 n的路徑上的單位代價(jià)表示實(shí)際代價(jià) ， 用結(jié)點(diǎn) n中 “ 不在位 ” 的數(shù)碼個(gè)數(shù)作為啟發(fā)信息 。 34 例 城市交通問題。 搜索算法 (1)把初始節(jié)點(diǎn) S0放入 Open表中； (2)如果 Open表為空，則問題無解，失敗退出； (3)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。各種搜索策略的主要區(qū)別在于對(duì) Open表中節(jié)點(diǎn)的排列順序不同。即 (1, 2, 2)→(3, 2, 2) (3) 把金片 A及 B移到 3號(hào)鋼針的雙金片移動(dòng)問題。 ② 對(duì)“或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)都為不可解節(jié)點(diǎn)，則該或節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 操作符號(hào) 條件 動(dòng)作 P01 b=1, m=0或 3, c≥1 b=0, c=c1 Q01 b=0, m=0或 3， c≤2 b=1, c=c+1 13 a b c 例 猴子摘香蕉問題。 A(1,2) B(1,3) A(2,3) (1,1) (3,1) (3,2) (2,1) (2,3) A(1,3) B(1,2) A(3,2) 9 例 修道士 (Missionaries)和野人 (Cannibals)問題 (簡稱MC問題 )。操作可理解為狀態(tài)集合上的一個(gè)函數(shù)，它描述了狀態(tài)之間的關(guān)系。 狀態(tài)空間 (State space) 用來描述一個(gè)問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。 設(shè)在河的一岸有三個(gè)野人、三個(gè)修道士和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束： 一是修道士和野人都會(huì)劃船，但每次船上至多可載兩個(gè)人； 二是在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會(huì)被野人吃掉。 在討論謂詞邏輯知識(shí)表示時(shí)，我們?cè)岬竭^這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。 ③ 對(duì)“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個(gè)為不可解節(jié)點(diǎn)，則該與節(jié)點(diǎn)是不可解節(jié)點(diǎn)。即 (3, 2, 2)→( (3, 3, 3) 其中，子問題 (1)和 (3)都是一個(gè)二階梵塔問題，它們都還可以再繼續(xù)進(jìn)行分解；子問題 (2)是本原問題，它已不需要再分解。例如，廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點(diǎ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)步。設(shè)有 5個(gè)城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用，即代價(jià)。 一般來說 ， 某節(jié)點(diǎn)中的 “ 不在位 ” 的數(shù)碼個(gè)數(shù)越多 ， 說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn) 。 46 A*算法 1. A*算法的可納性 (1/6) 可納性的含義： 對(duì)任一狀態(tài)空間圖，當(dāng)從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路經(jīng)存在時(shí)，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。)=g(n39。 證明： （反證法）假設(shè) A*不結(jié)束，由引理 Open表中的節(jié)點(diǎn)有任意大的 f值，這與引理 ，因此， A*算法只能成功結(jié)束。) 所以有 f(n)≤f*(S0) A*算法 1. A*算法的可納性 (6/6) 52 A*算法的搜索效率很大程度上取決于估價(jià)函數(shù) h(n)。 定義 如果啟發(fā)函數(shù)滿足以下兩個(gè)條件 : (1) h(Sg)=0。其一般搜索過程如下： (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)為止。由于 t3為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 1號(hào)節(jié)點(diǎn)為可解節(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)的代價(jià)即為解樹的代價(jià)。 (3)若 n為與節(jié)點(diǎn)，且子節(jié)點(diǎn)為 n1, n2, … ,n k，則 n的代價(jià)可用和代價(jià)法或最大代價(jià)法。 ③ 轉(zhuǎn)第 (2)步。由于 t1為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，不能確定 3號(hào)節(jié)點(diǎn)是否可解。 MC問題的搜索過程如下圖所示。 對(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)的父指針。若 n=n39。) 因?yàn)樵谧罴崖窂缴系乃泄?jié)點(diǎn)的 f*值都應(yīng)相等，因此有 f(n39。設(shè)這些節(jié)點(diǎn)中排在最前面的節(jié)點(diǎn)為 n39。且 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)。 請(qǐng)計(jì)算初始狀態(tài) S0的估價(jià)函數(shù)值 f(S0) 40 解： 取 g(n)=d(n)， h(n)=W(n)。然后轉(zhuǎn)第 (2)步。 Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。 26 算法的幾點(diǎn)說明： (1) 上述過程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過程的一個(gè)特例。即 (1, 1, 1)→(1, 2, 2) (2) 把金片 C移到 3號(hào)鋼針上的單金片移動(dòng)問題。 同樣，可用類似的方法定義 不可解節(jié)點(diǎn)： ① 不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 12 操作的表示： 用符號(hào) Pij表示從左岸到右岸的運(yùn)人操作 用符號(hào) Qij表示從右岸到左岸的操作 其中： i表示 船上的修道士人數(shù) j表示 船上的野人數(shù) 操作集 本問題有 10種操作可供選擇： F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20} 下面以 P01和 Q01為例來說明這些操作的條件和動(dòng)作。例如，從 (1, 1)開始，通過使用操作 A(1, 3)、 B(1, 2)及 A(3, 2)，可到達(dá) (3, 3)。操作可以是一個(gè)機(jī)械步驟，一個(gè)運(yùn)算，一條規(guī)則或一個(gè)過程。常用一個(gè)三元組表示為： (S, F, G) 其中， S為問題的所有初始狀態(tài)的集合； F為操作的集合； G為目標(biāo)狀態(tài)的集合。 如果野人會(huì)服從任何一次過河安排，請(qǐng)規(guī)劃一個(gè)確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計(jì)劃。 解： 問題的狀態(tài)可用 4元組 （ w, x, y, z） 表示。 19 P t t t 解樹 (6) 解樹 由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)（它對(duì)應(yīng)著原始問題）為可解節(jié)點(diǎn)的子樹為解樹。 三階梵塔問題的分解過程可用如下圖與 /或樹來表示 (1,1,1)→(3,3,3) (1,1,1)→(1,2,2) (1,2,2)→(3,2,2) (3,2,2)→(3,3,3) (1,1,1)→(1,1,3) (1,1,3)→(1,2,3) (1,2,3)→(1,2,2) (3,2,2)→(3,2,1) (3,2,1)→(3,3,1) (3,3,1)→(3,3,3) 在該與 /或樹中，有 7個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著 7個(gè)本原問題。 (2) 在第 (5)步對(duì)節(jié)點(diǎn) n擴(kuò)展后，生成并記入 M的子節(jié)點(diǎn)有以下三種情況： ① 該子節(jié)點(diǎn)來從未被任何節(jié)點(diǎn)生成過，由 n第一次生成； ② 該子節(jié)點(diǎn)原來被其他節(jié)點(diǎn)生成過，但還沒有被擴(kuò)展，這一次又被n再次生成； ③ 該子節(jié)點(diǎn)原來被其他節(jié)點(diǎn)生成過，并且已經(jīng)被擴(kuò)展過，這一次又被 n再次生成。 廣度優(yōu)先和深度優(yōu)先搜索 1. 廣度優(yōu)先搜索 29 例 八數(shù)碼難題 。用代價(jià)樹的廣度優(yōu)先搜索，求從 A市出發(fā)到 E市，費(fèi)用最小的交通路線。 對(duì)初始節(jié)點(diǎn) S0， 由于 d(S0)=0， W(S0)=3， 因此有 f(S0)=0+3=3 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 S0 Sg 41 概念： 在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì) Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為 A算法。 A*算法可納性的證明 以下分三步（定理 、定理 、定理 ，即引理）進(jìn)行證明。)+h(n39。 推論 Open表