【正文】 Open表 是否為空 失敗 把第 1個結(jié)點(diǎn) n，從 Open表 移出并把它放入 Closed表中 擴(kuò)展 n,把它的后繼結(jié)點(diǎn)放入 Open表的末端 ,提供回到 n的 指針 是否有 任何后繼結(jié)點(diǎn)為目標(biāo) 結(jié)點(diǎn)？ 成 功 否 是 否 是 示意圖 算法框圖 2 8 3 1 4 7 6 5 S0 1 2 8 3 1 4 7 6 5 2 2 3 1 8 4 7 6 5 3 2 8 3 1 4 7 6 5 4 2 8 3 1 6 4 7 5 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 6 7 8 9 10 11 12 13 8 3 2 1 4 7 6 5 2 8 3 7 1 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 14 15 21 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 22 23 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 24 25 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 26 27 Sg 解的路徑是： S0 →3 → 8 → 16 → 26( Sg) 八數(shù)碼難題的廣度優(yōu)先搜索 ?廣度優(yōu)先搜索是一種完備策略，即只要問題有解 ,它就一定可以找到解。解可從目標(biāo)結(jié)點(diǎn)開始直到初始結(jié)點(diǎn)的返回指針中得到，算法成功退出。 ? 廣度優(yōu)先搜索算法如下： ? (1)把初始結(jié)點(diǎn)放入 Open表中； ? (2)如果 Open表為空，則問題無解，失敗退出； ? (3)把 Open表的第一個結(jié)點(diǎn)取出 ， 放入 Closed表 ， 并記該結(jié)點(diǎn)為 n； ? (4)擴(kuò)展節(jié)點(diǎn) n，如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第 (2)步； ? (5)把 n的所有后繼結(jié)點(diǎn)放入 Open表的末尾，并提供從這些后繼結(jié)點(diǎn)回到父結(jié)點(diǎn) (編號值為 n)的指針 。 數(shù)據(jù)結(jié)構(gòu) ? Open表（ 未擴(kuò)展節(jié)點(diǎn)表 ） 存放未進(jìn)行過擴(kuò)展的節(jié)點(diǎn) ? Closed表（ 已擴(kuò)展節(jié)點(diǎn)表 ） 存放已經(jīng)擴(kuò)展過的節(jié)點(diǎn) 節(jié)點(diǎn) 父節(jié)點(diǎn) 編號 節(jié)點(diǎn) 父節(jié)點(diǎn) Open表： Closed表 ： 算法步驟 Step1 把初始節(jié)點(diǎn) S0放入 Open表，建立僅包含 S0的圖 G； Step2 從 Open表中取出待擴(kuò)展節(jié)點(diǎn)，放入 Closed表 ； （不同搜索策略的區(qū)別主要體現(xiàn)于此） Step3 對節(jié)點(diǎn)進(jìn)行擴(kuò)展，將擴(kuò)展得到的、未在 G中出現(xiàn)過的子節(jié)點(diǎn)放入 Open表；根據(jù)需要修改 G中節(jié)點(diǎn)的指針； Step4 重復(fù) Step23直到 狀態(tài)空間 ：待擴(kuò)展節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)或 Open表為空 盲目搜索策略 ? 廣度（寬度）優(yōu)先搜索 先生成的節(jié)點(diǎn)先擴(kuò)展 ? 深度優(yōu)先搜索 后生成的節(jié)點(diǎn)先擴(kuò)展 ? 有界深度優(yōu)先搜索 在深度優(yōu)先策略中增加深度限制，在廣度優(yōu)先與深度優(yōu)先之間折衷 完備 最小路徑解 效率 2 8 3 1 4 7 6 5 S0 1 2 3 8 4 7 6 5 Sg 盲目搜索例（狀態(tài)空間） : 八數(shù)碼難題 在 3*3 的方格棋盤上，分別放置了標(biāo)有數(shù)字 8的八張牌，初始狀態(tài) S0和目標(biāo)狀態(tài) Sg分別如圖所示。 一般圖搜索算法 ? 無論是狀態(tài)空間，還是與或圖的問題表示，問題求解過程都可看作是在“ 圖 ”中進(jìn)行搜索。棋盤中留有一個空格，允許其周圍的某一個將牌向空格移動，這樣通過移動將牌就可以不斷改變將牌的布局。全部可能的問題狀態(tài)共有以下 9種： SO=(1， l) S1=（ 1， 2） S2=（ 1， 3） S3=(2， 1） S4=（ 2， 2） S5=（ 2， 3） S6=(3， 1） S7=（ 3， 2） S8=（ 3， 3） 1 2 3 B A B A B A 1 2 3 S0=(1,1) S4=(2,2) S8=(3,3) 二階梵塔問題的初始與目標(biāo)狀態(tài) ? 操作符 ： A(i,j)表示把金片 A從第 i號鋼針移到 j號鋼針上； B(i,j)表示把金片 B從第 i號鋼針移到 j號鋼針上。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大片位于小片的上面。 ? ??, 10 kkk SSS ?? ?GSFS ,0初始 狀態(tài) 中間 狀態(tài) 1 中間 狀態(tài) 2 目標(biāo) 狀態(tài) 狀態(tài)空間例： 二階梵塔問題 ? 設(shè)有三根鋼針，它們的編號分別是 1號、 2號和3號。第 5章 狀態(tài)空間搜索策略 Searching 搜索概述 ? 在解空間中尋找解的過程與 策略 ? 搜索問題的產(chǎn)生 （ 1）結(jié)構(gòu)不良或非結(jié)構(gòu)化的問題，無解析解 （ 2）理論上可解的問題，計算復(fù)雜度可能太高 ? 基本搜索方式 （ 1） 盲目搜索 按預(yù)定策略進(jìn)行搜索，不考慮問題本身的特性 （ 2） 啟發(fā)式 (Heuristic)搜索 利用與問題有關(guān)的啟發(fā)式信息，加快搜索過程 啟發(fā)式搜索 ? 啟發(fā)式信息 與 評價函數(shù) 反映問題特性，可用于確定搜索方向的信息 評價函數(shù)的作用是根據(jù)啟發(fā)式信息，計算對應(yīng)于特定搜索方向的評價值，作為選擇搜索方向的依據(jù)。 ? 局部 (local)搜索 vs. 全局 (glo