太原工業(yè)學(xué)院算法設(shè)計(jì)與分析-第5章-回溯法教學(xué)課件

1、第5章 回溯法5.1 回溯法的算法框架5.2 裝載問題5.3 批處理作業(yè)調(diào)度5.4 符號(hào)三角形問題5.5 n后問題5.6 0-1背包問題5.7 最大團(tuán)問題5.8 圖的m著色問題5.9 旅行售貨員問題5.10 圓排列問題5.11 電路板排列問題5.12 連續(xù)郵資問題5.13 回溯法的效率分析例如：走迷宮用計(jì)算機(jī)求解問題問題空間現(xiàn)實(shí)求解過程實(shí)際解狀態(tài)空間對(duì)象的定義機(jī)器求解過程算法與程序的設(shè)計(jì)機(jī)內(nèi)解計(jì)算機(jī)求解的過程在狀態(tài)空間尋找機(jī)內(nèi)解, 可以看成是從初始狀態(tài)出發(fā),搜索目標(biāo)狀態(tài)(解所在的狀態(tài))的過程。狀態(tài)空間初始狀態(tài)目標(biāo)狀態(tài)搜索搜索的過程可描述為：S0S1Sn，其中S0為初態(tài)，Sn為終態(tài)?；蛘哒f(S0

2、)且(Sn)，這里稱為初始條件，稱為終止條件。求解是狀態(tài)空間的搜索求解的過程可以描述為對(duì)狀態(tài)空間的搜索S0S11S12S1k Sn1SniSnm其中S0為初始狀態(tài)，不妨設(shè)Sni為終止?fàn)顟B(tài)S0Sni問題求解就是通過搜索，尋找出一條從初始狀態(tài)S0到終止?fàn)顟B(tài)Sni的路徑。幾種搜索方法狀態(tài)空間的搜索實(shí)際上是一種樹/DAG（Directed Acyclic Graph ）的搜索，常用的方法有：廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索從初始狀態(tài)開始，逐層地進(jìn)行搜索。從初始狀態(tài)開始，逐個(gè)分枝地進(jìn)行搜索。從初始狀態(tài)開始，每次選擇最有可能達(dá)到終止?fàn)顟B(tài)的結(jié)點(diǎn)進(jìn)行搜索。三種搜索的優(yōu)劣之處一般來說，三種搜索方法各有優(yōu)劣之處

3、：廣度優(yōu)先搜索和深度優(yōu)先搜索優(yōu)點(diǎn)：一定能找到解；缺點(diǎn)：時(shí)間復(fù)雜性大。啟發(fā)式搜索優(yōu)點(diǎn)：一般來說能較快地找到解，即其時(shí)間復(fù)雜性小；缺點(diǎn)：需要設(shè)計(jì)一個(gè)評(píng)價(jià)函數(shù)，并且評(píng)價(jià)函數(shù)的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣。當(dāng)需要找出問題的解集，或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉鳎蚴且环N組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。在問題的解空間樹中，回溯法按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹?；厮莘ㄋ惴ㄋ阉髦两饪臻g樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖

4、先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。5.1 回溯法的算法框架5.1.1 問題的解空間應(yīng)用回溯法解問題時(shí)，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個(gè)(最優(yōu))解。通常將解空間組織成樹或圖的形式。問題的解向量：回溯法希望一個(gè)問題的解，能夠表示成一個(gè)n元式(x1,x2,xn)的形式。顯約束：對(duì)分量xi的取值限定隱約束：為滿足問題的解，而對(duì)不同分量間施加的約束。解空間：對(duì)于問題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。例如，對(duì)于有n種可選物品的0-1背包問題，其解空間由長度為n的0-1向量組成。n=3時(shí)的0-1背包問題用完全二叉樹表示的

5、解空間5.1.2 回溯法的基本思想基本概念：擴(kuò)展結(jié)點(diǎn)：一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)活結(jié)點(diǎn)：一個(gè)自身已生成但其兒子還沒有全部生成的節(jié)點(diǎn)死結(jié)點(diǎn)：一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)深度優(yōu)先的問題狀態(tài)生成法：如果對(duì)一個(gè)擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個(gè)兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對(duì)子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個(gè)兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)。回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的

