【正文】 節(jié)點用某個可用操作進(jìn)行作用，生成該節(jié)點的一組子節(jié)點。 25 一般圖搜索過程 (1) 把初始節(jié)點 S0放入 Open表，并建立目前僅包含 S0的圖 G； (2) 檢查 Open表是否為空，若為空，則問題無解，失敗推出； (3) 把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為節(jié)點 n； (4)考察節(jié)點 n是否為目標(biāo)節(jié)點。把這些子節(jié)點中不是節(jié)點 n先輩的那部分子節(jié)點記入集合 M，并把這些子節(jié)點作為節(jié)點 n的子節(jié)點加入 G中 (6) 針對 M中子節(jié)點的不同情況，分別作如下處理： ① 對那些沒有在 G中出現(xiàn)過的 M成員設(shè)置一個指向其父節(jié)點（即節(jié)點n）的指針，并把它放入 Open表。（原生成但未擴展的） ③ 對于那些先前已在 G中出現(xiàn)過，并已經(jīng)擴展了的 M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。 (8) 轉(zhuǎn)第 (2)步。各種搜索策略的主要區(qū)別在于對 Open表中節(jié)點的排列順序不同。 (2) 在第 (5)步對節(jié)點 n擴展后，生成并記入 M的子節(jié)點有以下三種情況： ① 該子節(jié)點來從未被任何節(jié)點生成過，由 n第一次生成； ② 該子節(jié)點原來被其他節(jié)點生成過，但還沒有被擴展，這一次又被n再次生成； ③ 該子節(jié)點原來被其他節(jié)點生成過，并且已經(jīng)被擴展過，這一次又被 n再次生成。對于盲目搜索，由于其狀態(tài)空間是樹狀結(jié)構(gòu)，因此不會出現(xiàn)后兩種情況，每個節(jié)點經(jīng)擴展后生成的子節(jié)點都是第一次出現(xiàn)的節(jié)點，不必檢查并修改指向父節(jié)點的指針。所謂由原始節(jié)點到該節(jié)點路徑上的代價是指這條路經(jīng)上的所有有向邊的代價之和。其依據(jù)也是由原始節(jié)點到該節(jié)點的路徑上的代價。因此，由所有節(jié)點及其指向父節(jié)點的指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹。由初始節(jié)點到目標(biāo)節(jié)點路徑上的所有操作就構(gòu)成了該問題的解，而路徑由第 (6)步所形成的指向父節(jié)點的指針來確定。 28 基本思想 從初始節(jié)點 S0開始逐層向下擴展，在第 n層節(jié)點還沒有全部搜索完之前，不進(jìn)入第 n+1層節(jié)點的搜索。 搜索算法 (1)把初始節(jié)點 S0放入 Open表中； (2)如果 Open表為空，則問題無解，失敗退出； (3)把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (4)考察節(jié)點 n是否為目標(biāo)節(jié)點。 廣度優(yōu)先和深度優(yōu)先搜索 1. 廣度優(yōu)先搜索 29 例 八數(shù)碼難題 。 可以使用的操作有 空格左移 ， 空格上移 ， 空格右移 ， 空格下移 即只允許把位于空格左、上、右、下方的牌移入空格。 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 1 4 5 7 6 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 S0 1 2 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é)點 S0放入 Open表中； (2) 如果 Open表為空，則問題無解 ，失敗退出； (3) 把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (4) 考察節(jié)點 n是否為目標(biāo)節(jié)點。 廣度優(yōu)先和深度優(yōu)先搜索 2. 深度優(yōu)先搜索 基本思想 從初始節(jié)點 S0開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進(jìn)行考察，如果該子節(jié)點不是目標(biāo)節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進(jìn)行考察，依此向下搜索，直到某個子節(jié)點既不是目標(biāo)節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進(jìn)行考察 。 這樣 ， 對節(jié)點 n2的代價有：g(n2)=g(n1)+c(n1, n2)。 代價樹搜索 1. 代價樹的廣度優(yōu)先搜索 代價樹的廣度優(yōu)先搜索算法： (1) 把初始節(jié)點 S0放入 Open表中，置 S0的代價 g(S0)=0； (2) 如果 Open表為空，則問題無解 ，失敗退出； (3) 把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (4) 考察節(jié)點 n是否為目標(biāo)。按如下公式： g(ni)=g(n)+c(ni) i=1,2,... 計算各子結(jié)點的代價，并根據(jù)各子結(jié)點的代價對 Open表中的全部結(jié)點按由小到大的順序排序。 34 例 城市交通問題。用代價樹的廣度優(yōu)先搜索，求從 A市出發(fā)到 E市，費用最小的交通路線。其中，紅線為最優(yōu)解，其代價為 8 35 代價樹搜索 代價樹的深度優(yōu)先搜索算法： (1) 把初始節(jié)點 S0放入 Open表中，置 S0的代價 g(S0)=0； (2) 如果 Open表為空，則問題無解 ，失敗退出； (3) 把 Open表的第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (4) 考察節(jié)點 n是否為目標(biāo)節(jié)點。然后轉(zhuǎn)第 (2)步。 啟發(fā)性信息的種類 ① 有效地幫助確定擴展節(jié)點的信息； ② 有效的幫助決定哪些后繼節(jié)點應(yīng)被生成的信息； ③ 能決定在擴展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除的信息 。 啟發(fā)性信息和估價函數(shù) 1. 啟發(fā)性信息 39 估價函數(shù)用來估計節(jié)點重要性的函數(shù) 。 它的一般形式為： f(n)=g(n)+h(n) 其中， g(n)是從初始節(jié)點 S0到節(jié)點 n的實際代價； h(n)是從節(jié)點 n到目標(biāo)節(jié)點 Sg的最優(yōu)路徑的估計代價。設(shè)問題的初始狀態(tài) S0和目標(biāo)狀態(tài) Sg如下圖所示，且估價函數(shù)為 f(n)=d(n)+W(n) 其中： d(n)表示節(jié)點 n在搜索樹中的深度 W(n)表示節(jié)點 n中“不在位”的數(shù)碼個數(shù)。 它說明是用從 S0到 n的路徑上的單位代價表示實際代價 ， 用結(jié)點 n中 “ 不在位 ” 的數(shù)碼個數(shù)作為啟發(fā)信息 。 對初始節(jié)點 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 概念： 在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對 Open表中的節(jié)點進(jìn)行排序，則該搜索算法為 A算法。 類型： 可根據(jù)搜索過程中選擇擴展節(jié)點的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。 局部擇優(yōu)： 僅從剛生成的子節(jié)點中選擇一個 估價函數(shù)值最小的一個進(jìn)行擴展。若是，則找到了問題的解，成功退出； (5)若節(jié)點 n不可擴展，則轉(zhuǎn)第 (2)步； (6)擴展節(jié)點 n，生成其子節(jié)點 ni(i=1, 2, …) ，計算每一個子節(jié)點的估價值 f(ni)(i=1, 2, …) ，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后將這些子節(jié)點放入 Open表中； (7)根據(jù)各節(jié)點的估價函數(shù)值，對 Open表中的全部節(jié)點按從小到大的順序重新進(jìn)行排序； (8)轉(zhuǎn)第 (2)步。 設(shè)問題的初始狀態(tài) S0和目標(biāo)狀態(tài) Sg如圖所示 ， 估價函數(shù)與例 。 解： 該問題的全局擇優(yōu)搜索樹如下圖所示 。 例如 ， 對節(jié)點 S2， 其估價函數(shù)值的計算為： f(S2)=d(S2)+W(S2) =1+3=4 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 S0 Sg 44 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 S0 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 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 4 4 5 5 5 6 4 6 4 4 Sg S1 S2 八數(shù)碼難題的全局擇優(yōu)搜索樹 該問題的解為： S0→S 1→S 2→S 3→S g S3 6 45 A*算法 A*算法是對 A算法的 估價函數(shù) f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法 假設(shè) f*(n)是從初始節(jié)點出發(fā)，約束經(jīng)過節(jié)點 n達(dá)到目標(biāo)節(jié)點的最小代價，估價函數(shù) f(n)是對 f*(n)的估計值。 即滿足上述兩條限制的 A算法稱為 A