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