算法優(yōu)化策略ppt課件-資料下載頁
2025-04-29 02:45本頁面
【正文】 nt step) {// 解最短加法鏈問題的標準回溯法 int i,j,k。 if (a[step]==n) // 找到一條加法鏈 { if (stepbest) 更新最優(yōu)值 return。 } // 對當前結點 a[step]的每一個兒子結點遞歸搜索 for (i=step。i=1。i) if (2*a[i]a[step]) for (j=i。j=1。j){ k=a[i]+a[j]。 a[step+1]=k。 if ((ka[step])amp。amp。(k=n)) backtrack(step+1)。 } } 由于加法鏈問題的狀態(tài)空間樹的每一個第 k層結點至少有 k+1個兒子結點，因此從根結點到第 k層的任一結點的路徑數至少是 k!。用標準的回溯法只能對較小的構造出最短加法鏈。 26 迭代搜索法 ?深度優(yōu)先搜索 : 算法所搜索到的第一個加法鏈不一定是最短加法鏈。 ?廣度優(yōu)先搜索 : 算法找到的第一個加法鏈就是最短加法鏈，但這種方法的空間開銷太大。 ?迭代搜索算法 : 既能保證算法找到的第一個加法鏈就是最短加法鏈，又不需要太大的空間開銷。其基本思想是控制回溯法的搜索深度 d，從 d=1開始搜索，每次搜索后使 d增 1，加深搜索深度，直到找到一條加法鏈為止。 private static void iterativeDeepening() {// 逐步深化的迭代搜索算法 best=n+1。 found=false。 lb=2。 // 初始迭代搜索深度 while (!found){ a[1]=1。 backtrack(1)。 lb++。 // 加深搜索深度 } } 對于正整數，記 ?(n)=?logn?，v(n)=n的 2進制表示中 1的個數。迄今為止所知道的 l(n)的最好下界是 l(n)≥lb(n)= ?(n)+?logv(n)?。利用這個下界，可以從深度 lb(n)開始搜索，大大加快了算法的搜索進程。 27 剪枝函數 ?設 ai和 aj是加法鏈中的兩個元素，且 ai2maj。由于加倍是加法鏈中元素增大的最快的方式，即 ai?2ai1，所以從 aj到 ai至少需要m+1步。如果預期在狀態(tài)空間樹 T的第 d層找到關于 n的一條加法鏈，則以狀態(tài)空間樹第 i層結點 ai為根的子樹中，可在第 d層找到一條加法鏈的必要條件是 2diai≥n。 ?當 時，狀態(tài)空間樹中以結點 ai為根的子樹中不可能在第 d層之前找到最短加法鏈。 ?設在求正整數 n的最短加法鏈的逐步深化迭代搜索算法中，當前搜索深度為 d。且正整數可表示為 n=2t(2k+1)， k0，則在狀態(tài)空間樹的第 i層結點 ai處的一個剪枝條件是 na iid ?? ?? )2(23? ?? ? ditdtdidiandianii??????????? ?????120/l o g23/l o g28 最短加法鏈長的上界 與加法鏈問題密切相關的冪樹給出了 l(n)的更精確的上界。 假設已定義了冪樹 T的第 k層結點，則 T的第 k+1層結點可定義如下。依從左到右順序取第 k層結點 ak，定義其按從左到右順序排列的兒子結點為 ak+aj， 0?j?k。其中 a0,a1,…,ak ，是從 T的根到結點 ak的路徑。且 ak+aj在 T中未出現(xiàn)過。 含正整數 n的部分冪樹 T容易在線性時間內用迭代搜索方式構造出來。 29 優(yōu)化算法 綜合前面的討論，對構造最短加法鏈的標準回溯法作如下改進。 (1)采用逐步深化迭代搜索策略； (2)利用 l(n)的下界 lb(n)對迭代深度作精確估計； (3)采用剪枝函數對問題的狀態(tài)空間樹進行剪枝搜索，加速搜索進程； (4)用冪樹構造 l(n)的精確上界 ub(n)。 當 lb(n)=ub(n)時，冪樹給出的加法鏈已是最短加法鏈。 當 lb(n)ub(n)時，用改進后的逐步深化迭代搜索算法，從深度 d=lb(n)開始搜索。
教學課件相關推薦
鄂ICP備17016276號-1