【正文】 bal)搜索 確定搜索方向時(shí)考慮局部信息還是全局信息？ ? 任一解 vs. 最優(yōu)解 搜索方法 ? 圖搜索方法 寬度優(yōu)先法 (breadthfirst)，深度優(yōu)先法 (depthfirst)，有界深度優(yōu)先法，啟發(fā)式最優(yōu)圖搜索法 (A*，AO*)…….. ? 博弈搜索方法 極小極大法 (MiniMax)， AlphaBeta剪枝法 (pruning)……… ? 現(xiàn)代優(yōu)化搜索方法 爬山法 (hill climbing)，模擬退火法 (simulated annealing)，遺傳算法 (geic algorithms)……. 搜索策略的評價(jià) ? 完備性 如果問題有解，能否保證找到？ ? 最優(yōu)性 (optimization) 如果問題存在不同的解，能否找到最優(yōu)解？ ? 時(shí)間復(fù)雜性 找到一個(gè)解需要花費(fèi)多少時(shí)間 ? 空間復(fù)雜性 在搜索過程中需要占用多少內(nèi)存 時(shí)空復(fù)雜性的量度 ?狀態(tài)空間圖的大小 ?分支因子 b ?目標(biāo)節(jié)點(diǎn)的深度 d ?路徑的最大長度 m ?搜索深度限制 l 問題及其搜索過程的表示 ? 狀態(tài)空間 表示法 通過“ 狀態(tài) ”表示問題，通過“ 操作符 ”求解問題 狀態(tài)的改變 表示了問題求解過程 狀態(tài)空間 ? 以“狀態(tài)”和“操作符”為基礎(chǔ) 狀態(tài) ： 問題求解過程中任意時(shí)刻的狀況 操作符 ： 使問題從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作 ? 問題的全部狀態(tài) (包含初始狀態(tài)和目標(biāo)狀態(tài) )及一切可用操作符所構(gòu)成的集合稱為問題的狀態(tài)空間。在初始情況下， l號鋼針上穿有 A、 B兩個(gè)金片， A比 B小， A位于 B的上面。 ? 用 Sk=｛ Sk0， Sk1｝表示問題的 狀態(tài) ，其中，Sk0表示金片 A所在的鋼針號， Sk1表示金片 B所在的鋼針號。共有 12種操作，分別是： A(1， 3) A(2， 1) A(2， 3) A(3， 1) A(3， 2) B(1， 3) B(2， 1) B(2， 3) B(3， 1) B(3， 2) (1,1) (2,1) (2,3) (3,3) (1,3) (1,2) (2,2) (3,2) (3,1) A(1,3) B(1,2) A(3,2) ? 根據(jù)狀態(tài)和操作符，可構(gòu)成 二階梵塔問題的狀態(tài)圖 最短路徑解 ? 八數(shù)碼游戲（八數(shù)碼問題）描述為：在 3 3組成的九宮格棋盤上，擺有八個(gè)將牌，每一個(gè)將牌都刻有 18八個(gè)數(shù)碼中的某一個(gè)數(shù)碼。這種游戲求解的問題是：給定一種初始的將牌布局或結(jié)構(gòu)（稱初始狀態(tài)）和一個(gè)目標(biāo)的布局（稱目標(biāo)狀態(tài)），問如何移動(dòng)將牌，實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。 ? 基本思想 不存儲(chǔ)全部搜索圖，而是逐步展開問題求解所需的搜索子圖 ? 具體方法 從初始狀態(tài)開始，不斷擴(kuò)展當(dāng)前節(jié)點(diǎn)，即生成子節(jié)點(diǎn)，直到目標(biāo)狀態(tài)出現(xiàn)在這些子節(jié)點(diǎn)中，或者沒有可供擴(kuò)展的節(jié)點(diǎn)為止。可以使用的操作有： 空格左移，空格上移，空格右移，空格下移 尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。 ? (6)如果剛產(chǎn)生的這些后繼結(jié)點(diǎn)中存在一個(gè)目標(biāo)結(jié)點(diǎn)，則找到一個(gè)解。否則轉(zhuǎn) (2)繼續(xù)。并且廣度優(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)，依此向下搜索，直到某個(gè)子結(jié)點(diǎn)既不是目標(biāo)結(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟結(jié)點(diǎn)進(jì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)先搜索是一種不完備策略，即使問題有解，它也不一定能夠找到解。事實(shí)上，如果能利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程，則對搜索將是非常有益的。 ?啟發(fā)式搜索方法所依據(jù)的是問題自身的 啟發(fā)性信息 ，而啟發(fā)性信息又是通過 估價(jià)函數(shù) 而作用于搜索過程的 。 ? 啟發(fā)信息 可指導(dǎo)搜索過程，且與具體問題求解過程有關(guān)的控制性信息。 一般形式 為 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) S0的最優(yōu)路徑的估計(jì)代價(jià)。 估價(jià)函數(shù)例： f(n) = d(n) + W(n) 2 8 3 1 4 7 6 5 S0 節(jié)點(diǎn) n在搜索樹中的深度 n中“不在位”的數(shù)碼個(gè)數(shù) f(S0) = ? = 0 + 3 = 3 1 2 3 8 4 7 6 5 Sg ? 根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，分為全局擇優(yōu)搜索和局部擇優(yōu)搜索。 局部最佳優(yōu)先搜索算法 ? 對 OPEN表中所有節(jié)點(diǎn)的 f(n)進(jìn)行比較，按從小到大的順序重排 OPEN表。 開始 把 S放入 OPEN表，計(jì)算估價(jià)函數(shù) f (s) OPEN表為空表？ 把 OPEN表中的第一個(gè)節(jié)點(diǎn) n放入 CLOSED表 n為目標(biāo)節(jié)點(diǎn)嗎？ 擴(kuò)展 n，計(jì)算所有子節(jié)點(diǎn)的估價(jià)函數(shù)值，并提供它們返回節(jié)點(diǎn) n的指針。 ? 舉例： 八數(shù)碼魔方（ 8puzzle problem） 1 2 3 8 4 5 6 7 （目標(biāo)狀態(tài)） 1 2 3 8 4 5 6 7 （初始狀態(tài)） 5 7 ① ④ ⑤ ⑥ ③ 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (5) (5) ② 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (4) (3) (3) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (2) (4) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (4) 1 2 3 8 4 5 6 7 (1) 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 (0) (2) 八數(shù)碼魔方的局部最佳優(yōu)先搜索樹 1 2 3 8 4 6 (4) ⑦