6、計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法?；舅枷耄捍_定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。 示例1 0-1背包問題n=3, C=30, w=16,

7、 15, 15, v=45, 25, 25開始時(shí)，Cr=C=30，V=0，A為唯一活結(jié)點(diǎn)，也是當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展A，先到達(dá)B結(jié)點(diǎn)Cr=Cr-w1=14，V=V+v1=45此時(shí)A、B為活結(jié)點(diǎn)，B成為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展B，先到達(dá)DCrw2，D導(dǎo)致一個(gè)不可行解，回溯到B再擴(kuò)展B到達(dá)EE可行，此時(shí)A、B、E是活結(jié)點(diǎn)，E成為新的擴(kuò)展結(jié)點(diǎn)擴(kuò)展E，先到達(dá)JCr45，皆得到一個(gè)可行解x=(0,1,1)，V=50L不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到F再擴(kuò)展F到達(dá)MM是葉結(jié)點(diǎn)，且2550，不是最優(yōu)解M不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到FF沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到C再擴(kuò)展C到達(dá)GCr=30，V=0，活結(jié)點(diǎn)為A、C、G，G

8、為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展G，先到達(dá)N，N是葉結(jié)點(diǎn)，且2550，不是最優(yōu)解，又N不可擴(kuò)展，返回到G再擴(kuò)展G到達(dá)O，O是葉結(jié)點(diǎn)，且050，不是最優(yōu)解，又O不可擴(kuò)展，返回到GG沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到CC沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到AA沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，算法結(jié)束，最優(yōu)解X=(0,1,1)，最優(yōu)值V=50ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45CCr=30，V=0DCrw2不可行解JCr45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M25n) output(x);/ tn時(shí)已搜索到一個(gè)葉結(jié)點(diǎn), output(x)對(duì)得到 的可行解x進(jìn)行

9、記錄或輸出處理. else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t); in) output(x); else for (int i=0;in) output(x); else for (int i=t;in)/到達(dá)葉結(jié)點(diǎn) if(cwbestw) bestw=cw; return; /搜索子樹 if(cw+wi=c) /搜索左子樹，即xi=1 cw+=wi; backtrack(i+1); cw-=wi; backtrack(i+1);/搜索右子樹3. 上界函數(shù)可對(duì)上面的算法引入上界函數(shù)，減去不含最優(yōu)解的子樹?？扇∩辖绾?/p>

10、數(shù)為：cw+rbestwcw：當(dāng)前載重量bestw：當(dāng)前最優(yōu)載重量r：剩余集裝箱重量，即這樣算法可寫為：程序代碼：public class Loading static int n; /集裝箱數(shù) static int w; /集裝箱重量數(shù)組 static int c; /第一艘輪船的載重量 static int cw; /當(dāng)前載重量 static int bestw; /當(dāng)前最優(yōu)載重量 static int r; /剩余集裝箱重量public static int maxLoading(int ww,int cc) /初始化類數(shù)據(jù)成員 n=ww.length-1; w=ww; c=cc; cw

11、=0; bestw=0; r=0; /初始化r for(int i=1;in) /到達(dá)葉結(jié)點(diǎn) if(cwbestw)bestw=cw; return; r-=wi; if(cw+wibestw) backtrack(i+1);/搜索右子樹 r+=wi;4.構(gòu)造最優(yōu)解可在算法中增加數(shù)據(jù)成員x和bestx。x：用來記錄從根到當(dāng)前結(jié)點(diǎn)的路徑bestx：用來記錄當(dāng)前最優(yōu)解public class Loading /類數(shù)據(jù)成員 static int n; /集裝箱數(shù) static int w; /集裝箱重量數(shù)組 static int c; /第一艘輪船的載重量 static int cw; /當(dāng)前載重量

