0028算法筆記——【回溯法】批作業(yè)調(diào)度問題和符號(hào)三角形問題

1、1、批作業(yè)調(diào)度問題問題描述給定n個(gè)作業(yè)的集合J1,J2, 口每個(gè)作業(yè)必須先由機(jī)器1處 理，然后由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時(shí)間為tji。對(duì)于一 個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。所有 作業(yè)在機(jī)器2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問題要求對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí) 間和達(dá)到最小。例：設(shè)n=3,考慮以下實(shí)例:機(jī)器2務(wù) 機(jī)器1 作業(yè)T-1作業(yè) 3 2作業(yè) 2這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,

2、20,21, 19, 19。易見，最佳調(diào)度方案是1,3,2,其完成時(shí)間和為18。(2)算法設(shè)計(jì)批處理作業(yè)調(diào)度問題要從n個(gè)作業(yè)的所有排列中找出具有最小完成時(shí)間和的作業(yè)調(diào)度，所以如圖，批處理作業(yè)調(diào)度問題的解空間是一顆排列樹。按照回溯法搜索排列樹的算法框架，設(shè)開始時(shí) x=1,2,n是所給的n個(gè)作業(yè)，則相應(yīng)的排列樹由x1:n的所有排列構(gòu)成。55.cout<< ")"19 r 20211919算法具體代碼如下:cpp view plain copy1. #include "stdafx.h"2. #include <iostream>3.

3、using namespace std;4.5. class Flowshop6. 7. friend int Flow( int *M, int n, int bestx);8. private :9. void Backtrack( int i);11.int *M,/各作業(yè)所需的處理時(shí)間2.*x,/當(dāng)前作業(yè)調(diào)度13.*bestx,/當(dāng)前最優(yōu)作業(yè)調(diào)度14.15.*f2,/機(jī)器2完成處理時(shí)間16.f1,/機(jī)器1完

4、成處理時(shí)間17.f,/完成時(shí)間和18.19.bestf,/當(dāng)前最優(yōu)值20.n;/ 作業(yè)數(shù)21. ;22.23. intFlow( int*M, int n, int bestx);24.template < class Type> inline void S &a, Type &b);int main()int n=3,bf;int M143=0,0,0,021,0,3,1,0,2。;int *M= new int *n+1;for ( int i=0;i<=n;i+)Mi= new int 3;cout<< "M(i,j)值如下：&qu

5、ot;<<endl;for ( int i=0;i<=n;i+) for (int j=0;j<3;j+)Mij=M1ij;int bestx4;for ( int i=1;i<=n;i+) cout<< "("for (int j=1;j<3;j+) cout<<Mij<<""9.90

6、.7.98.99.bf=Flow(M,n,bestx);for ( int i=0;i<=n;i+) delete Mi; delete M;M=0;cout<<endl<<"最優(yōu)值是："<<bf<<endl;cout<<"最優(yōu)調(diào)度是："for ( int i=1;i<=n;i+) cout<<bestxi<<""cout<<endl;return 0;void Flowshop:Backt

7、rack( int i) if (i>n) for ( int j=1;j<=n;j+) bestxj = xj; bestf = f; else for ( int j = i;j <= n; j+) f1+=Mxj1;/機(jī)器2執(zhí)行的是機(jī)器1已完成的作業(yè)，所以是f2i=(f2i-1>f1)?f2i-1:f1)+Mxj2;f+=f2i;i-1if (f < bestf) / 剪枝 100.Swap(xi, xj);101.Backtrack(i+1);102.Swap(xi, xj);103.104.f1-=Mxj1;105.f-=f2i;106.107.108.

