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