12、 static int bestw; /當(dāng)前最優(yōu)載重量 static int r; /剩余集裝箱重量 static int x; /當(dāng)前解 static int bestx; /當(dāng)前最優(yōu)解public static int maxLoading(int ww,int cc,int xx)n=ww.length-1;w=ww;c=cc;cw=0;bestw=0;x=new intn+1;bestx=xx;r=0;for(int i=1;i=n;i+)r+=wi;backtrack(1);return bestw;public static int maxLoading(int ww,int cc

13、) /初始化類數(shù)據(jù)成員 n=ww.length-1; w=ww; c=cc; cw=0; bestw=0; r=0; /初始化r for(int i=1;in)for(int j=1;j=n;j+)bestxj=xj;bestw=cw;return; r-=wi;if(cw+wibestw)xi=0; backtrack(i+1); /搜索右子樹r+=wi;5.3 批處理作業(yè)調(diào)度1 問題的描述給定n個(gè)作業(yè)集 J1,J2,Jn。每個(gè)作業(yè)先由機(jī)器1處理，再由機(jī)器2處理。Ji需機(jī)器j的處理時(shí)間為tji。對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間(時(shí)間點(diǎn))。所有作業(yè)在機(jī)器2上完成

14、處理的時(shí)間和f=F21+F22+F2n稱為該作業(yè)調(diào)度的完成時(shí)間和。問題：對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。對(duì)于批處理作業(yè)調(diào)度問題,可以證明, 存在一個(gè)最佳作業(yè)調(diào)度使得在機(jī)器1和2上以相同次序完成。例如：有3個(gè)作業(yè)，所需時(shí)間如下表tji機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)323這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(=3+6+10)，18，20，21，19，19易見，最佳調(diào)度方案是1, 3, 2，其完成時(shí)間和為18。2.算法設(shè)計(jì)解空間：排列樹設(shè)x=1,2, n為所給

15、n個(gè)作業(yè)，則相應(yīng)的排列樹由x1:n的所有排列構(gòu)成。public class FlowShop static int n, /作業(yè)數(shù) f1, /機(jī)器1完成處理時(shí)間點(diǎn) f, /完成時(shí)間和 bestf; /當(dāng)前最優(yōu)值static int m; /各作業(yè)所需的處理時(shí)間static int x; /當(dāng)前作業(yè)調(diào)度static int bestx;/當(dāng)前最優(yōu)作業(yè)調(diào)度static int f2;/機(jī)器2完成處理時(shí)間點(diǎn)private static void backtrack(int i)if (in) for (int j=1; j=n; j+) bestxj = xj;bestf = f;elsefor (

16、int j=i; jf1)?f2i-1:f1)+mxj2;f+=f2i;if (f bestf) Swap(x,i,j);backtrack(i+1);Swap(x,i,j);f1-=mxj1;f-=f2i;由于Backtrack在每一結(jié)點(diǎn)處耗費(fèi)O(1)時(shí)間, 整個(gè)算法時(shí)間復(fù)雜性為(n!).5.4 符號(hào)三角形問題1 問題的描述右圖是由14個(gè)“+”和14個(gè)“-”組成的符號(hào)三角形。2個(gè)同號(hào)下面都是“+”，2個(gè)異號(hào)下面都是“-”。在一般情況下，符號(hào)三角形的第一行有n個(gè)符號(hào)。問題：要求對(duì)于給定的n，計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的“+”和“-”的個(gè)數(shù)相同。+ + - + - + + - - -

17、 - +- + + + - - + + - - + - - - +2. 算法設(shè)計(jì)解向量：用n元組x1:n表示符號(hào)三角形的第一行。xi=1表示三角形的第一行的第i個(gè)字符為”+”; xi=0為”-”. 解空間：子集樹可行性約束函數(shù)：當(dāng)前符號(hào)三角形所包含的“+”個(gè)數(shù)與“-”個(gè)數(shù)均不超過n*(n+1)/4, 因其符號(hào)總數(shù)為n*(n+1)/2. 無解的判斷：n*(n+1)/2為奇數(shù) public class Triangles static int n,half,count;/第一行符號(hào)數(shù)目,總符號(hào)數(shù)一半,”+”個(gè)數(shù)static int p;/符號(hào)三角形矩陣static long sum;/可行符號(hào)三角

