【正文】 )( 3,2) ( 2,3 )( 2,2) ( 1,2) ( 1,3) ( 3,3)( 1) ( 1,1 )( 2) ( 3)15 河內(nèi)塔問(wèn)題形式化 ? 初始狀態(tài) ? 初始狀態(tài)向量 — 規(guī)定向量中各分量對(duì)應(yīng)所有n個(gè)盤(pán)子，位置上數(shù)字代表 3個(gè)柱子之一 ? 后繼函數(shù) ? 移動(dòng)規(guī)則 — 依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài) ? 目標(biāo)測(cè)試 ? 新向量是否是目標(biāo)狀態(tài) (也是向量形式 ) ? 路徑耗散函數(shù) ? 每移動(dòng)一個(gè)盤(pán)子的代價(jià)為 1 第 2章 搜索技術(shù) 16 河內(nèi)塔問(wèn)題求解 ? 求最短路徑問(wèn)題：狀態(tài)圖中從三角形 1個(gè)頂點(diǎn)走到另一個(gè)頂點(diǎn) ? 結(jié)論 ： (1)如果初始狀態(tài)或目標(biāo)狀態(tài)在三角形頂點(diǎn)上，則最短路徑唯一； (2)對(duì)于任意 2個(gè)狀態(tài)，最短求解路徑至多為 2條。 (中國(guó)某大學(xué)研究生證明 ) ? 求解過(guò)程 — 對(duì)狀態(tài)空間的搜索 — 以 2階河內(nèi)塔為例 第 2章 搜索技術(shù) 17 河內(nèi)塔問(wèn)題的搜索樹(shù) 第 2章 搜索技術(shù) 1,1 2,1 3,1 1,1 2,3 1,1 3,2 3,3 2,1 2,2 √ 3,1 2,2 1,3 2,1 3,3 2,3 3,3 1,2 1,1 √ 2,2 1,2 3,1 3,3 √ 2,2 3,2 1,3 1,1 √ 18 求解過(guò)程 — 樹(shù)搜索 ? 求解問(wèn)題的過(guò)程使用搜索樹(shù)形式 ? 每個(gè)狀態(tài)對(duì)應(yīng) 搜索樹(shù)中一個(gè)節(jié)點(diǎn) ? 根節(jié)點(diǎn)對(duì)應(yīng)于初始狀態(tài) ? 每次從搜索樹(shù)的上層節(jié)點(diǎn)出發(fā)，根據(jù)約束條件進(jìn)入下一個(gè)可能的狀態(tài)，即展開(kāi)新的一層樹(shù)節(jié)點(diǎn) —節(jié)點(diǎn)擴(kuò)展 ? 節(jié)點(diǎn)展開(kāi)的順序即代表了不同的搜索策略 ? 當(dāng)展開(kāi)的節(jié)點(diǎn)為目標(biāo)狀態(tài)時(shí)，就找到了問(wèn)題的一個(gè)解 第 2章 搜索技術(shù) 19 搜索策略 ? 研究搜索過(guò)程考慮的若干問(wèn)題 (1)有限搜索還是無(wú)限搜索 (2)已知目標(biāo)還是未知目標(biāo) (3)目標(biāo)或目標(biāo) +路徑 (4)有約束還是無(wú)約束 (5)數(shù)據(jù)驅(qū)動(dòng) (向前搜索 )還是目標(biāo)驅(qū)動(dòng) (6)單向搜索還是雙向搜索 第 2章 搜索技術(shù) 20 搜索的分類 ? 搜索過(guò)程的分類：狀態(tài)空間搜索 (圖搜索方式 )，問(wèn)題空間搜索 (層次方法 )，博弈空間搜索 ? 無(wú)信息搜索與啟發(fā)式搜索 ? 啟發(fā)式：利用中間信息改進(jìn)控制策略 ? 啟發(fā)式： (1)任何有助于找到問(wèn)題的解，但不能保證找到解的方法是啟發(fā)式方法 ? (2)有助于加速求解過(guò)程和找到較優(yōu)解的方法是啟發(fā)式方法 ? 啟發(fā)式也叫啟發(fā)函數(shù) 第 2章 搜索技術(shù) 21 搜索算法的性能 ? 4種途徑來(lái)評(píng)價(jià)搜索算法的性能 ? 完備性 — 當(dāng)問(wèn)題有解時(shí) ， 算法是否保證找到一個(gè)解 ? 最優(yōu)性 — 算法是否能找到一個(gè)最優(yōu)解 (路徑耗散函數(shù)值最小的路徑 ) ? 時(shí)間復(fù)雜性 — 找到一個(gè)解需要花費(fèi)多少時(shí)間 ? 空間復(fù)雜性 — 在搜索過(guò)程中需要占用多少內(nèi)存 第 2章 搜索技術(shù) 22 性能量度 ? 時(shí)空復(fù)雜性的量度 — 由狀態(tài)空間圖的大小來(lái)衡量 / 相關(guān)度量如下： ? 分支因子 b (每次展開(kāi)的平均節(jié)點(diǎn)個(gè)數(shù) ) ? 目標(biāo)節(jié)點(diǎn)的深度 d ? 路徑的最大長(zhǎng)度 m ? 搜索深度限制 l ? 搜索耗散 第 2章 搜索技術(shù) 23 無(wú)信息搜索策略 廣度優(yōu)先搜索 深度優(yōu)先搜索和深度有限搜索 疊代深入深度優(yōu)先搜索 無(wú)信息搜索策略性能比較 圖搜索算法 第 2章 搜索技術(shù) 24 盲目搜索策略 ? 無(wú)信息搜索也稱盲目搜索：沒(méi)有任何附加信息，只有生成后繼和區(qū)分目標(biāo)與非目標(biāo)狀態(tài) ? 有 5種盲目搜索策略 ? 廣度優(yōu)先搜索 ? 代價(jià)一致搜索 ? 深度優(yōu)先搜索 ? 深度有限搜索 ? 迭代深入深度優(yōu)先搜索 第 2章 搜索技術(shù) 25 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索過(guò)程： ? 首先擴(kuò)展根節(jié)點(diǎn) ? 接著擴(kuò)展根節(jié)點(diǎn)的所有后繼節(jié)點(diǎn) ? 然后再擴(kuò)展后繼節(jié)點(diǎn)的后繼，依此類推 ? 在下一層任何節(jié)點(diǎn)擴(kuò)展之前搜索樹(shù)上的本層深度的所有節(jié)點(diǎn)都已經(jīng)被擴(kuò)展 ? 廣度優(yōu)先搜索可以調(diào)用樹(shù)搜索算法 (TreeSearch)實(shí)現(xiàn) ? 其參數(shù) fringe(邊緣 /擴(kuò)展分支 )為先進(jìn)先出隊(duì)列 FIFO 第 2章 搜索技術(shù) 26 樹(shù)搜索算法 (1) function TreeSearch(problem,fringe) return solution /failure (initial fringe=empty, mode=FIFO) fringe← Insert(MakeNode(InitialState[problem]),fringe) do while(1) if fringe=Empty then return failure node← RemoveFirst(fringe) if State[node]=Goal then return Solution(node) fringe← InsertAll(Expend(node,problem), fringe) 第 2章 搜索技術(shù) 27 樹(shù)搜索算法 (2) ? 關(guān)鍵在于如何擴(kuò)展節(jié)點(diǎn) function Expend(node,problem) return set of nodes successors← the empty set for each action,result in SuccessorFind[problem] (State[node]) do s← new Node / State[s]← result ParentNode[s]=node / Action[s]=action PathCost[s]=PathCost[node]+StepCost[node, action,s] Depth[s]← Depth[node]+1 add s to successors return successors 第 2章 搜索技術(shù) 28 廣度優(yōu)先搜索的性能 ? 在上述算法中，廣度優(yōu)先搜索以 TreeSearch(problem,FIFOQueue)調(diào)用樹(shù)搜索算法 ? 從 4種度量來(lái)評(píng)價(jià)廣度優(yōu)先搜索： ? 完備性 —總能找到一個(gè)解 ? 如果每步擴(kuò)展的耗散相同時(shí)，廣度優(yōu)先搜索能找到最優(yōu)解 ? 內(nèi)存消耗是比執(zhí)行時(shí)間消耗更大的問(wèn)題 ? 指數(shù)級(jí)的時(shí)間消耗 (空間和時(shí)間消耗的例子參見(jiàn) p60圖 ) 第 2章 搜索技術(shù) 29 深度優(yōu)先搜索和深度有限搜索 ? 深度優(yōu)先搜索過(guò)程： ? 總是擴(kuò)展搜索樹(shù)的當(dāng)前擴(kuò)展分支 (邊緣 )中最深的節(jié)點(diǎn) ? 搜索直接伸展到搜索樹(shù)的最深層，直到那里的節(jié)點(diǎn)沒(méi)有后繼節(jié)點(diǎn) ? 那些沒(méi)有后繼節(jié)點(diǎn)的節(jié)點(diǎn)擴(kuò)展完畢就從邊緣中去掉 ? 然 后搜索算法回退下一個(gè)還有未擴(kuò)展后繼節(jié)點(diǎn)的上層節(jié)點(diǎn)繼續(xù)擴(kuò)展 ? 搜索算法參見(jiàn)深度有限搜索算法 (l=∞ ) 第 2章 搜索技術(shù) 30 深度優(yōu)先搜索的性能 ? 深度優(yōu)先搜索通過(guò)后進(jìn)先出隊(duì)列 LIFO(棧 )調(diào)用 TreeSearch實(shí)現(xiàn) / 通常使用遞歸函數(shù)實(shí)現(xiàn)，依次對(duì)當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)調(diào)用該函數(shù) ? 性能： ? 內(nèi)存需求少 —如分支因子 =b/最大深度 =m的狀態(tài)空間深度優(yōu)先搜索只需要存儲(chǔ) bm+1個(gè)節(jié)點(diǎn) (比較廣度優(yōu)先 O(bd+1)) ? 不是完備的 / 不是最優(yōu)的 ? 最壞情況下時(shí)間復(fù)雜性也很高 O(bm) 第 2章 搜索技術(shù) 31 深度有限搜索 ? 深度優(yōu)先搜索的無(wú)邊界問(wèn)題可以通過(guò)提供一個(gè)預(yù)先設(shè)定的深度限制 l來(lái)解決 ? 深度 =l的節(jié)點(diǎn)當(dāng)作無(wú)后繼節(jié)點(diǎn)看待 ? 雖然解決了無(wú)限路徑問(wèn)題，但如果 ld則找不到解 ? 如果選擇 dl則深度優(yōu)先搜索也不是最優(yōu)的 ? 時(shí)間復(fù)雜度 O(bl) ? 空間復(fù)雜度 O(bl) ? 深度優(yōu)先搜索可看作是一種特例即 l=∞ 第 2章 搜索技術(shù) 32 非遞歸的深度有限搜索算法 function DepthLimitedSearch(problem,fringe,limit) return solution/failure/cutoff fringe← Insert(MakeNode(Init