【正文】 前載重量 static int bestw。 return； } //搜索子樹 if (cw+w[i]=c) { //搜索左子樹，即 cw += w[i]。 例 n=4, c1=12, w=[8,6,2,3] 具體算法描述如下： public static int maxLoading (int [] ww, int cc ) { //初始化類數(shù)據(jù)成員 n=。 } } 確定問題的解空間 子集樹問題： 裝載問題、 01背包問題、符號三角形問題、最大團(tuán)問題 排列樹問題： 批處理作業(yè)調(diào)度、 n后問題、旅行售貨員問題、圓排列問題、電路板排列問題 其他：圖的 m著色問題 找出適當(dāng)?shù)募糁瘮?shù) 約束函數(shù) 限界函數(shù) 以深度優(yōu)先的方式搜索解空間 遞歸回溯 迭代回溯 裝載問題 有一批共 n個集裝箱要裝上 2艘載重量分別為 c1和 c2的輪船，其中集裝箱 i的重量為 wi，且 211ccwnii ????裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這 2艘輪船。i++) { x[t]=i。 else t++。 } } 回溯法的算法實現(xiàn)： 迭代回溯 采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。 回溯法的算法實現(xiàn)： 遞歸回溯 回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。如果在當(dāng)前擴(kuò)展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點就成為 死結(jié)點 。 n=3時的 01背包問題用完全二叉樹表示的解空間 解空間樹的第 i層到第 i+1層邊上的標(biāo)號給出了變量的值。該解空間包含對變量的所有 01賦值。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。 例，對于有 n種可選擇物品的 01背包問題，其解空間由長度為 n的 01向量組成。典型的組織方法是圖或樹。這個新結(jié)點成為新的活結(jié)點，并成為當(dāng)前擴(kuò)展結(jié)點。 （用于求解最優(yōu)解時，例如旅行售貨員問題） 回溯法搜索解空間樹時，需要避免無效搜索，提高回溯法的搜索效率，通常采用兩種策略。bound(t)) backtrack(t+1)。bound(t)) { if (solution(t)) output(x)。i=1。 swap(x[t], x[i])。在某些情況下該算法優(yōu)于動態(tài)規(guī)劃算法。 } //回溯算法 private static void backtrack (int i) { //搜索第 i層結(jié)點 if (in) { // 到達(dá)葉結(jié)點 if (cwbestw) bestw=cw。 //第一艘輪船的載重量 static int cw。 } //回溯算法 private static void backtrack (int i) { //搜索第 i層結(jié)點 if (in) { // 到達(dá)葉結(jié)點 if (cwbestw) bestw=cw。 //剩余集裝箱重量 ?上界函數(shù) (不選擇當(dāng)前元素 )：當(dāng)前載重量 cw+剩余集裝箱的重量 r?當(dāng)前最優(yōu)載重量 bestw 構(gòu)造最優(yōu)解 為了不僅僅得到最優(yōu)裝載量，而且能得到與此最優(yōu)裝載量對應(yīng)的裝載方案，即需要構(gòu)造最優(yōu)解，則必須在算法中記錄與當(dāng)前最優(yōu)值相應(yīng)的當(dāng)前最優(yōu)解。 return bestw。 backtrack (i+1)。 批處理作業(yè)調(diào)度 40 給定 n個作業(yè)的集合 {J1,J2,…,J n}。 ?解空間：排列樹 void Flowshop::Backtrack(int i) { if (i n) { for (int j = 1。 f+=f2[i]。 int **M, // 各作業(yè)所需的處理時間 *x, // 當(dāng)前作業(yè)調(diào)度 *bestx, // 當(dāng)前最優(yōu)作業(yè)調(diào)度 *f2, // 機(jī)器 2完成處理時間 f1, // 機(jī)器 1完成處理時間 f, // 完成時間和 bestf, // 當(dāng)前最優(yōu)值 n。j++) if ((abs(kj)==abs(x[j]x[k]))||(x[j]==x[k])) return false。 好的約束函數(shù)能顯著地減少所生成的結(jié)點數(shù)。前者的效果明顯比后者好。 ?可行性約束函數(shù)：當(dāng)前符號三角形所包含的“ +”個數(shù)與“ ”個數(shù)均不超過 n*(n+1)/4 ?無解的判斷： n*(n+1)/2為奇數(shù)