18、形的數(shù)目public static long compute(int nn)n=nn; count=0;sum=0;half=n*(n+1)/2;if (half%2=1) return 0;half=half/2;p=new int n+1n+1;for(int i=0;i=n;i+)for(int j=0;jhalf)|(t*(t-1)/2-counthalf) return;/ 搜索至葉結(jié)點(diǎn),得到+-號(hào)相同的符號(hào)三角形, 三角形數(shù)增1. if (tn) sum+;elsefor (int i=0;i2;i+)p1t=i; /得到第1行的第t個(gè)符號(hào)count+=i; /記錄符號(hào)的數(shù)目/由第

19、1行的t個(gè)符號(hào)得到第2行到第t行的符號(hào)for (int j=2;j=t;j+)/由上一行的相鄰兩個(gè)符號(hào)異或得到當(dāng)前行的當(dāng)前元素pjt-j+1=pj-1t-j+1pj-1t-j+2;count+=pjt-j+1;backtrack(t+1); /計(jì)算下一層/去除重復(fù)計(jì)算的當(dāng)前層計(jì)數(shù)for (int j=2;j=t;j+) count-=pjt-j+1;count-=i;5.5 n后問題1 問題的描述在nn格的棋盤上放置彼此不受攻擊的n個(gè)皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在nn格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一

20、斜線上。1 2 3 4 5 6 7 812345678QQQQQQQQ2.算法設(shè)計(jì)解向量：(x1, x2, , xn), xi表示皇后i放在棋盤的第i行的第xi列上. 可行解空間：排列樹顯約束：xi=1,2, ,n (列的取值范圍)隱約束：1) 不同列：xixj 2) 不處于同一正、反對(duì)角線上：|i-j|xi-xj|函數(shù)Place：來測試若將皇后k放在xk列，是否與前面已放置的k-1個(gè)皇后都不在同一列，且不在同一斜線上。回溯法解n后問題，用一棵完全n叉樹來表示其解空間。用可行性約束函數(shù)place可剪去不滿足行、列和斜線約束的子樹。public class NQueen1 static int

21、n; /皇后個(gè)數(shù)static int x; /當(dāng)前解static long sum; /當(dāng)前已找到的可靠方案數(shù) public static long nQueen(int nn) n=nn; sum=0; x=new int n+1; for(int i=0;i=n;i+) xi=0; backtrack(1); return sum; private static boolean place(int k) /判斷當(dāng)前第k個(gè)皇后，是否與前k-1個(gè)沖突 for(int j=1;jn) sum+;/可行解數(shù)目增1 /輸出當(dāng)前解 for(int i=0;ix.length;i+) System.ou

22、t.print (xi+ ); System.out.println(); else /依次嘗試將當(dāng)前皇后放在各個(gè)列 for(int i=1;i=n;i+) xt=i; /若可以放置在t列，則繼續(xù)放置下一個(gè) if(place(t)backtrack(t+1); 5.6 0-1背包問題1 算法的描述解空間：子集樹 (與裝載問題的回溯法相似)可行性約束函數(shù)：上界函數(shù)為：cp+rbestpcp：當(dāng)前背包中物品價(jià)值bestp：當(dāng)前最優(yōu)價(jià)值r：當(dāng)前剩余物品價(jià)值總和，即上界函數(shù)的改進(jìn)：計(jì)算右子樹中解的上界的更好方法是將剩余物品依其單位重量價(jià)值排序，然后依次裝入物品，直到裝不下時(shí)，再裝入該物品的一部分而裝滿

23、背包。由此可得右子樹的上界。例如：n=4，c=7，p=9,10,7,4，w=3,5,2,1對(duì)于整個(gè)問題上界的計(jì)算可以為：計(jì)算單位重量的價(jià)值為3,2,3.5,4可得該情況背包問題解為1,0.2,1,1，最優(yōu)值為22所以對(duì)于0-1背包問題的最優(yōu)值不大于22public class Knapsack private static class Element implements Comparable int id; /物品編號(hào)double d;/單位重量價(jià)值private Element(int idd, double dd)id = idd; d = dd;public int compareTo

24、(Object x)double xd = (Element) x).d;if(dxd) return -1;if(d = xd) return 0;return 1;public boolean equals(Object x)return d = (Element)x).d;static double c; /背包容量static int n; /物品數(shù)static double w; /物品重量數(shù)組static double p; /物品價(jià)值數(shù)組static double cw; /當(dāng)前重量static double cp; /當(dāng)前價(jià)值static double bestp; /當(dāng)前最優(yōu)

