【文章內(nèi)容簡(jiǎn)介】 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é)點(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)。若是，則得到問題的解，成功退出； (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)先搜索 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)行考察 。 32 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 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 6 7 5 4 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4 2 8 1 6 3 7 5 4 S0 1 2 3 4 5 6 八數(shù)碼難題的深度優(yōu)先搜索如右圖 一種改進(jìn)的深度優(yōu)先算法是有界深度優(yōu)先搜索算法，深度限制為 dm 例 八數(shù)碼難題 33 在代價(jià)樹中 ， 可以用 g(n)表示從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的代價(jià) ， 用 c(n1, n2)表示從父節(jié)點(diǎn) n1到其子節(jié)點(diǎn) n2的代價(jià) 。 這樣 ， 對(duì)節(jié)點(diǎn) n2的代價(jià)有：g(n2)=g(n1)+c(n1, n2)。 代價(jià)樹搜索的目的是為了找到最佳解 ， 即找到一條代價(jià)最小的解路徑 。 代價(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)。若是，則找到了問題的解，成功退出； (5) 若節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第 (2)步； (6) 擴(kuò)展節(jié)點(diǎn) n，生成其子節(jié)點(diǎn) ni(i=1, 2, …) ，將這些子節(jié)點(diǎn)放入 Open表中，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。按如下公式： g(ni)=g(n)+c(ni) i=1,2,... 計(jì)算各子結(jié)點(diǎn)的代價(jià)，并根據(jù)各子結(jié)點(diǎn)的代價(jià)對(duì) Open表中的全部結(jié)點(diǎn)按由小到大的順序排序。然后轉(zhuǎn)第 (2)步。 34 例 城市交通問題。設(shè)有 5個(gè)城市，它們之間的交通線路如左圖所示，圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用，即代價(jià)。用代價(jià)樹的廣度優(yōu)先搜索，求從 A市出發(fā)到 E市，費(fèi)用最小的交通路線。 A B C D E 4 3 4 5 2 3 2 4 5 A C1 B1 D1 D2 E1 E2 B2 C2 E3 3 4 3 4 2 3 城市交通圖 城市交通圖的代價(jià)樹 解： 代價(jià)樹如右圖所示。其中，紅線為最優(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)。若是，則找到了問題的解，成功退出； (5) 若節(jié)點(diǎn) n不可擴(kuò)展，則轉(zhuǎn)第 (2)步； (6) 擴(kuò)展節(jié)點(diǎn) n，生成其子節(jié)點(diǎn) ni(i=1, 2, …) ，將這些子節(jié)點(diǎn)按邊代價(jià)由小到大放入 Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。然后轉(zhuǎn)第 (2)步。 36 ?搜索的基本概念 ?狀態(tài)空間的盲目搜索 狀態(tài)空間的啟發(fā)式搜索 ?與 /或樹的盲目搜索 ?與 /或樹的啟發(fā)式搜索 ?博弈樹的啟發(fā)式搜索 第 4章 搜索策略 37 狀態(tài)空間的啟發(fā)式搜索 啟發(fā)性信息和估價(jià)函數(shù) A算法 A*算法 A*算法應(yīng)用舉例 38 啟發(fā)性信息的概念 啟發(fā)性信息是指那種與具體問題求解過程有關(guān)的 ， 并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息 。 啟發(fā)性信息的種類 ① 有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息； ② 有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息； ③ 能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上刪除的信息 。 啟發(fā)性信息的作用 啟發(fā)信息的啟發(fā)能力越強(qiáng) ， 擴(kuò)展的無用結(jié)點(diǎn)越少 。 啟發(fā)性信息和估價(jià)函數(shù) 1. 啟發(fā)性信息 39 估價(jià)函數(shù)用來估計(jì)節(jié)點(diǎn)重要性的函數(shù) 。 估價(jià)函數(shù) f(n)被定義為從初始節(jié)點(diǎn) S0出發(fā) ， 約束經(jīng)過節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn) Sg的所有路徑中最小路徑代價(jià)的估計(jì)值 。 它的一般形式為： 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à)。 啟發(fā)性信息和估價(jià)函數(shù) 2. 估價(jià)函數(shù) 例 八數(shù)碼難題。設(shè)問題的初始狀態(tài) S0和目標(biāo)狀態(tài) Sg如下圖所示，且估價(jià)函數(shù)為 f(n)=d(n)+W(n) 其中： d(n)表示節(jié)點(diǎn) n在搜索樹中的深度 W(n)表示節(jié)點(diǎn) n中“不在位”的數(shù)碼個(gè)數(shù)。 請(qǐng)計(jì)算初始狀態(tài) S0的估價(jià)函數(shù)值 f(S0) 40 解： 取 g(n)=d(n)， h(n)=W(n)。 它說明是用從 S0到 n的路徑上的單位代價(jià)表示實(shí)際代價(jià) ， 用結(jié)點(diǎn) n中 “ 不在位 ” 的數(shù)碼個(gè)數(shù)作為啟發(fā)信息 。 一般來說 ， 某節(jié)點(diǎn)中的 “ 不在位 ” 的數(shù)碼個(gè)數(shù)越多 ， 說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn) 。 對(duì)初始節(jié)點(diǎn) 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 概念： 在圖搜索算法中，如果能在搜索的每一步都利用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì) Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為 A算法。 由于估價(jià)函數(shù)中帶有問題自身的啟發(fā)性信息，因此， A算法也被稱為啟發(fā)式搜索算法。 類型： 可根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將啟發(fā)式搜索算法分為全局擇優(yōu)搜索算法和局部擇優(yōu)搜索算法。 全局擇優(yōu)： 從 Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。 局部擇優(yōu)： 僅從剛生成的子節(jié)點(diǎn)中選擇一個(gè) 估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。 A算法 42 全局擇優(yōu)搜索 A算法描述： (1)把初始節(jié)點(diǎn) S0放入 Open表中， f(S0)=g(S0)+h(S0)； (2)如果 Open表為空，則問題無解 ，失敗退出； (3)把 Open表的第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (4)考察節(jié)點(diǎn) n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問題的解，成功退出； (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)步。 A算法 43 例 八數(shù)碼難題 。 設(shè)問題的初始狀態(tài) S0和目標(biāo)狀態(tài) Sg如圖所示 ， 估價(jià)函數(shù)與例 。 請(qǐng)用全局擇優(yōu)搜索解決該問題 。 解： 該問題的全局擇優(yōu)搜索樹如下圖所示 。 在該圖中 ， 每個(gè)節(jié)點(diǎn)旁邊的數(shù)字是該節(jié)點(diǎn)的估價(jià)函數(shù)值 。 例如 ， 對(duì)節(jié)點(diǎn) S2， 其估價(jià)函數(shù)值的計(jì)算為： 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*算法是對(duì) A算法的 估價(jià)函數(shù) f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法 假設(shè) f*(n)是從初始節(jié)點(diǎn)出發(fā)，約束經(jīng)過節(jié)點(diǎn) n達(dá)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，估價(jià)函數(shù) f(n)是對(duì) f*(n)的估計(jì)值。且 f*(n)=g*(n)+h*(n) A*算法 對(duì) A