【正文】 和目標狀態(tài) Sg如圖所示 ， 估價函數(shù)與例 。 對初始節(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算法。 啟發(fā)性信息和估價函數(shù) 1. 啟發(fā)性信息 39 估價函數(shù)用來估計節(jié)點重要性的函數(shù) 。用代價樹的廣度優(yōu)先搜索，求從 A市出發(fā)到 E市，費用最小的交通路線。 這樣 ， 對節(jié)點 n2的代價有：g(n2)=g(n1)+c(n1, n2)。 廣度優(yōu)先和深度優(yōu)先搜索 1. 廣度優(yōu)先搜索 29 例 八數(shù)碼難題 。因此，由所有節(jié)點及其指向父節(jié)點的指針所構(gòu)成的集合是一棵樹，稱為搜索樹。 (2) 在第 (5)步對節(jié)點 n擴展后，生成并記入 M的子節(jié)點有以下三種情況： ① 該子節(jié)點來從未被任何節(jié)點生成過，由 n第一次生成； ② 該子節(jié)點原來被其他節(jié)點生成過，但還沒有被擴展，這一次又被n再次生成； ③ 該子節(jié)點原來被其他節(jié)點生成過，并且已經(jīng)被擴展過，這一次又被 n再次生成。把這些子節(jié)點中不是節(jié)點 n先輩的那部分子節(jié)點記入集合 M，并把這些子節(jié)點作為節(jié)點 n的子節(jié)點加入 G中 (6) 針對 M中子節(jié)點的不同情況，分別作如下處理： ① 對那些沒有在 G中出現(xiàn)過的 M成員設置一個指向其父節(jié)點（即節(jié)點n）的指針，并把它放入 Open表。 三階梵塔問題的分解過程可用如下圖與 /或樹來表示 (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個本原問題。要求把 1號鋼針上的 3個金片全部移到 3號鋼針上，如下圖所示。 19 P t t t 解樹 (6) 解樹 由可解節(jié)點構(gòu)成，并且由這些可解節(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é)點 。 解： 問題的狀態(tài)可用 4元組 （ w, x, y, z） 表示。因此，共有 4 4 2=32種狀態(tài)。 如果野人會服從任何一次過河安排，請規(guī)劃一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計劃。 解： 設用 Sk=(Sk0, Sk1)表示問題的狀態(tài)，其中， Sk0表示金片 A所在的鋼針號， Sk1表示金片 B所在的鋼針號。常用一個三元組表示為： (S, F, G) 其中， S為問題的所有初始狀態(tài)的集合； F為操作的集合； G為目標狀態(tài)的集合。 搜索的基本概念 狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 與 /或樹的盲目搜索 與 /或樹的啟發(fā)式搜索 博弈樹的啟發(fā)式搜索 第 4章 搜索策略 1 搜索的基本概念 搜索的含義 狀態(tài)空間法 問題歸約法 2 搜索的含義 適用情況： 不良結(jié)構(gòu)或非結(jié)構(gòu)化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用。操作可以是一個機械步驟，一個運算，一條規(guī)則或一個過程。 設有三根鋼針 ， 它們的編號分別是1號 、 2號和 3號 。例如，從 (1, 1)開始，通過使用操作 A(1, 3)、 B(1, 2)及 A(3, 2)，可到達 (3, 3)。=3m 右岸野人數(shù) c39。 12 操作的表示： 用符號 Pij表示從左岸到右岸的運人操作 用符號 Qij表示從右岸到左岸的操作 其中： i表示 船上的修道士人數(shù) j表示 船上的野人數(shù) 操作集 本問題有 10種操作可供選擇： F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20} 下面以 P01和 Q01為例來說明這些操作的條件和動作。 即分解所得到的子問題的“與”與原問題 P等價。 同樣，可用類似的方法定義 不可解節(jié)點： ① 不為終止節(jié)點的端節(jié)點是不可解節(jié)點。 問題歸約求解過程就實際上就是生成解樹，即證明原始節(jié)點是可解節(jié)點的過程。即 (1, 1, 1)→(1, 2, 2) (2) 把金片 C移到 3號鋼針上的單金片移動問題。 一般圖搜索過程 算法的數(shù)據(jù)結(jié)構(gòu)和符號約定 Open表：用于存放剛生成的節(jié)點 Closed表：用于存放已經(jīng)擴展或?qū)⒁獢U展的節(jié)點 S0：用表示問題的初始狀態(tài) G：表示搜索過程所得到的搜索圖 M：表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集。 26 算法的幾點說明： (1) 上述過程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過程的一個特例。 如果發(fā)生第③種情況，除了需要確定該子節(jié)點指向父節(jié)點的指針外，還需要確定其后繼節(jié)點指向父節(jié)點的指針。 Open表中的節(jié)點總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。若是，則得到問題的解，成功退出； (5) 若節(jié)點 n不可擴展，則轉(zhuǎn)第 (2)步； (6) 擴展節(jié)點 n，將其子節(jié)點放入 Open表的首部，并為每一個子節(jié)點設置 指向父節(jié)點的指針，然后轉(zhuǎn)第 (2)步。然后轉(zhuǎn)第 (2)步。 36 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 第 4章 搜索策略 37 狀態(tài)空間的啟發(fā)式搜索 啟發(fā)性信息和估價函數(shù) A算法 A*算法 A*算法應用舉例 38 啟發(fā)性信息的概念 啟發(fā)性信息是指那種與具體問題求解過程有關的 ， 并可指導搜索過程朝著最有希望方向前進的控制信息 。 請計算初始狀態(tài) S0的估價函數(shù)值 f(S0) 40 解： 取 g(n)=d(n)， h(n)=W(n)。 A算法 42 全局擇優(yōu)搜索 A算法描述： (1)把初始節(jié)點 S0放入 Open表中， f(S0)=g(S0)+h(S0)； (2)如果 Open表為空，則問題無解 ，失敗退出； (3)把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (4)考察節(jié)點 n是否為目標節(jié)點。且 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)。 然后證明算法一定會成功結(jié)束。設這些節(jié)點中排在最前面的節(jié)點為 n39。)=g*(n39。) 因為在最佳路徑上的所有節(jié)點的 f*值都應相等，因此有 f(n39。（反證法） 假設 A*算法未能終止在最佳路徑上，而是終止在 某個目標節(jié)點 t處，則有 f(t)=g(t)f*(S0) 但由引理 ，在 A*算法結(jié)束前，必有最佳路徑上的一個節(jié)點 n39。若 n=n39。 (2) 假設對 A2 *中 d(n)=k的任意節(jié)點 n結(jié)論成立，即 A1 *也擴展了這些節(jié)點。 對已在 Open表中的子節(jié)點，需要決定是否調(diào)整指向其父節(jié)點的指針； 對已在 Closed表中的子節(jié)點，除需要決定是否調(diào)整其指向父節(jié)點的指針外，還需要決定是否調(diào)整其子節(jié)點的后繼節(jié)點的父指針。如果 h(n)不滿足單調(diào)性限制，則它們不一定成立。 MC問題的搜索過程如下圖所示。 ③ 轉(zhuǎn)第 (2)步。由于 t1為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，不能確定 3號節(jié)點是否可解。 65 與 /或樹的深度優(yōu)先搜索和與 /或樹的廣度優(yōu)先搜索過程基本相同，其主要區(qū)別在于 Open表中節(jié)點的排列順序不同。 ③ 轉(zhuǎn)第 (2)步。由于 t2為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，可標記 2號節(jié)點為可解，再往上又可標記 1號節(jié)點為可解。 (3)若 n為與節(jié)點，且子節(jié)點為 n1, n2, … ,n k，則 n的代價可用和代價法或最大代價法。 定義 希望解樹 (1) 初始節(jié)點 S0在希望樹 T (2) 如果 n是具有子節(jié)點 n1, n2, … , n k的或節(jié)點，則 n的某個子節(jié)點 ni在希望樹 T中的充分必要條件是 (3) 如果 n是與節(jié)點，則 n的全部子節(jié)點都在希望樹 T中。 (5)根節(jié)點的代價即為解樹的代價。由于 t3為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，可標記 3號節(jié)點為可解節(jié)點，但不能標記 1號為可解。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 搜索過程為： (1) 先擴展 1號節(jié)點，生成 2號節(jié)點和3號節(jié)點。 與 /或樹的深度優(yōu)先搜索也可以帶有深度限制 dm，其搜索算法如下： (1)把初始節(jié)點 S0放入 Open表中； (2)把 Open表第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (3)如果節(jié)點 n的深度等于 dm，則轉(zhuǎn)第 (5)步的第 ① 點； (4)如果節(jié)點 n可擴展，則做下列工作： ① 擴展節(jié)點 n，將其子節(jié)點放入 Open表的首部，并為每一個子節(jié)點設置指向父節(jié)點的指針； 與 /或樹的廣度優(yōu)先和深度優(yōu)先搜索 2. 深度優(yōu)先搜索 66 ② 考察這些子節(jié)點中是否有終止節(jié)點 。由于 t3為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，可標記 1號節(jié)點為可解節(jié)點。 如果初始解節(jié)點 S0也被標記為不可解節(jié)點 ， 則搜索失敗 ， 表明原始問題無解 ， 退出搜索過程；如果不能確定 S0為不可解節(jié)點 ， 則從 Open表中刪去具有不可解先輩的節(jié)點 。其一般搜索過程如下： (1) 把原始問題作為初始節(jié)點 S0，并把它作為當前節(jié)點； (2) 應用分解或等價變換操作對當前節(jié)點進行擴展； (3) 為每個子節(jié)點設置指向父節(jié)點的指針； (4) 選擇合適的子節(jié)點作為當前節(jié)點，反復執(zhí)行第 (2)步和第 (3)步，在此期間需要多次調(diào)用可解標記過程或不可解標記過程，直到初始節(jié)點被標記為可解節(jié)點或不可解節(jié)點為止。 A*算法 3. h(n)的單調(diào)限制 (3/3) 57 例 八數(shù)碼難題。