搜索是人工智能中的一個基本問題(文件)

　

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