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