8、 109.110. int Flow( int *M, int n, int111. 112.int ub=30000;113.114.Flowshop X;115.X.n=n;116.X.x= new int n+1;117.X.f2= new int n+1;118.119.X.M=M;120.X.bestx=bestx;121.X.bestf=ub;122.123.X.f1=0;124.X.f=0;125.126.for (int i=0;i<=n;i+)127.128.X.f2i=0,X.xi=i;129.130.X.Backtrack(1);131.delete X.x;132

9、.delete 口X.f2;133.return X.bestf;134. 135.136. template < class Type>137. inline void S &a, Type &b)138. 139.Type temp=a;140.a=b;141.b=temp;142. bestx口)由于算法Backtrack在每一個(gè)節(jié)點(diǎn)處耗費(fèi) 0(1)計(jì)算時(shí)間，故在最壞情況下，整個(gè)算法計(jì)算時(shí)間復(fù)雜性為0(n!)。程序運(yùn)行結(jié)果如下:2、符號(hào)三角形問題問題描速下圖是由14個(gè)“前14個(gè)-”組成的符號(hào)三角形。2個(gè)同號(hào)下面都是“土” 2個(gè)異號(hào)下面都是，。，O在一般情況下，

10、符號(hào)三角形的第一行有 n個(gè)符號(hào)。符號(hào)三角形問題要求對(duì)于給定的n,計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含的“+'和-”的個(gè)數(shù)相同。(2)算法設(shè)計(jì)解向量：用n元組x1:n表示符號(hào)三角形的第一行。當(dāng)xi=1時(shí)表示符號(hào)三角形第一行的第i個(gè)符號(hào)為"+”;當(dāng)i=0時(shí)，表示符號(hào)三角形 第一行的第i個(gè)符號(hào)為"-"； 1<=x<=n。由于xi是二值的，所以可以用 一棵完全二叉樹來表示解空間?？尚行约s束函數(shù)：在符號(hào)三角形的第一行前i個(gè)符號(hào)x1:i確定后，就 確定了一個(gè)由i(i+1)/2個(gè)符號(hào)組成的符號(hào)三角形。下一步確定xi+1的值后，只要在前面已確定的符號(hào)三角形的

11、右邊加一條邊，就可以擴(kuò)展 為x1:i+1所相應(yīng)的符號(hào)三角形。最終由x1:n所確定的符號(hào)三角形中 包含"+”號(hào)個(gè)數(shù)與"”個(gè)數(shù)同為n(n+1)/4。因此，當(dāng)前符號(hào)三角形所包含 的“嚇數(shù)與-”個(gè)數(shù)均不超過n*(n+1)/4 。無解的判斷：對(duì)于給定的n,當(dāng)n*(n+1)/2為奇數(shù)時(shí)，顯然不存在包含 的"+"號(hào)個(gè)數(shù)與"-”號(hào)個(gè)數(shù)相同的符號(hào)三角形。此時(shí)，可以通過簡(jiǎn)單的判 斷加以處理。程序的具體代碼如下：cpp view plain copy1. #include "stdafx.h"2. #include <iostream>

12、;3. using namespace std;4.5. class Triangle6. 7. friendint Compute( int );8. private :9. void Backtrack( int i);10. int n,/第一行的符號(hào)個(gè)數(shù)11. half,/n*(n+1)/412. count,/當(dāng)前"+"號(hào)個(gè)數(shù)13. *p;/符號(hào)三角矩陣14. long sum; /已找到的符號(hào)三角形數(shù)15. ;16.17. int Compute( int n);18.19. int main()20. 21. for ( int n=1;n<=10;n+

13、)22. 23. cout<<"n=" <<n<<"時(shí)，共有"<<Compute(n);24. cout<<"個(gè)不同的符號(hào)三角形。"<<endl;25. 26. return 0;27. 28.29. void Triangle:Backtrack( int t)30. 31. if (count>half)|(t*(t-1)/2-count>half)32. 33. return ;34. 35.36. if (t>n)37. 38. sum+

14、;39. 40. else41. 42. for ( int i=0;i<2;i+)43. 44. p1t=i;/ 第一行符號(hào)45. count+=i;/ 當(dāng)前"+"號(hào)個(gè)數(shù)6.47. for (int j=2;j<=t;j+)pjt-j+1=pj-1t-j+1Apj-1t-j+2；count+=pjt-j+1;Backtrack(t+1);for ( int j=2;j<=t;j+)count-=pjt-j+1;58. 59. 60. 4.95.96.int Compute( int n)Triangle X;X.n=n;X.count=0;X.sum=0;X.half=n*(n+1)/2;if (X.half%2=1) return 0;X.half=X.half/2;int *p= new int *n+1;for ( int i=0;i<=n;i+)pi= new int n+1;for ( int i=0;i<=n;i+)for (int j