【正文】 1 b=0, m=0或 3， c≤2 b=1, c=c+1 13 a b c 例 猴子摘香蕉問題。 狀態(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) 這個(gè)問題的狀態(tài)空間圖如下圖所示。 等價(jià)變換 如果一個(gè)問題 P可以歸約為一組子問題 P1,P2,…,P n，并且子問題 Pi中只要有一個(gè)有解則原問題 P就有解，只有當(dāng)所有子問題 Pi都無解時(shí)原問題 P才無解，稱此種歸約為問題的等價(jià)變換，簡(jiǎn)稱變換。 (5) 可解節(jié)點(diǎn)與不可解節(jié)點(diǎn) 在與 /或樹中，滿足以下三個(gè)條件之一的節(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)。 例如，右圖給出的與或樹中，用紅 線表示的子樹是一個(gè)解樹。這一過程涉及到搜索的問題，對(duì)于與 /或樹的搜索將在后面詳細(xì)討論。 為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。即 (1, 2, 2)→(3, 2, 2) (3) 把金片 A及 B移到 3號(hào)鋼針的雙金片移動(dòng)問題。若出現(xiàn)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 25 一般圖搜索過程 (1) 把初始節(jié)點(diǎn) S0放入 Open表，并建立目前僅包含 S0的圖 G； (2) 檢查 Open表是否為空，若為空，則問題無解，失敗推出； (3) 把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn) n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。（原生成但未擴(kuò)展的） ③ 對(duì)于那些先前已在 G中出現(xiàn)過，并已經(jīng)擴(kuò)展了的 M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。各種搜索策略的主要區(qū)別在于對(duì) Open表中節(jié)點(diǎn)的排列順序不同。對(duì)于盲目搜索，由于其狀態(tài)空間是樹狀結(jié)構(gòu)，因此不會(huì)出現(xiàn)后兩種情況，每個(gè)節(jié)點(diǎn)經(jīng)擴(kuò)展后生成的子節(jié)點(diǎn)都是第一次出現(xiàn)的節(jié)點(diǎn)，不必檢查并修改指向父節(jié)點(diǎn)的指針。其依據(jù)也是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的代價(jià)。由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑上的所有操作就構(gòu)成了該問題的解，而路徑由第 (6)步所形成的指向父節(jié)點(diǎn)的指針來確定。 搜索算法 (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)先搜索 2. 深度優(yōu)先搜索 基本思想 從初始節(jié)點(diǎn) S0開始，在其子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)行考察，如果該子節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)且可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn)，然后再在此子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)行考察，依此向下搜索，直到某個(gè)子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察 。 代價(jià)樹搜索 1. 代價(jià)樹的廣度優(yōu)先搜索 代價(jià)樹的廣度優(yōu)先搜索算法： (1) 把初始節(jié)點(diǎn) S0放入 Open表中，置 S0的代價(jià) g(S0)=0； (2) 如果 Open表為空，則問題無解 ，失敗退出； (3) 把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4) 考察節(jié)點(diǎn) n是否為目標(biāo)。 34 例 城市交通問題。其中，紅線為最優(yōu)解，其代價(jià)為 8 35 代價(jià)樹搜索 代價(jià)樹的深度優(yōu)先搜索算法： (1) 把初始節(jié)點(diǎn) S0放入 Open表中，置 S0的代價(jià) g(S0)=0； (2) 如果 Open表為空，則問題無解 ，失敗退出； (3) 把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4) 考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。 啟發(fā)性信息的種類 ① 有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息； ② 有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息； ③ 能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上刪除的信息 。 它的一般形式為： f(n)=g(n)+h(n) 其中， g(n)是從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的實(shí)際代價(jià)； h(n)是從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn) Sg的最優(yōu)路徑的估計(jì)代價(jià)。 它說明是用從 S0到 n的路徑上的單位代價(jià)表示實(shí)際代價(jià) ， 用結(jié)點(diǎn) n中 “ 不在位 ” 的數(shù)碼個(gè)數(shù)作為啟發(fā)信息 。 類型： 可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。若是，則找到了問題的解，成功退出； (5)若節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第 (2)步； (6)擴(kuò)展節(jié)點(diǎn) n，生成其子節(jié)點(diǎn) ni(i=1, 2, …) ，計(jì)算每一個(gè)子節(jié)點(diǎn)的估價(jià)值 f(ni)(i=1, 2, …) ，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后將這些子節(jié)點(diǎn)放入 Open表中； (7)根據(jù)各節(jié)點(diǎn)的估價(jià)函數(shù)值，對(duì) Open表中的全部節(jié)點(diǎn)按從小到大的順序重新進(jìn)行排序； (8)轉(zhuǎn)第 (2)步。 解： 該問題的全局擇優(yōu)搜索樹如下圖所示 。 即滿足上述兩條限制的 A算法稱為 A*算法。 證明： 首先證明算法必然會(huì)結(jié)束。 由于至少存在一條有初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，設(shè)此路徑為 S0=n0, n1, … , n k=Sg 算法開始時(shí)，節(jié)點(diǎn) n0在 Open表中，而且路徑中任一節(jié)點(diǎn) ni離開 Open表后，其后繼節(jié)點(diǎn) ni+1必然進(jìn)入 Open表，這樣，在 Open表變?yōu)榭罩?，目?biāo)節(jié)點(diǎn)必然出現(xiàn)在 Open表中。 A*算法 1. A*算法的可納性 (2/6) 48 引理 在 A*算法終止前的任何時(shí)刻， Open表中總存在節(jié)點(diǎn) n’ ，它是從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn)的最佳路徑上的一個(gè)節(jié)點(diǎn)，且滿足 f(n’ )≤ f*(S0)。則有 f(n39。在最佳路徑上，故有 g(n39。)+h(n39。)≤g*(n39。)≤f*(S0) A*算法 1. A*算法的可納性 (3/6) 49 定理 對(duì)無限圖，若從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則 A*算法必然會(huì)結(jié)束。 證明： 證明過程分以下兩步進(jìn)行： 先證明 A*算法一定能夠終止在某個(gè)目標(biāo)節(jié)點(diǎn)上。在 Open表中，且有 f(n’ )≤f*(S0)f(t) 這時(shí)， A*算法一定會(huì)選擇 n39。 證明： 令 n是由 A*選作擴(kuò)展的任一節(jié)點(diǎn)，因此 n不會(huì)是目標(biāo)節(jié)點(diǎn)，且搜索沒有結(jié)束。則有 f(n)≤f*(S0)；否則，選擇 n擴(kuò)展，必有 f(n) ≤f(n39。 下面通過一個(gè)定理來描述這一特性。 (3) 證明 A2 *中 d(n)=k+1的任意節(jié)點(diǎn) n，也要由 A1 *擴(kuò)展。既然節(jié)點(diǎn) n沒有被 A1 *擴(kuò)展，則有 f1(n)≥f*(S0) 即 g1(n)+h1(n)≥f*(S0)。 如果能夠保證，每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)就已經(jīng)找到了通往這個(gè)節(jié)點(diǎn)的最佳路徑，就沒有必要再去作上述檢查 為滿足這一要求，我們需要對(duì)啟發(fā)函數(shù) h(n)增加單調(diào)性限制。 證明： 設(shè) A*正要擴(kuò)展節(jié)點(diǎn) n，而節(jié)點(diǎn)序列 S0=n0, n1, … ,n k=n 是由初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的最佳路徑。 在 h(n)滿足單調(diào)性限制下的 A*算法常被稱為改進(jìn)的 A*算法。 對(duì) A*算法 ， 首先需要確定估價(jià)函數(shù) 。 A*算法應(yīng)用舉例 59 (3,3,1) h=4 f=4 (3,2,0) (3,1,0) (2,2,0) (3,2,1) (2,1,0) (3,0,0) (2,2,1) (3,1,1) (0,2,0) (1,1,0) (0,3,1) (0,1,0) (0,2,1) (0,0,0) h=5 f=6 h=3 f=5 h=3 f=6 h=3 f=6 h=2 f=6 h=2 f=7 h=1 f=7 h=1 f=8 h=0 f=8 傳教士和野人問題的搜索圖 問題狀態(tài)： (m,c,b) 估價(jià)函數(shù)： h(n)=m+c2b h=4 f=5 h=4 f=5 h=2 f=6 h=2 f=7 60 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 ?狀態(tài)空間的啟發(fā)式搜索 與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 61 與 /或樹的搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。 其搜索算法如下： (1)把初始節(jié)點(diǎn) S0放入 Open表中； (2)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (3)如果節(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)先搜索 1. 廣度優(yōu)先搜索 63 ② 考察這些子節(jié)點(diǎn)中有否終止節(jié)點(diǎn) 。 (4) 如果節(jié)點(diǎn) n不可擴(kuò)展，則作下列工作： ① 標(biāo)記節(jié)點(diǎn) n為不可解節(jié)點(diǎn)； ② 應(yīng)用不可解標(biāo)記過程對(duì)節(jié)點(diǎn) n的先輩中不可解解的節(jié)點(diǎn)進(jìn)行標(biāo)記 。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的廣度優(yōu)先搜索 搜索過程為： (1) 先擴(kuò)展 1號(hào)節(jié)點(diǎn)，生成 2號(hào)節(jié)點(diǎn)和 3號(hào)節(jié)點(diǎn)。 (6) 擴(kuò)展 5號(hào)節(jié)點(diǎn)，生成 t3節(jié)點(diǎn)和 C節(jié)點(diǎn)。調(diào)用不可解標(biāo)記過程 … 。在擴(kuò)展節(jié)點(diǎn)時(shí)，與 /或樹的深度優(yōu)先搜索過程總是把剛生成的節(jié)點(diǎn)放在Open表的首部。 ③ 轉(zhuǎn)第 (2)步。 67 對(duì)上例， 若按有界深度優(yōu)先，且 設(shè) dm=4，則其節(jié)點(diǎn)擴(kuò)展順序?yàn)椋?， 3， 5， 2， 4。 (6) 搜索成功，得到由 4號(hào)節(jié)點(diǎn)即 tt t3節(jié)點(diǎn)構(gòu)成的解樹。 (3)擴(kuò)展 5號(hào)節(jié)點(diǎn)，生成 t3節(jié)點(diǎn)和 C節(jié)點(diǎn)。 最優(yōu)解樹是指代價(jià)最小的那棵解樹。 若用和代價(jià)法，則其計(jì)算公式為： 若用最大代價(jià)法，則其計(jì)算公式為： (4)若 n是端節(jié)點(diǎn)，但又不是終止節(jié)點(diǎn)，則 n不可擴(kuò)展，其代價(jià)定義為h(n)=∝ 。 請(qǐng)計(jì)算解樹的代價(jià) 。 解樹的代價(jià)與希望樹 2. 希望樹 ? ?1m in ( , ) ( )iiik c n n h n?? ?73 與 /或樹的啟發(fā)式搜索過程如下： (1) 把初始節(jié)點(diǎn) S0放入 Open表中，計(jì)算 h(S0)； (2) 計(jì)算希望樹 T； (3) 依次在 Open表中取出 T的端節(jié)點(diǎn)放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)如果節(jié)點(diǎn) n為終止節(jié)點(diǎn)，則做下列工作： ① 標(biāo)記節(jié)點(diǎn) n為可解節(jié)點(diǎn)； ② 在 T上應(yīng)用可解標(biāo)記過程，對(duì) n的先輩節(jié)點(diǎn)中的所有可解解節(jié)點(diǎn)進(jìn)行標(biāo)記； ③ 如果初始解節(jié)點(diǎn) S0能夠被標(biāo)記為可解節(jié)點(diǎn)，則