【正文】 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Sg 31 算法描述 (1) 把初始節(jié)點 S0放入 Open表中； (2) 如果 Open表為空，則問題無解 ，失敗退出； (3) 把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (4) 考察節(jié)點 n是否為目標節(jié)點。 廣度優(yōu)先和深度優(yōu)先搜索 1. 廣度優(yōu)先搜索 29 例 八數碼難題 。 28 基本思想 從初始節(jié)點 S0開始逐層向下擴展，在第 n層節(jié)點還沒有全部搜索完之前，不進入第 n+1層節(jié)點的搜索。因此，由所有節(jié)點及其指向父節(jié)點的指針所構成的集合是一棵樹，稱為搜索樹。所謂由原始節(jié)點到該節(jié)點路徑上的代價是指這條路經上的所有有向邊的代價之和。 (2) 在第 (5)步對節(jié)點 n擴展后，生成并記入 M的子節(jié)點有以下三種情況： ① 該子節(jié)點來從未被任何節(jié)點生成過，由 n第一次生成； ② 該子節(jié)點原來被其他節(jié)點生成過，但還沒有被擴展，這一次又被n再次生成； ③ 該子節(jié)點原來被其他節(jié)點生成過，并且已經被擴展過，這一次又被 n再次生成。 (8) 轉第 (2)步。把這些子節(jié)點中不是節(jié)點 n先輩的那部分子節(jié)點記入集合 M，并把這些子節(jié)點作為節(jié)點 n的子節(jié)點加入 G中 (6) 針對 M中子節(jié)點的不同情況，分別作如下處理： ① 對那些沒有在 G中出現過的 M成員設置一個指向其父節(jié)點（即節(jié)點n）的指針，并把它放入 Open表。所謂對一個節(jié)點進行“擴展”是指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(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é)點，它們分別對應著 7個本原問題。上述三元組中 i 代表金片 C所在的鋼針號 j 代表金片 B所在的鋼針號 k 代表金片 A所在的鋼針號 1 2 3 1 2 3 問題歸約法 2. 問題的與 /或樹表示 A B C A B C 21 利用問題歸約方法，原問題可分解為以下 三個子問題： (1) 把金片 A及 B移到 2號鋼針上的雙金片移動問題。要求把 1號鋼針上的 3個金片全部移到 3號鋼針上，如下圖所示。根據可解節(jié)點的定義，很容易推出原始問題 P為可解節(jié)點。 19 P t t t 解樹 (6) 解樹 由可解節(jié)點構成，并且由這些可解節(jié)點可以推出初始節(jié)點（它對應著原始問題）為可解節(jié)點的子樹為解樹。 ③ 對“與”節(jié)點，只有當其子節(jié)點全部為可解節(jié)點時，該與節(jié)點才是可解節(jié)點。 問題歸約法 1. 問題的分解與等價變換 17 P P1 P2 P3 與樹 P1 P2 P3 或樹 P P P1 P2 P3 P12 P12 P31 P32 P33 與 /或樹 (1)與樹 分解 (2) 或樹 等價變換 (3) 與 /或樹 問題歸約法 2. 問題的與 /或樹表示 18 (4) 端節(jié)點與終止節(jié)點 在與 /或樹中，沒有子節(jié)點的節(jié)點稱為 端節(jié)點 ；本原問題所對應的節(jié)點稱為 終止節(jié)點 。 分解 如果一個問題 P可以歸約為一組子問題 P1,P2,…,P n，并且只有當所有子問題 Pi都有解時原問題 P才有解，任何一個子問題 Pi無解都會導致原問題 P無解，則稱此種歸約為問題的分解。 解： 問題的狀態(tài)可用 4元組 （ w, x, y, z） 表示。 因此， 操作應由條件部分和動作部分： 條件： 只有當其條件具備時才能使用 動作： 刻劃了應用此操作所產生的結果。因此，共有 4 4 2=32種狀態(tài)。 右岸的狀態(tài)可由下式確定： 右岸修道士數 m39。 如果野人會服從任何一次過河安排，請規(guī)劃一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計劃。其中，最短的路徑長度是 3，它由 3個操作組成。 解： 設用 Sk=(Sk0, Sk1)表示問題的狀態(tài)，其中， Sk0表示金片 A所在的鋼針號， Sk1表示金片 B所在的鋼針號。 狀態(tài)空間法 2. 狀態(tài)空間問題求解 5 例 二階梵塔問題 。常用一個三元組表示為： (S, F, G) 其中， S為問題的所有初始狀態(tài)的集合； F為操作的集合； G為目標狀態(tài)的集合。 操作 (Operator) 也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。 搜索的基本概念 狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 與 /或樹的盲目搜索 與 /或樹的啟發(fā)式搜索 博弈樹的啟發(fā)式搜索 第 4章 搜索策略 1 搜索的基本概念 搜索的含義 狀態(tài)空間法 問題歸約法 2 搜索的含義 適用情況： 不良結構或非結構化問題；難以獲得求解所需的全部信息；更沒有現成的算法可供求解使用。 概念： 依靠經驗，利用已有知識，根據問題的實際情況，不斷尋找可利用知識，從而構造一條代價最小的推理路線，使問題得以解決的過程稱為搜索 搜索的類型 按是否使用啟發(fā)式信息： 盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息并不改變控制策略。操作可以是一個機械步驟，一個運算，一條規(guī)則或一個過程。 狀態(tài)空間也可用一個賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖。 設有三根鋼針 ， 它們的編號分別是1號 、 2號和 3號 。全部可能的問題狀態(tài)共有以下 9種： S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S4=(2, 2) S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3) 狀態(tài)空間法 3. 狀態(tài)空間的例子 (1/11) 6 A B A B A B 1 2 3 1 2 3 1 2 3 二階梵塔問題的初始狀態(tài)和目標狀態(tài) 問題的初始狀態(tài)集合 為 S={S0} 目標狀態(tài)集合 為 G={S4, S5} 初始狀態(tài) S0和目標狀態(tài) S S8如圖所示 S0=(1, 1) S4=(2, 2) S8=(3, 3) 狀態(tài)空間法 3. 狀態(tài)空間的例子 (2/11) 7 操作分別用 A(i, j)和 B(i, j)表示 A(i, j)表示把金片 A從第 i號鋼針移到 j號鋼針上； B(i, j)表示把金片 B從第 i號鋼針一到第 j號鋼針上。例如，從 (1, 1)開始，通過使用操作 A(1, 3)、 B(1, 2)及 A(3, 2)，可到達 (3, 3)。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (5/11) 10 解： 首先選取描述問題狀態(tài)的方法。=3m 右岸野人數 c39。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (6/11) 11 這 32種狀態(tài)并非全有意義，除去不合法狀態(tài)和修道士被野人吃掉的狀態(tài)， 有意義的狀態(tài)只有 16種： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0) 有了這些狀態(tài)，還需要考慮可進行的操作。 12 操作的表示： 用符號 Pij表示從左岸到右岸的運人操作 用符號 Qij表示從右岸到左岸的操作 其中： i表示 船上的修道士人數 j表示 船上的野人數 操作集 本問題有 10種操作可供選擇： F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20} 下面以 P01和 Q01為例來說明這些操作的條件和動作。其中： w表示猴子的水平位置； x表示箱子的水平位置； y表示猴子是否在箱子上，當猴子在箱子上時， y取1，否則 y取 0； z表示猴子是否拿到香蕉，當拿到香蕉時 z取 1，否則 z取 0。 即分解所得到的子問題的“與”與原問題 P等價?？梢?，終止節(jié)點一定是端節(jié)點，但端節(jié)點卻不一定是終止節(jié)點。 同樣，可用類似的方法定義 不可解節(jié)點： ① 不為終止節(jié)點的端節(jié)點是不可解節(jié)點。在解樹中一定包含初始節(jié)點。 問題歸約求解過程就實際上就是生成解樹，即證明原始節(jié)點是可解節(jié)點的過程。 解： 這個問題也可用狀態(tài)空間法來解，不過本例主要用它來說明如何用歸約法來解決問題。即 (1, 1, 1)→(1, 2, 2) (2) 把金片 C移到 3號鋼針上的單金片移動問題。如果把這些本原問題從左至右排列起來，即得到了原始問題的解： (1, 1, 1)→(1, 3, 3) (1, 3, 3)→(1, 2, 3) (1, 2, 3)→(1, 2, 2) (1, 2, 2)→(3, 2, 2) (3, 2, 2)→(3, 2, 1) (3, 2, 1)→(3, 3, 1) (3, 3, 1)→(3, 3, 3) 22 ?搜索的基本概念 狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 第 4章 搜索策略 23 狀態(tài)空間的盲目搜索 一般圖搜索過程 廣度優(yōu)先和深度優(yōu)先搜索 代價樹搜索 24 狀態(tài)空間搜索的基本思想 先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現在這些子節(jié)點中。 一般圖搜索過程 算法的數據結構和符號約定 Open表：用于存放剛生成的節(jié)點 Closed表：用于存放已經擴展或將要擴展的節(jié)點 S0：用表示問題的初始狀態(tài) G：表示搜索過程所得到的搜索圖 M：表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集。（新生成的） ② 對那些原來已在 G中出現過，但還沒有被擴展的 M成員，確定是否需要修改它指向父節(jié)點的指針。 26 算法的幾點說明： (1) 上述過程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過程的一個特例。 以上三種情況是對一般圖搜索算法而言的。 如果發(fā)生第③種情況，除了需要確定