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