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