【正文】 同的符號(hào)三角形，使其所含的 “ +”和 “ ”的個(gè)數(shù)相同。 2個(gè)同號(hào)下面都是 “ +”， 2個(gè)異號(hào)下面都是 “ ”。 // 當(dāng)前最優(yōu)作業(yè)調(diào)度 static int [] f2。 // 各作業(yè)所需的處理時(shí)間 static int [] x。 } } public class FlowShop static int n, // 作業(yè)數(shù) f1, // 機(jī)器 1完成處理時(shí)間 f, // 完成時(shí)間和 bestf。 } f1=m[x[j]][1]。 backtrack(i+1)。 f+=f2[i]。 j++) { f1+=m[x[j]][1]。 } else for (int j = i。 j++) bestx[j] = x[j]。 12 批處理作業(yè)調(diào)度 ?解空間：排列樹(shù) private static void backtrack(int i) { if (i n) { for (int j = 1。 jittji 機(jī)器 1 機(jī)器 2 作業(yè) 1 2 1 作業(yè) 2 3 1 作業(yè) 3 2 3 這 3個(gè)作業(yè)的 6種可能的調(diào)度方案是 1,2,3； 1,3,2； 2,1,3； 2,3,1；3,1,2； 3,2,1；它們所相應(yīng)的完成時(shí)間和分別是 19， 18， 20，21， 19， 19。所有作業(yè)在機(jī)器 2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。作業(yè) Ji需要機(jī)器 j的處理時(shí)間為 tji。 } 11 批處理作業(yè)調(diào)度 給定 n個(gè)作業(yè)的集合 {J1,J2,…,J n}。 // 搜索右子樹(shù) backtrack(i + 1)。 cw = w[i]。 cw += w[i]。 r = w[i]。 10 裝載問(wèn)題 ?解空間：子集樹(shù) ?可行性約束函數(shù) (選擇當(dāng)前元素 )： ?上界函數(shù) (不選擇當(dāng)前元素 )： 當(dāng)前載重量 cw+剩余集裝箱的重量 r?當(dāng)前最優(yōu)載重量 bestw 11cxwniii ???private static void backtrack (int i) {// 搜索第 i層結(jié)點(diǎn) if (i n) // 到達(dá)葉結(jié)點(diǎn) 更新最優(yōu)解 bestx,bestw。 nixcxwxwiniiiniii????????1},1,0{s .t .m a x111 用回溯法設(shè)計(jì)解裝載問(wèn)題的 O(2n)計(jì)算時(shí)間算法。 將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近。 容易證明，如果一個(gè)給定裝載問(wèn)題有解，則采用下面的策略可得到最優(yōu)裝載方案。 } } 9 裝載問(wèn)題 有一批共 n個(gè)集裝箱要裝上 2艘載重量分別為 c1和 c2的輪船，其中集裝箱 i的重量為 wi，且 211ccwnii ????裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這 2艘輪船。 if (legal(t)) backtrack(t+1)。i=n。 } } void backtrack (int t) { if (tn) output(x)。i++) { x[t]=i。 else for (int i=0。} } else t。bound(t)) { if (solution(t)) output(x)。 if (constraint(t)amp。i=g(n,t)。 void iterativeBacktrack () { int t=1。bound(t)) backtrack(t+1)。 if (constraint(t)amp。i=g(n,t)。 void backtrack (int t) { if (tn) output(x)。而顯式地存儲(chǔ)整個(gè)解空間則需要 O(2h(n))或 O(h(n)!)內(nèi)存空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。 常用剪枝函數(shù)： 用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹(shù)； 用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。在完成對(duì)子樹(shù) C（以 C為根的子樹(shù)）的窮盡搜索之后，將 R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成 R的下一個(gè)兒子（如果存在） ? 寬度優(yōu)先的問(wèn)題狀態(tài)生成法：在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn) ? 回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問(wèn)題狀態(tài)，要不斷地利用限界函數(shù) (bounding function)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。 注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡(jiǎn)單）。 ? 隱約束：為滿足問(wèn)題的解而對(duì)不同分量之間施加的約束。 3 問(wèn)題的解空間 ? 問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè) n元式 (x1,x2,… ,xn)的形式。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。1 第 5章 回溯法 2 回溯法 ? 有許多問(wèn)題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。 ? 回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。 ? 顯約束：對(duì)分量 xi的取值限定。 ? 解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。 n=3時(shí)的 01背包問(wèn)題用完全二叉樹(shù)表示的解空間 4 生成問(wèn)題狀態(tài)的基本方法 ? 擴(kuò)展結(jié)點(diǎn) :一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn) ? 活結(jié)點(diǎn) :一個(gè)自身已生成但其兒子還沒(méi)有全部生成的節(jié)點(diǎn)稱做活結(jié)點(diǎn) ? 死結(jié)點(diǎn) :一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)點(diǎn) ? 深度優(yōu)先的問(wèn)題狀態(tài)生成法：如果對(duì)一個(gè)擴(kuò)展結(jié)點(diǎn) R，一旦產(chǎn)生了它的一個(gè)兒子 C，就把 C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。 具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法 5 回溯法的基本思想 (1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間； (2)確定易于搜索的解空間結(jié)構(gòu)； (3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。 用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。如果解空間樹(shù)中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為 O(h(n))。 6 遞歸回溯 回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)回溯法。 else for (int i=f(n,t)。i++) { x[t]=h(i)。amp。 } } 7 迭代回溯 采用樹(shù)的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過(guò)程。 while (t0) { if (f(n,t)=g(n,t)) for (int i=f(