【正文】 *擴展的節(jié)點 A1 *也一定擴展，故有 g1(n)≤g2(n) 因此有 h1(n)≥f*(S0)g2(n) 另一方面，由于 A2 *擴展了 n，因此有 f2(n)≤f*(0) 即 g2(n)+h2(n)≤f*(S0)，亦即 h2(n)≤f*(S0)g2(n)，所以有 h1(n)≥h2(n) 這與我們最初假設的 h1(n)h2(n)矛盾，因此反證法的假設不成立。（用反證法） 假設 A2搜索樹上有一個滿足 d(n)=k+1的節(jié)點 n， A2 *擴展了該節(jié)點，但 A1 *沒有擴展它。 定理 設有兩個 A*算法 A1*和 A2*，它們有 A1*: f1(n)=g1(n)+h1(n) A2*: f2(n)=g2(n)+h2(n) 如果 A2*比 A1*有更多的啟發(fā)性信息，即對所有非目標節(jié)點均有 h2(n)h1(n) 則在搜索過程中，被 A2*擴展的節(jié)點也必然被 A1*擴展，即 A1*擴展的節(jié)點不會比 A2*擴展的節(jié)點少，亦即 A2*擴展的節(jié)點集是 A1*擴展的節(jié)點集的子集。) 所以有 f(n)≤f*(S0) A*算法 1. A*算法的可納性 (6/6) 52 A*算法的搜索效率很大程度上取決于估價函數(shù) h(n)。由引理 ，在 Open表中有滿足 f(n39。來擴展，而不可能選擇 Sg，從而也不會去測試目標節(jié)點 Sg，這就與假設 A*算法終止在目標節(jié)點 t相矛盾。 由定理 ，無論是對有限圖還是無限圖， A*算法都能夠找到某個目標節(jié)點而結束。 證明： （反證法）假設 A*不結束，由引理 Open表中的節(jié)點有任意大的 f值，這與引理 ，因此， A*算法只能成功結束。)+h*(n39。) 又由于 A*算法滿足 h(n39。)=g*(n39。)=g(n39。 證明： 設從初始節(jié)點 S0到目標節(jié)點 t的一條最佳路徑序列為 S0= n0, n1, … , n k=Sg 算法開始時，節(jié)點 S0在 Open表中，當節(jié)點 S0離開 Open表進入 Closed表時，節(jié)點 n1進入 Open表。因此，算法一定會成功結束。 由于搜索圖為有限圖，如果算法能找到解，則成功結束；如果算法找不到解，則必然會由于 Open表變空而結束。 46 A*算法 1. A*算法的可納性 (1/6) 可納性的含義： 對任一狀態(tài)空間圖，當從初始節(jié)點到目標節(jié)點有路經(jīng)存在時，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點到目標節(jié)點的最佳路徑，并在此路徑上結束，則稱該搜索算法是可采納的。 在該圖中 ， 每個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值 。 A算法 43 例 八數(shù)碼難題 。 全局擇優(yōu)： 從 Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的一個進行擴展。 一般來說 ， 某節(jié)點中的 “ 不在位 ” 的數(shù)碼個數(shù)越多 ， 說明它離目標節(jié)點越遠 。 啟發(fā)性信息和估價函數(shù) 2. 估價函數(shù) 例 八數(shù)碼難題。 啟發(fā)性信息的作用 啟發(fā)信息的啟發(fā)能力越強 ， 擴展的無用結點越少 。若是，則找到了問題的解，成功退出； (5) 若節(jié)點 n不可擴展，則轉第 (2)步； (6) 擴展節(jié)點 n，生成其子節(jié)點 ni(i=1, 2, …) ，將這些子節(jié)點按邊代價由小到大放入 Open表的首部，并為每一個子節(jié)點設置指向父節(jié)點的指針。設有 5個城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。若是，則找到了問題的解，成功退出； (5) 若節(jié)點 n不可擴展，則轉第 (2)步； (6) 擴展節(jié)點 n，生成其子節(jié)點 ni(i=1, 2, …) ，將這些子節(jié)點放入 Open表中，并為每一個子節(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)先搜索如右圖 一種改進的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為 dm 例 八數(shù)碼難題 33 在代價樹中 ， 可以用 g(n)表示從初始節(jié)點 S0到節(jié)點 n的代價 ， 用 c(n1, n2)表示從父節(jié)點 n1到其子節(jié)點 n2的代價 。要求應用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標狀態(tài)的解路徑 。若是，則得到問題的解，成功退出； (5)若節(jié)點 n不可擴展，則轉第 (2)步； (6)擴展節(jié)點 n，將其子節(jié)點放入 Open表的尾部，并為每一個子節(jié)點設置指向父節(jié)點的指針，然后轉第 (2)步。 (6) 如果搜索過程終止在第 (2)步，即沒有達到目標，且 Open表中已無可供擴展的節(jié)點，則失敗結束。 (4) 在搜索圖中，除初始節(jié)點外，任意一個節(jié)點都含有且只含有一個指向其父節(jié)點的指針。 27 (3) 在第 (6)步針對 M中子節(jié)點的不同情況進行處理時，如果發(fā)生當?shù)冖诜N情況，那么，這個 M中的節(jié)點究竟應該作為哪一個節(jié)點的后繼節(jié)點呢？一般是由原始節(jié)點到該節(jié)點路徑上所付出的代價來決定的，哪一條路經(jīng)付出的代價小，相應的節(jié)點就作為它的父節(jié)點。例如，廣度優(yōu)先搜索把先生成的子節(jié)點排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點排在前面。（原生成也擴展過的） (7) 按某種策略對 Open表中的節(jié)點進行排序。若是則得到了問題的解，成功退出； (5) 擴展節(jié)點 n，生成一組子節(jié)點。重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。即 (3, 2, 2)→( (3, 3, 3) 其中，子問題 (1)和 (3)都是一個二階梵塔問題，它們都還可以再繼續(xù)進行分解；子問題 (2)是本原問題，它已不需要再分解。設用三元組 (i, j, k) 表示問題在任一時刻的狀態(tài)，用“ → ”表示狀態(tài)的轉換。 20 例 三階梵塔問題。在該圖中，節(jié)點 P為原始問題節(jié)點，用 t標出的節(jié)點是終止節(jié)點。 ③ 對“與”節(jié)點，只要其子節(jié)點中有一個為不可解節(jié)點，則該與節(jié)點是不可解節(jié)點。 ② 對“或”節(jié)點，當其子節(jié)點中至少有一個為可解節(jié)點時，則該或節(jié)點就是可解節(jié)點。 即變換所得到的子問題的“或”與原問題 P等價。不難看出，由初始狀態(tài)變?yōu)槟繕藸顟B(tài)的操作序列為： {Goto(b), Pushbox(c), Climbbox, Grasp} 15 猴子摘香蕉問題的解 (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 目標狀態(tài) 猴子摘香蕉問題的狀態(tài)空間圖 解序列為： {Goto(b), Pushbox(c), Climbbox, Grasp} Pushbox(c) Climbbox Climbbox Pushbox(c) Pushbox(a) Pushbox(a) 16 基本思想 當一問題較復雜時，可通過分解或變換，將其轉化為一系列較簡單的子問題，然后通過對這些子問題的求解來實現(xiàn)對原問題的求解。 在討論謂詞邏輯知識表示時，我們曾提到過這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。 每個操作都應當滿足如下條件： 一是 船至少有一個人（ m或 c）操作，離開岸邊的 m和 c的減少數(shù)目應該等于到達岸邊的 m和 c的增加數(shù)目； 二是 每次操作船上人數(shù)不得超過 2個； 三是 操作應保證不產(chǎn)生非法狀態(tài)。=1b 在這種表示方式下， m和 c都可取 0、 3中之一， b可取0和 1中之一。從而可用一個三元組來表示狀態(tài) S=(m, c, b) 其中， m表示左岸的修道士人數(shù)， c表示左岸的野人數(shù)， b表示左岸的船數(shù)。 設在河的一岸有三個野人、三個修道士和一條船，修道士想用這條船把所有的人運到河對岸，但受以下條件的約束： 一是修道士和野人都會劃船，但每次船上至多可載兩個人； 二是在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會被野人吃掉。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (3/11) 8 (3,3) (1,3) (1,2) (2,2) 二階梵塔的狀態(tài)空間圖 從初始節(jié)點 (1, 1)到目標節(jié)點 (2, 2)及 (3, 3)的任何一條路徑都是問題的一個解。 要求把這兩個金片全部移到另一根鋼針上 ， 而且規(guī)定每次只能移動一個金片 ， 任何時刻都不能使大的位于小的上面 。 4 狀態(tài)空間法求解問題的基本過程： 首先為問題選擇適當?shù)摹盃顟B(tài)”及“操作”的形式化描述方法； 然后從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達到目標狀態(tài)為止； 此時，由初始狀態(tài)到目標狀態(tài)所使用的算符序列就是該問題的一個解。 狀態(tài)空間 (State space) 用來描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關系。 按問題的表示方式： 狀態(tài)空間搜索：用狀態(tài)空間法來求解問題所進行的搜索 與或樹搜索：用問題歸約法來求解問題時所進行的搜索 3 狀態(tài)空間法 1. 狀態(tài)空間表示方法 狀態(tài) (State)： 是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結構，它可形式地表示為： Sk={Sk0, Sk1, …} 當對每一個分量都給以確定的值時，就得到了一個具體的狀態(tài)。 搜索是人工智能中的一個基本問題，并與推理密切相關，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。 啟發(fā)式搜索：在搜索中加入了與問題有關的啟發(fā)性信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。操作可理解為狀態(tài)集合上的一個函數(shù)，它描述了狀態(tài)之間的關系。在狀態(tài)空間圖中，節(jié)點表示問題的狀態(tài)，有向邊表示操作。 在初始情況下 ， 1號鋼針上穿有 A、 B兩個金片 ， A比 B小 ， A位于 B的上面 。共有 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種操作，可構成二階梵塔問題的狀態(tài)空間圖，如下圖所示。 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問題 )。在這個問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。=3c 右岸船數(shù) b39。 操作 是指用船把修道士或野人從河的左岸運到右岸，或從河的右岸運到左岸。 操作符號 條件 動作 P01 b=1, m=0或 3, c≥1 b=0, c=c1 Q0