25、價(jià)值public static double knapsack(double pp,double ww,double cc)c = cc; n = pp.length-1;cw = 0.0; cp = 0.0; bestp = 0.0;Element q = new Elementn;for(int i=1;i=n;i+) /根據(jù)單位價(jià)值對(duì)數(shù)組q進(jìn)行初始化qi-1 = new Element(i,ppi/wwi);MergeSort.mergeSort(q); /按單位價(jià)值由小到大排序p = new doublen+1; w = new doublen+1; /根據(jù)單位價(jià)值由大到小的順序，存放

26、各物品的價(jià)值和重量for(int i=1;in)bestp = cp;return;if(cw+wibestp)backtrack(i+1); /進(jìn)入右子樹private static double bound(int i)double cleft = c-cw;/剩余容量double bound = cp;/以物品單位重量價(jià)值遞減順序裝入物品while(i=n & wi=cleft)cleft -= wi;bound += pi;i+;/裝滿背包if(in)/ 到達(dá)葉結(jié)點(diǎn)for (int j=1;j=n;j+)bestxj = xj;bestn = cn; return;/ 檢查頂點(diǎn) i 與

27、當(dāng)前團(tuán)的連接boolean OK=true;for (int j=1; j bestn) xi = 0;backtrack(i+1);5.8 圖的m著色問題1.問題描述給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色。這個(gè)問題是圖的m可著色判定問題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題?？善矫鎴D：若一個(gè)圖的所有頂點(diǎn)和邊都能用某種方式畫在平面上且沒有任何兩個(gè)邊相交。對(duì)于圖著色的研究是從m可著色性問題的著名特例 四

28、色問題開始的。四色猜想是英國學(xué)者于1852年提出的，這個(gè)問題要求證明平面或球面上的任何地圖的所有區(qū)域都可以至多用四種顏色來著色，使任何兩個(gè)有一段公共邊界的相鄰區(qū)域沒有相同的顏色。假設(shè)每個(gè)國家單連通，國家相鄰指這兩個(gè)國家有一段長度不為0的公共邊界，而不僅有一個(gè)公共點(diǎn)。這個(gè)問題可轉(zhuǎn)換成對(duì)一平面圖的4著色判定問題。多年來，已證明用5種顏色足以對(duì)任何一幅地圖著色。但是, 一直找不到一定要求多于4種顏色的地圖。直到1976年 ，這個(gè)問題才由三位美國學(xué)者在計(jì)算機(jī)上花費(fèi)了1200個(gè)小時(shí)才給出證明：任何平面圖是可以4著色的。四色猜想從此變成了四色定理。實(shí)例：如下圖n=7, m=32. 算法設(shè)計(jì)討論一般連通圖的

29、可著色問題，不僅限于可平面圖。問題：給定圖G=(V,E)和m種顏色，如果該圖不是m可著色，給出否定回答；若m可著色，找出所有不同著色方法。數(shù)據(jù)表示：無向連通圖：鄰接矩陣a表示， aij=true表示有邊(i,j)， aij=false表示無邊(i,j)m種顏色：整數(shù)1,2,n表示頂點(diǎn)著色情況：數(shù)組x表示，xi表示頂點(diǎn)i的顏色解向量：(x1, x2, , xn)，頂點(diǎn)i所著顏色為xi解空間：完全m叉樹可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。n3，m3的狀態(tài)空間樹public class Coloring static int n;/圖G的頂點(diǎn)數(shù)static int m;/可用顏色數(shù)s

