【正文】 與樹(shù) P1 P2 P3 或樹(shù) P P P1 P2 P3 P12 P12 P31 P32 P33 與 /或樹(shù) (1)與樹(shù) 分解 (2) 或樹(shù) 等價(jià)變換 (3) 與 /或樹(shù) 問(wèn)題歸約法 2. 問(wèn)題的與 /或樹(shù)表示 18 (4) 端節(jié)點(diǎn)與終止節(jié)點(diǎn) 在與 /或樹(shù)中，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為 端節(jié)點(diǎn) ；本原問(wèn)題所對(duì)應(yīng)的節(jié)點(diǎn)稱(chēng)為 終止節(jié)點(diǎn) ?？梢?jiàn)，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不一定是終止節(jié)點(diǎn)。 (5) 可解節(jié)點(diǎn)與不可解節(jié)點(diǎn) 在與 /或樹(shù)中，滿(mǎn)足以下三個(gè)條件之一的節(jié)點(diǎn)為 可解節(jié)點(diǎn)： ① 任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)。 ② 對(duì)“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)。 ③ 對(duì)“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。 同樣，可用類(lèi)似的方法定義 不可解節(jié)點(diǎn)： ① 不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 ② 對(duì)“或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)都為不可解節(jié)點(diǎn)，則該或節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 ③ 對(duì)“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個(gè)為不可解節(jié)點(diǎn)，則該與節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 19 P t t t 解樹(shù) (6) 解樹(shù) 由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)（它對(duì)應(yīng)著原始問(wèn)題）為可解節(jié)點(diǎn)的子樹(shù)為解樹(shù)。在解樹(shù)中一定包含初始節(jié)點(diǎn)。 例如，右圖給出的與或樹(shù)中，用紅 線(xiàn)表示的子樹(shù)是一個(gè)解樹(shù)。在該圖中，節(jié)點(diǎn) P為原始問(wèn)題節(jié)點(diǎn)，用 t標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)。根據(jù)可解節(jié)點(diǎn)的定義，很容易推出原始問(wèn)題 P為可解節(jié)點(diǎn)。 問(wèn)題歸約求解過(guò)程就實(shí)際上就是生成解樹(shù)，即證明原始節(jié)點(diǎn)是可解節(jié)點(diǎn)的過(guò)程。這一過(guò)程涉及到搜索的問(wèn)題，對(duì)于與 /或樹(shù)的搜索將在后面詳細(xì)討論。 20 例 三階梵塔問(wèn)題。要求把 1號(hào)鋼針上的 3個(gè)金片全部移到 3號(hào)鋼針上，如下圖所示。 解： 這個(gè)問(wèn)題也可用狀態(tài)空間法來(lái)解，不過(guò)本例主要用它來(lái)說(shuō)明如何用歸約法來(lái)解決問(wèn)題。 為了能夠解決這一問(wèn)題，首先需要定義該問(wèn)題的形式化表示方法。設(shè)用三元組 (i, j, k) 表示問(wèn)題在任一時(shí)刻的狀態(tài)，用“ → ”表示狀態(tài)的轉(zhuǎn)換。上述三元組中 i 代表金片 C所在的鋼針號(hào) j 代表金片 B所在的鋼針號(hào) k 代表金片 A所在的鋼針號(hào) 1 2 3 1 2 3 問(wèn)題歸約法 2. 問(wèn)題的與 /或樹(shù)表示 A B C A B C 21 利用問(wèn)題歸約方法，原問(wèn)題可分解為以下 三個(gè)子問(wèn)題： (1) 把金片 A及 B移到 2號(hào)鋼針上的雙金片移動(dòng)問(wèn)題。即 (1, 1, 1)→(1, 2, 2) (2) 把金片 C移到 3號(hào)鋼針上的單金片移動(dòng)問(wèn)題。即 (1, 2, 2)→(3, 2, 2) (3) 把金片 A及 B移到 3號(hào)鋼針的雙金片移動(dòng)問(wèn)題。即 (3, 2, 2)→( (3, 3, 3) 其中，子問(wèn)題 (1)和 (3)都是一個(gè)二階梵塔問(wèn)題，它們都還可以再繼續(xù)進(jìn)行分解；子問(wèn)題 (2)是本原問(wèn)題，它已不需要再分解。 三階梵塔問(wèn)題的分解過(guò)程可用如下圖與 /或樹(shù)來(lái)表示 (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) 在該與 /或樹(shù)中，有 7個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著 7個(gè)本原問(wèn)題。如果把這些本原問(wèn)題從左至右排列起來(lái)，即得到了原始問(wèn)題的解： (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ā)式搜索 ?與 /或樹(shù)的盲目搜索 ?與 /或樹(shù)的啟發(fā)式搜索 ?博弈樹(shù)的啟發(fā)式搜索 第 4章 搜索策略 23 狀態(tài)空間的盲目搜索 一般圖搜索過(guò)程 廣度優(yōu)先和深度優(yōu)先搜索 代價(jià)樹(shù)搜索 24 狀態(tài)空間搜索的基本思想 先把問(wèn)題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問(wèn)題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了問(wèn)題的解；若沒(méi)出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒(méi)有可供操作的節(jié)點(diǎn)為止。所謂對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行“擴(kuò)展”是指對(duì)該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)行作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。 一般圖搜索過(guò)程 算法的數(shù)據(jù)結(jié)構(gòu)和符號(hào)約定 Open表：用于存放剛生成的節(jié)點(diǎn) Closed表：用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展的節(jié)點(diǎn) S0：用表示問(wèn)題的初始狀態(tài) G：表示搜索過(guò)程所得到的搜索圖 M：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集。 25 一般圖搜索過(guò)程 (1) 把初始節(jié)點(diǎn) S0放入 Open表，并建立目前僅包含 S0的圖 G； (2) 檢查 Open表是否為空，若為空，則問(wèn)題無(wú)解，失敗推出； (3) 把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn) n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問(wèn)題的解，成功退出； (5) 擴(kuò)展節(jié)點(diǎn) n，生成一組子節(jié)點(diǎn)。把這些子節(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ì)那些沒(méi)有在 G中出現(xiàn)過(guò)的 M成員設(shè)置一個(gè)指向其父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它放入 Open表。（新生成的） ② 對(duì)那些原來(lái)已在 G中出現(xiàn)過(guò)，但還沒(méi)有被擴(kuò)展的 M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針。（原生成但未擴(kuò)展的） ③ 對(duì)于那些先前已在 G中出現(xiàn)過(guò)，并已經(jīng)擴(kuò)展了的 M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。（原生成也擴(kuò)展過(guò)的） (7) 按某種策略對(duì) Open表中的節(jié)點(diǎn)進(jìn)行排序。 (8) 轉(zhuǎn)第 (2)步。 26 算法的幾點(diǎn)說(shuō)明： (1) 上述過(guò)程是狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過(guò)程的一個(gè)特例。各種搜索策略的主要區(qū)別在于對(duì) Open表中節(jié)點(diǎn)的排列順序不同。例如，廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點(diǎn)排在前面。 (2) 在第 (5)步對(duì)節(jié)點(diǎn) n擴(kuò)展后，生成并記入 M的子節(jié)點(diǎn)有以下三種情況： ① 該子節(jié)點(diǎn)來(lái)從未被任何節(jié)點(diǎn)生成過(guò)，由 n第一次生成； ② 該子節(jié)點(diǎn)原來(lái)被其他節(jié)點(diǎn)生成過(guò)，但還沒(méi)有被擴(kuò)展，這一次又被n再次生成； ③ 該子節(jié)點(diǎn)原來(lái)被其他節(jié)點(diǎn)生成過(guò)，并且已經(jīng)被擴(kuò)展過(guò)，這一次又被 n再次生成。 以上三種情況是對(duì)一般圖搜索算法而言的。對(duì)于盲目搜索，由于其狀態(tài)空間是樹(shù)狀結(jié)構(gòu)，因此不會(huì)出現(xiàn)后兩種情況，每個(gè)節(jié)點(diǎn)經(jīng)擴(kuò)展后生成的子節(jié)點(diǎn)都是第一次出現(xiàn)的節(jié)點(diǎn)，不必檢查并修改指向父節(jié)點(diǎn)的指針。 27 (3) 在第 (6)步針對(duì) M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時(shí)，如果發(fā)生當(dāng)?shù)冖诜N情況，那么，這個(gè) M中的節(jié)點(diǎn)究竟應(yīng)該作為哪一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？一般是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價(jià)來(lái)決定的，哪一條路經(jīng)付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。所謂由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的代價(jià)是指這條路經(jīng)上的所有有向邊的代價(jià)之和。 如果發(fā)生第③種情況，除了需要確定該子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。其依據(jù)也是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的代價(jià)。 (4) 在搜索圖中，除初始節(jié)點(diǎn)外，任意一個(gè)節(jié)點(diǎn)都含有且只含有一個(gè)指向其父節(jié)點(diǎn)的指針。因此，由所有節(jié)點(diǎn)及其指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成的集合是一棵樹(shù)，稱(chēng)為搜索樹(shù)。 (5) 在搜索過(guò)程的第 (4)步，一旦某個(gè)被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則搜索過(guò)程成功結(jié)束。由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑上的所有操作就構(gòu)成了該問(wèn)題的解，而路徑由第 (6)步所形成的指向父節(jié)點(diǎn)的指針來(lái)確定。 (6) 如果搜索過(guò)程終止在第 (2)步，即沒(méi)有達(dá)到目標(biāo)，且 Open表中已無(wú)可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)束。 28 基本思想 從初始節(jié)點(diǎn) S0開(kāi)始逐層向下擴(kuò)展，在第 n層節(jié)點(diǎn)還沒(méi)有全部搜索完之前，不進(jìn)入第 n+1層節(jié)點(diǎn)的搜索。 Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。 搜索算法 (1)把初始節(jié)點(diǎn) S0放入 Open表中； (2)如果 Open表為空，則問(wèn)題無(wú)解，失敗退出； (3)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wè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)步。 廣度優(yōu)先和深度優(yōu)先搜索 1. 廣度優(yōu)先搜索 29 例 八數(shù)碼難題 。 在 3 3的方格棋盤(pán)上 ， 分別放置了表有數(shù)字 8的八張牌 ， 初始狀態(tài) S0， 目標(biāo)狀態(tài) Sg， 如下圖所示 。 可以使用的操作有 空格左移 ， 空格上移 ， 空格右移 ， 空格下移 即只允許把位于空格左、上、右、下方的牌移入空格。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑 。 2 8 3 3 1 4 4 7 6 5 1 2 3 8 4 7 6 5 S0 Sg 30 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 8 3