【正文】 前者的效果明顯比后者好。j++) if ((abs(kj)==abs(x[j]x[k]))||(x[j]==x[k])) return false。 f+=f2[i]。 批處理作業(yè)調(diào)度 40 給定 n個作業(yè)的集合 {J1,J2,…,J n}。 return bestw。 } //回溯算法 private static void backtrack (int i) { //搜索第 i層結(jié)點 if (in) { // 到達葉結(jié)點 if (cwbestw) bestw=cw。 } //回溯算法 private static void backtrack (int i) { //搜索第 i層結(jié)點 if (in) { // 到達葉結(jié)點 if (cwbestw) bestw=cw。 swap(x[t], x[i])。bound(t)) { if (solution(t)) output(x)。 （用于求解最優(yōu)解時，例如旅行售貨員問題） 回溯法搜索解空間樹時，需要避免無效搜索，提高回溯法的搜索效率，通常采用兩種策略。典型的組織方法是圖或樹。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。該解空間包含對變量的所有 01賦值。如果在當(dāng)前擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為 死結(jié)點 。 } } 回溯法的算法實現(xiàn)： 迭代回溯 采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。i++) { x[t]=i。 例 n=4, c1=12, w=[8,6,2,3] 具體算法描述如下： public static int maxLoading (int [] ww, int cc ) { //初始化類數(shù)據(jù)成員 n=。 //當(dāng)前載重量 static int bestw。在類 Loading中增加兩個私有數(shù)據(jù)成員 x和 bestx: x用于記錄從根至當(dāng)前結(jié)點的路徑， bestx記錄當(dāng)前最優(yōu)解。 cw = w[i]。 j = n。 // 作業(yè)數(shù) }。但這樣的約束函數(shù)往往計算量較大。 為了便于運算，設(shè) + 為 0， 為 1，這樣可以使用異或運算符表示符號三角形的關(guān)系 ++為 +即 0^0=0, 為 +即 1^1=0, +為 即 0^1=1, +為 即 1^0=1。 } } 影響回溯算法效率的因素 通過前面具體實例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素： (1)產(chǎn)生 x[k]的時間； (2)滿足顯約束的 x[k]值的個數(shù)； (3)計算約束函數(shù) constraint的時間； (4)計算上界函數(shù) bound的時間； (5)滿足約束函數(shù)和上界函數(shù)約束的所有 x[k]的個數(shù)。 private: void Backtrack(int i)。易見，最佳調(diào)度方案是 1,3,2，其完成時間和為18。 cw += w[i]。 } } public class Loading { static int r。 //集裝箱重量數(shù)組 static int c。 nixcxwxwiniiiniii????????1},1,0{s . t .m ax111用回溯法設(shè)計解裝載問題的 O(2n)計算時間算法。 else for (int i=0。amp。在當(dāng)前擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。問題的解空間應(yīng)至少包含問題的一個 (最優(yōu) )解。 ? 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。從樹根到葉的任一路徑表示解空間中的一個元素。 void backtrack (int t) { if (tn) output(x)。} } else t。如果有，找出一種裝載方案。 backtrack (i+1)。 if (cw+w[i]=c) { //搜索左子樹 cw += w[i]。 j=n。作業(yè) Ji需要機器 j的處理時間為 tji。 Backtrack(i+1)。 } void Queen::Backtrack(int t) { if (tn) sum++。 2個同號下面都是 “ +”， 2個異號下面都是 “ ”。 圖 (a)中，從第 1層剪去 1棵子樹，則從所有應(yīng)當(dāng)考慮的 3元組中一次消去 12個 3元組。 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Q Q Q Q Q Q Q Q ?解向量： (x1, x2, … , x n) ?顯約束： xi=1,2, … ,n