30、tatic boolean a;/圖G的鄰接矩陣static int x;/當(dāng)前解static long sum;/當(dāng)前已找到的方案數(shù)public static long mColoring(int mm)m=mm;sum=0;backtrack(1);return sum;/ 檢查顏色可用性private static boolean Ok(int k)for (int j=1;jn)sum+;/可行解數(shù)目加1/輸出當(dāng)前可行解for (int i=1;i=n;i+)System.out.print(xi+ );System.out.println();elsefor (int i=1;i=m

31、;i+)xt=i;/為當(dāng)前點(diǎn)著顏色i/檢測當(dāng)前點(diǎn)著色是否可行if (Ok(t) backtrack(t+1);xt=0;3.復(fù)雜度分析圖m可著色問題的解空間樹中，內(nèi)結(jié)點(diǎn)個(gè)數(shù)是： 對(duì)于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)每一個(gè)兒子的顏色可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是5.9 旅行售貨員問題1.算法描述某售貨員到若干城市去推銷商品，已知各城市之間的路程（或旅費(fèi)）。他要選定一條路線，經(jīng)過每個(gè)城市一遍最后回到駐地的路線，使得總的路程（或總旅費(fèi)）最小。問題表示：G =（V,E），有n個(gè)結(jié)點(diǎn)的連通圖表示城市路程解向量：(x1,x2,xn)解空間：排列數(shù)顯式約束：xixj隱式

