【正文】 0) S15=(0, 0, 0) 有了這些狀態(tài)，還需要考慮可進(jìn)行的操作。=1b 在這種表示方式下， m和 c都可取 0、 3中之一， b可取0和 1中之一。=3m 右岸野人數(shù) c39。從而可用一個三元組來表示狀態(tài) S=(m, c, b) 其中， m表示左岸的修道士人數(shù)， c表示左岸的野人數(shù)， b表示左岸的船數(shù)。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (5/11) 10 解： 首先選取描述問題狀態(tài)的方法。 設(shè)在河的一岸有三個野人、三個修道士和一條船，修道士想用這條船把所有的人運(yùn)到河對岸，但受以下條件的約束： 一是修道士和野人都會劃船，但每次船上至多可載兩個人； 二是在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會被野人吃掉。例如，從 (1, 1)開始，通過使用操作 A(1, 3)、 B(1, 2)及 A(3, 2)，可到達(dá) (3, 3)。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (3/11) 8 (3,3) (1,3) (1,2) (2,2) 二階梵塔的狀態(tài)空間圖 從初始節(jié)點(diǎn) (1, 1)到目標(biāo)節(jié)點(diǎn) (2, 2)及 (3, 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)和目標(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號鋼針移到 j號鋼針上； B(i, j)表示把金片 B從第 i號鋼針一到第 j號鋼針上。 要求把這兩個金片全部移到另一根鋼針上 ， 而且規(guī)定每次只能移動一個金片 ， 任何時(shí)刻都不能使大的位于小的上面 。 設(shè)有三根鋼針 ， 它們的編號分別是1號 、 2號和 3號 。 4 狀態(tài)空間法求解問題的基本過程： 首先為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法； 然后從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止； 此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個解。 狀態(tài)空間也可用一個賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖。 狀態(tài)空間 (State space) 用來描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。操作可以是一個機(jī)械步驟，一個運(yùn)算，一條規(guī)則或一個過程。 按問題的表示方式： 狀態(tài)空間搜索：用狀態(tài)空間法來求解問題所進(jìn)行的搜索 與或樹搜索：用問題歸約法來求解問題時(shí)所進(jìn)行的搜索 3 狀態(tài)空間法 1. 狀態(tài)空間表示方法 狀態(tài) (State)： 是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)，它可形式地表示為： Sk={Sk0, Sk1, …} 當(dāng)對每一個分量都給以確定的值時(shí)，就得到了一個具體的狀態(tài)。 概念： 依靠經(jīng)驗(yàn)，利用已有知識，根據(jù)問題的實(shí)際情況，不斷尋找可利用知識，從而構(gòu)造一條代價(jià)最小的推理路線，使問題得以解決的過程稱為搜索 搜索的類型 按是否使用啟發(fā)式信息： 盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息并不改變控制策略。 搜索是人工智能中的一個基本問題，并與推理密切相關(guān)，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。 搜索的基本概念 狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 與 /或樹的盲目搜索 與 /或樹的啟發(fā)式搜索 博弈樹的啟發(fā)式搜索 第 4章 搜索策略 1 搜索的基本概念 搜索的含義 狀態(tài)空間法 問題歸約法 2 搜索的含義 適用情況： 不良結(jié)構(gòu)或非結(jié)構(gòu)化問題；難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用。 啟發(fā)式搜索：在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。 操作 (Operator) 也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。操作可理解為狀態(tài)集合上的一個函數(shù)，它描述了狀態(tài)之間的關(guān)系。常用一個三元組表示為： (S, F, G) 其中， S為問題的所有初始狀態(tài)的集合； F為操作的集合； G為目標(biāo)狀態(tài)的集合。在狀態(tài)空間圖中，節(jié)點(diǎn)表示問題的狀態(tài)，有向邊表示操作。 狀態(tài)空間法 2. 狀態(tài)空間問題求解 5 例 二階梵塔問題 。 在初始情況下 ， 1號鋼針上穿有 A、 B兩個金片 ， A比 B小 ， A位于 B的上面 。 解： 設(shè)用 Sk=(Sk0, Sk1)表示問題的狀態(tài)，其中， Sk0表示金片 A所在的鋼針號， Sk1表示金片 B所在的鋼針號。共有 12種操作，它們分別是： A(1, 2) A(1, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2) B(1, 2) B(1, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2) 根據(jù)上述 9種可能的狀態(tài)和 12種操作，可構(gòu)成二階梵塔問題的狀態(tài)空間圖，如下圖所示。其中，最短的路徑長度是 3，它由 3個操作組成。 A(1,2) B(1,3) A(2,3) (1,1) (3,1) (3,2) (2,1) (2,3) A(1,3) B(1,2) A(3,2) 9 例 修道士 (Missionaries)和野人 (Cannibals)問題 (簡稱MC問題 )。 如果野人會服從任何一次過河安排，請規(guī)劃一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計(jì)劃。在這個問題中，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸。 右岸的狀態(tài)可由下式確定： 右岸修道士數(shù) m39。=3c 右岸船數(shù) b39。因此，共有 4 4 2=32種狀態(tài)。 操作 是指用船把修道士或野人從河的左岸運(yùn)到右岸，或從河的右岸運(yùn)到左岸。 因此， 操作應(yīng)由條件部分和動作部分： 條件： 只有當(dāng)其條件具備時(shí)才能使用 動作： 刻劃了應(yīng)用此操作所產(chǎn)生的結(jié)果。 操作符號 條件 動作 P01 b=1, m=0或 3, c≥1 b=0, c=c1 Q01 b=0, m=0或 3， c≤2 b=1, c=c+1 13 a b c 例 猴子摘香蕉問題。 解： 問題的狀態(tài)可用 4元組 （ w, x, y, z） 表示。 狀態(tài)空間法 3. 狀態(tài)空間的例子 (9/11) 14 所有可能的狀態(tài)為 S0: (a, b, 0, 0) 初始狀態(tài) S1: (b, b, 0, 0) S2: (c, c, 0, 0) S3: (c, c, 1, 0) S4: (c, c, 1, 1) 目標(biāo)狀態(tài) 允許的操作為 Goto(u)：猴子走到位置 u，即 (w, x, 0, 0)→(u, x, 0, 0) Pushbox(v): 猴子推著箱子到水平位置 v，即 (x, x, 0, 0)→(v, v, 0, 0) Climbbox: 猴子爬上箱子，即 (x, x, 0, 0)→(x, x, 1, 0) Grasp；猴子拿到香蕉，即 (c, c, 1, 0 )→(c, c, 1, 1) 這個問題的狀態(tài)空間圖如下圖所示。 分解 如果一個問題 P可以歸約為一組子問題 P1,P2,…,P n，并且只有當(dāng)所有子問題 Pi都有解時(shí)原問題 P才有解，任何一個子問題 Pi無解都會導(dǎo)致原問題 P無解，則稱此種歸約為問題的分解。 等價(jià)變換 如果一個問題 P可以歸約為一組子問題 P1,P2,…,P n，并且子問題 Pi中只要有一個有解則原問題 P就有解，只有當(dāng)所有子問題 Pi都無解時(shí)原問題 P才無解，稱此種歸約為問題的等價(jià)變換，簡稱變換。 問題歸約法 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) 。 (5) 可解節(jié)點(diǎn)與不可解節(jié)點(diǎn) 在與 /或樹中，滿足以下三個條件之一的節(jié)點(diǎn)為 可解節(jié)點(diǎn)： ① 任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)。 ③ 對“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。 ② 對“或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)都為不可解節(jié)點(diǎn)，則該或節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 19 P t t t 解樹 (6) 解樹 由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)（它對應(yīng)著原始問題）為可解節(jié)點(diǎn)的子樹為解樹。 例如，右圖給出的與或樹中，用紅 線表示的子樹是一個解樹。根據(jù)可解節(jié)點(diǎn)的定義，很容易推出原始問題 P為可解節(jié)點(diǎn)。這一過程涉及到搜索的問題，對于與 /或樹的搜索將在后面詳細(xì)討論。要求把 1號鋼針上的 3個金片全部移到 3號鋼針上，如下圖所示。 為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。上述三元組中 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, 2, 2)→(3, 2, 2) (3) 把金片 A及 B移到 3號鋼針的雙金片移動問題。 三階梵塔問題的分解過程可用如下圖與 /或樹來表示 (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é)點(diǎn)，它們分別對應(yīng)著 7個本原問題。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。所謂對一個節(jié)點(diǎn)進(jìn)行“擴(kuò)展”是指對該