【正文】 D:變域的集合 。 k := k + 1。 conflicts := pute_conflicts(Xk+1)。/* search*/k:=0。 X0=select_aninitial_point()。 L:文字的集合 。 until no collisions。 ) Queens Number of solutions Time(seds) 12 14200 1 13 73712 4 14 365596 28 15 2279184 138 16 14772512 993 Nqueen問題的求解Fuction queen_search(queen:array[1..n] of integer)Begin repeart Generate a random solution for queens。 To Step2 否則 ,輸出 x, 停止搜索 .被用于大規(guī)模 Nqueen, SAT等問題的求解 .局部搜索法初始解 x0x3x4x1x2x5N(x0)N(x1)N(x5)局部搜索法的特征1. 局部搜索的要素? 評價函數(shù)的確定? 初始解的確定? N(x)的確定? 解更新的方法? 終止條件2. 特點：簡單 ,高效 ,但不完備 局部最優(yōu)解3. 改進方法 :多起點、加入非確定性、4. 加入從局部最優(yōu)解脫出的方法Nqueen問題的求解 Nqueen問題的求解(皇后 N,方案數(shù) ):(4,2) (5,10) ( 6,4) (7,40) ( 8,92) ( 9,352) (10,724) Nqueen問題的求解最快的 N皇后問題 C Program ：傳統(tǒng)的遞歸算法，但使用了 C的位操作 以極大地提高了運行速度。n 搜索空間指數(shù)增長 ,只能前推幾步 n 極大極小過程n 剪枝技術(shù) (7,min) (6,1,max) (5,2,max) (4,3,max)(5,1,1,min) (4,2,1min) (3,2,2,min) (3,3,1,min) (4,1,1,1,max) (3,2,1,1,mix) (2,2,2,1,max) max 失敗 (3,1,1,1,1,min) (2,2,1,1,1,min) min失敗 (2,1,1,1,1,1,max) max失敗分幣原則 :每次要將一堆分為幣數(shù)不等的兩堆 . 勝負標準 :交替分錢幣 ,誰不能再分誰輸 .分錢幣游戲的博弈樹結(jié)論 : ? (7,min) (6,1,max) (5,2,max) (4,3,max)(5,1,1,min) (4,2,1min) (3,2,2,min) (3,3,1,min) (4,1,1,1,max) (3,2,1,1,max) (2,2,2,1,max) max失敗 (3,1,1,1,1,min) (2,2,1,1,1,min) min失敗 (2,1,1,1,1,1,max) max失敗 . max 可解節(jié)點 min可解節(jié)點分錢幣游戲的博弈樹結(jié)論 : max必勝 n 錢幣為 8， 9時，結(jié)論如何？n 錢幣為 10 時，結(jié)論如何？n 錢幣為 x 時，結(jié)論如何？分錢幣游戲思考題極大極小過程BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 2 5 7 1 1 R2 522215倒推過程αβ 剪枝技術(shù)BAIHGFCQPONMLKIEDMAXMIN 2 8 1 3 2 5 7 R2 5≤ 1MAX節(jié)點的下界 α≥ 2MIN節(jié)點的上界 β ≤ 2≥ 5α剪枝β剪枝αβ 剪枝技術(shù)n MAX節(jié)點的 倒退值 α : 取后繼節(jié)點估值的 最大值 . MAX節(jié)點的 倒推下界值 .n MIN節(jié)點的 倒退值 β : 取后繼節(jié)估值點的 最小值 . MIN節(jié)點的 倒推上界值 .n α 剪枝 : 當 MIN節(jié)點的 β 值 ≤ 祖先 MAX節(jié)點的 α 值時 ,不必展開 MIN的其余子節(jié)點 . n β 剪枝 : 當 MAX節(jié)點的 α 值 ≥ 祖先 MIN節(jié)點的 β 值時 ,不必展開 MAX的其余子節(jié)點 . 討論n 局部優(yōu)先搜索與全局優(yōu)先搜索的區(qū)別是什么 ?n 什么是啟發(fā)式搜索？ A算法？ A*算法？n 博弈樹有什么特點 ?n 利用博弈樹分析九枚分錢幣游戲的可能結(jié)論 ? 局部搜索 (Local Search)*通過在當前解近旁的搜索 ,不斷改善當前解 ,最終搜索到滿足要求的最優(yōu)解或次優(yōu)解 .一般過程Step1: 初始化 . 求初始解 x0=當前解 x, k=1。 P:本原問題 集合O:操作算子集 。n 設評價函數(shù)為 f(N) =g(N) + h(N), 怎樣才能保證搜索到最優(yōu)解？ 設 f12(N) =K1 g(N) + K2 h(N)，討論 K1 ,K2對搜索結(jié)果的影響？n 如何進一步提高搜索效率？（雙向、多起點、非確定…)八數(shù)碼難題（ 8puzzle problem） 用 A*算法搜索，給出搜索樹。n 刪除重復節(jié)點和修改返回指針處理 .八數(shù)碼難題 :n h1(T) ? 0 啟發(fā)函數(shù)為 0注意注意 : h3(T) ? h2(T) ? h1(T) h2 = 41 3 247658n h2(T) =沒有處在目標狀態(tài)的字碼數(shù)目h3 = 1 + 1 + 2 + 2 = 61 3 247658n h3(T) =不在目標位置的字碼距離目標位置水平距離和垂直距離之和。n Step4: 若目標節(jié)點 Sg=N, 則搜索成功 ,結(jié)束 .n Step5: 若 N不可擴展 , 則轉(zhuǎn) Step2。n 4)： h(n)=h*(n)為什么 A*算法低估 h值n 在 A*算法中，對所有的 x存在 h(x)≤h*(x)（ 低估 )n 在 A*算法中 ,只有對 h值低估才能獲得優(yōu)化的搜索性能為什么 A*算法低估 h值n 舉例：SADFBEHCGI11 111111111紅色值表示紅色值表示真實的真實的剩余代價剩余代價3 2 12 13 2 13 2 15443 2多估多估n 在多估情況下：SADF1+31+51+4B2+2C3+1G 4并不是優(yōu)化路徑并不是優(yōu)化路徑 !為什么 A*算法低估 h值n 舉例：3 2SADFBEHCGI11 111111111 322111紅色值表示紅色值表示真實的真實的剩余代價剩余代價n 如果 h被低估 :SADF1+11+21+31 0 02312 1低估低估B2+0C3+0G 4E 3 !2+1f1f2f3f4A*A*算法沿算法沿 f函數(shù)進行擴展函數(shù)進行擴展啟發(fā)式搜索算法 A*n Step1: 把初始節(jié)點 S0放入 OPEN表中 。n 2) 問題域是有限的。n 定義 3 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。 稱此時的 A算法為 A*算法 .n A*算法的特征 :n A*是可采納的 :只要最短路徑存在 ,就一定能找出 .n 如果有 h1(n) = h2(n) = h*(n), 那么 h2比 h1展開更少的節(jié)點 .n 廣度優(yōu)先搜索是當 h(n)=0時的 A*算法的特例 . 啟發(fā)式搜索 :A*算法n 評價函數(shù) f(x) = g(x) + h(x) ( 當 h(n) = h*(n) )nSGg(n)=g*(n)h(n) = h*(n) A*算法要求保守估計： f(n) = f*(n)A*算法的定義n 定義 1 在圖搜索過程中，如果重排 OPEN表是依據(jù) f(x)=g(x)+h(x)進行的，則稱該過程為 A算法 。 初始棋局初始棋局 f值等于值等于 0+4=4 12 384567（初始狀態(tài)）57234512 38456712 38456712 3845671+31+5 1+5112 38 456712 38456712 3845672+42+3 2+312 38 456712 38 45673+2 3+412 38 4567123845673+3 3+41 2 38 45674+181 3245671 2 38 45675+0 5+2八數(shù)碼難題的搜索樹12 38