32、約束：(xi-1,xi)E上界函數(shù)：x1:ibestcG1的哈密頓回路存在，為：128765431而G2不存在任何哈密頓回路。G1：有哈密頓回路 G2：沒有哈密頓回路public class Bttsp static int n;/圖G的頂點(diǎn)數(shù)static int x;/當(dāng)前解static int bestx;/當(dāng)前最優(yōu)解static float bestc;/當(dāng)前最優(yōu)值static float cc;/當(dāng)前費(fèi)用static float a ;/圖G的鄰接矩陣public static float tsp(int v)/置x為單位排列x =new intn+1;for(int i=1;i=n;

33、i+) xi=i;bestc = Float.MAX_VALUE;bestx = v;cc = 0;backtrack(2); /搜索x2:n的全排列return bestc;private static void backtrack(int i)/到葉子結(jié)點(diǎn)if(i=n)/如果(n-1,n)和(n,1)邊存在，且回路費(fèi)用小于當(dāng)前最優(yōu)值/則保存最優(yōu)解和最優(yōu)值if(axn-1xn Float.MAX_VALUE & axn1Float.MAX_VALUE & (bestc = Float.MAX_VALUE | cc+axn-1xn+axn1bestc)for(int j=1;j=n;j+) b

34、estxj = xj;bestc = cc+axn-1xn+axn1;else/依次將各個(gè)數(shù)作為當(dāng)前位置i處排列的數(shù)for(int j=i;j=n;j+)/若邊(i-1,j)存在，且當(dāng)前費(fèi)用小于最優(yōu)值，則搜索子樹if(axi-1xjFloat.MAX_VALUE & (bestc = Float.MAX_VALUE |cc+axi-1xjn) compute(); else for (int j=t;j=n;j+) swap(r,t,j);float centerx = center(t);/若當(dāng)前所選圓的圓排列長度小于當(dāng)前最優(yōu)值if (centerx+rt+r1min) xt=centerx

35、;/記錄圓心坐標(biāo)trackback(t+1);/排列下一個(gè)swap(r,t,j);private static float center(int t) /計(jì)算當(dāng)前所選擇圓的圓心橫坐標(biāo)float temp=0;/考慮和1到t-1各個(gè)圓相切的情況for (int j=1;j temp) temp = valuex;return temp;private static void compute() / 計(jì)算當(dāng)前圓排列的長度/low表示當(dāng)前圓的左邊界，以當(dāng)前圓心坐標(biāo)為基準(zhǔn)float low=0;float high=0;/high表示當(dāng)前圓的右邊界/分別計(jì)算出每個(gè)圓的左右邊界for (int i=1;

36、i=n;i+) bestri=ri;/左邊界最小值為圓排列的左邊界if (xi-rihigh)high=xi+ri;/圓排列的長度為右邊界間左邊界if (high-lowmin) min=high-low; 3.復(fù)雜度分析在最壞情況下，算法backtrack可能需要計(jì)算O(n!)次當(dāng)前圓排列長度；每次計(jì)算需O(n)計(jì)算時(shí)間，整個(gè)算法的計(jì)算時(shí)間復(fù)雜性為O(n+1)!)。上述算法尚有許多改進(jìn)的余地。例如：1,2,n-1,n和n,n-1, ,2,1這種互為鏡像的排列具有相同的圓排列長度，只計(jì)算一個(gè)就夠了，可減少約一半的計(jì)算量。如果所給的n個(gè)圓中有k個(gè)圓有相同的半徑，則這k個(gè)圓產(chǎn)生的k!個(gè)完全相同的圓

37、排列，只計(jì)算一個(gè)就夠了。5.11 電路板排列問題1.問題描述大規(guī)模電子系統(tǒng)設(shè)計(jì)中提出的一個(gè)實(shí)際問題。問題的提法：將n塊電路板以最佳排列方案，插入帶有n個(gè)插槽的機(jī)箱中。電路板集合：B=1, 2, , n 連接塊集合：L=N1, N2, , Nm 連接塊：用同一根導(dǎo)線連接的電路板的集合，是電路板集合的子集，即有NjB排列：X=, 即在機(jī)箱的第i個(gè)插槽中插入電路板xi。排列密度density(X)：跨越相鄰電路板插槽的最大連線數(shù)問題要求：具有最小排列密度density(X)的排列實(shí)例：B=1,2,8L=N1,N2,N5N1=4,5,6N2=2,3N3=1,3N4=3,6N5=7,8 排列 X1= 排

38、列密度=?density(X1) = 2電路板插槽編號(hào)N1=4,5,6N2=2,3N3=1,3N4=3,6N5=7,8 排列 X2= density(X2) = 4插槽2和3之間的連線數(shù)為4 2.算法設(shè)計(jì)解空間：排列樹算法：通過系統(tǒng)搜索問題解空間的排列樹，找出電路板最佳排列。數(shù)據(jù)表示：totalj：連接塊Nj的電路板數(shù)nowj：x1, x2, , xi中包含的Nj中的電路板數(shù)cd：從電路板1到i的最大排列密度橫跨電路板i到i+1的連接塊集合，其條件如下：塊Nj的連線跨越i和i+1等價(jià)于：nowj0且nowjtotalj例如：計(jì)算插槽i和i1的連線密度當(dāng)i=2時(shí)：now1=now2=now3=n

39、ow4=1, total1=3, total2=total3=total4=2N1,N2,N3,N4的連線都跨越電路板2和3public class Board static int n = 10;/ 電路板的數(shù)量static int m = 6;/ 連接塊的數(shù)量static int x; / 用于記錄一個(gè)排列static int bestx;/當(dāng)前最優(yōu)解static int total; /totalj表示連接塊j的電路板數(shù)static int now;/nowj當(dāng)前解中含連接塊j的電路板數(shù)static int b; /bij=1表示xi在連接塊j中static int bestd; /當(dāng)前

40、最優(yōu)密度public static int arrange(int bb,int mm,int xx)n=bb.length-1;m=mm;x = new intn + 1;bestx=xx;total= new intm + 1;now = new intm + 1;b = bb;bestd = m + 1;/ 初始化電路板的排列為單位排列for (int i = 1; i = n; i+) xi = i;/記錄各連接塊的電路板數(shù)for(int j=1;j=m;j+)totalj+=bij;backtrack(1,0);return bestd;private static void bac

41、ktrack(int i,int dd) if (i = n) /搜索到葉子結(jié)點(diǎn)/將當(dāng)前解作為當(dāng)前最優(yōu)解for (int j = 1; j = n; j+)bestxj = xj;bestd=dd;/記錄最優(yōu)值 else /確定第i個(gè)電路板for (int j=i; j=n; j+) /選擇xj為下一電路板int d=0;for(int k=1;k0 & totalk!=nowk) d+;/若d小于上一層的密度dd，則當(dāng)前密度d為ddif (ddd) d=dd;/小于當(dāng)前最優(yōu)值，則搜索子樹if(dbestd)swap(x,i,j); backtrack(i+1,d); swap(x,i,j);

42、/恢復(fù)狀態(tài)for(int k=1;k=m;k+) nowk-=bxjk;3. 算法效率在每個(gè)結(jié)點(diǎn)處，函數(shù)Backtrack花費(fèi)O(m)時(shí)間計(jì)算每個(gè)兒子結(jié)點(diǎn)的密度。 排列樹的搜索時(shí)間為O(n!)。 算法耗費(fèi)為O(mn!)。5.12 連續(xù)郵資問題1.問題描述假設(shè)國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求：對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，使得在1張信封上可貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。例如: 當(dāng)n=5和m=4時(shí)， 解X=，其中x1=1，且滿足：x1x2x5面值為X=的5種郵票, 可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。若X=

43、, 則郵資連續(xù)區(qū)間為1-4。2.算法設(shè)計(jì)：解向量：用n元組x1: n表示n種不同的郵票面值，并約定它們從小到大排列。x1=1是唯一選擇。最大連續(xù)郵資區(qū)間是1: mx2的取值范圍是2: m+1可行性約束函數(shù)：已選定x1: i-1，其最大連續(xù)郵資區(qū)間是1: r，接下來xi的取值范圍是xi-1+1: r+1。解空間：用一棵樹來表示。樹結(jié)點(diǎn)的度隨x的值變化如何確定r的值？計(jì)算X1:i的最大連續(xù)郵資區(qū)間在本算法中被頻繁使用到，因此勢(shì)必要找到一個(gè)高效的方法。考慮到直接遞歸的求解復(fù)雜度太高，我們不妨嘗試計(jì)算用不超過m張面值為x1:i的郵票貼出郵資k所需的最少郵票數(shù)yk。通過yk可以很快推出r的值。事實(shí)上，y

44、k可以通過遞推在O(n)時(shí)間內(nèi)解決：for (int j=0; j= xi-2*(m-1);j+)if (yjm)for (int k=1;k=m-yj;k+)if (yj+kyj+xi-1*k) yj+xi-1*k=yj+k;while (yrmaxint) r+;public class Stamps static int n,/郵票面值種類數(shù)m,/允許貼的最多郵票數(shù)maxR,/當(dāng)前最優(yōu)值maxint,/大整數(shù)maxl;/郵資上界static int x;/當(dāng)前解static int y;/貼出各種郵資所需的最少郵票數(shù)static int bestx;/當(dāng)前最優(yōu)解public static

45、 int maxStamp(int nn, int mm, intxx)int maxll=1500;n=nn;m=mm;maxR=0;maxint=Integer.MAX_VALUE;maxl=maxll;bestx=xx;x=new intn+1;y=new intmaxl+1;for(int i=0;i=n;i+) xi=0;for(int i=1;i=maxl;i+) yi=maxint;x1=1;y0=0;backtrack(2,1);return maxR;/i為當(dāng)前層次，即確定的是第幾個(gè)郵票/r為x1:i-1的最大連續(xù)區(qū)間private static void backtrack(int i,int r)/計(jì)算貼出j所需的最小郵票數(shù)for(int j=0;j=xi-2*(m-1);j+)/若當(dāng)前貼出j的郵票數(shù)小于m，則利用它對(duì)貼出j+xi-1*k所需的最小郵票數(shù)進(jìn)行更新if (yjm)for(int k=1;k=m-yj;k+)if (yj+kyj+xi-1*k) yj+xi-1*k=yj+k;/更新r的值，r為x1:i-1的最大連續(xù)區(qū)間加1while(yrn)/若當(dāng)前連續(xù)區(qū)間大于最優(yōu)值，則更新最優(yōu)值與最優(yōu)解if(r-1maxR)maxR=r-1;for(int j=1;j=n;j+)