0028算法笔记回溯法批作业调度问题和符号三角形问题.docx
《0028算法笔记回溯法批作业调度问题和符号三角形问题.docx》由会员分享，可在线阅读，更多相关《0028算法笔记回溯法批作业调度问题和符号三角形问题.docx（13页珍藏版）》请在冰点文库上搜索。
0028算法笔记回溯法批作业调度问题和符号三角形问题
1、批作业调度问题
（1）问题描述
给定n个作业的集合{J1,J2,…,Jn}。
每个作业必须先由机器1处理，然后由机器2处理。
作业Ji需要机器j的处理时间为tji。
对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。
所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
例：
设n=3，考虑以下实例：
这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。
易见，最佳调度方案是1,3,2，其完成时间和为18。
（2）算法设计
批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树。
按照回溯法搜索排列树的算法框架，设开始时x=[1,2,……n]是所给的n个作业，则相应的排列树由x[1:
n]的所有排列构成。
算法具体代码如下：
[cpp] viewplain copy
1.#include "stdafx.h"
2.#include
3.using namespace std;
4.
5.class Flowshop
6.{
7. friend int Flow（int **M,int n,int bestx[]）;
8. private:
9. void Backtrack（int i）;
10.
11. int **M, // 各作业所需的处理时间
12. *x, // 当前作业调度
13. *bestx, // 当前最优作业调度
14.
15. *f2, // 机器2完成处理时间
16. f1, // 机器1完成处理时间
17. f, // 完成时间和
18.
19. bestf, // 当前最优值
20. n; // 作业数
21. };
22.
23.int Flow（int **M,int n,int bestx[]）;
24.
25.template
26.inline void Swap（Type &a, Type &b）;
27.
28.int main（）
29.{
30. int n=3,bf;
31. int M1[4][3]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};
32.
33. int **M=new int*[n+1];
34.
35. for（int i=0;i<=n;i++）
36. {
37. M[i]=new int[3];
38. }
39. cout<<"M（i,j）值如下：
"<40.
41. for（int i=0;i<=n;i++）
42. {
43. for（int j=0;j<3;j++）
44. {
45. M[i][j]=M1[i][j];
46. }
47. }
48.
49. int bestx[4];
50. for（int i=1;i<=n;i++）
51. {
52. cout<<"（";
53. for（int j=1;j<3;j++）
54. cout<55. cout<<"）";
56. }
57.
58. bf=Flow（M,n,bestx）;
59.
60. for（int i=0;i<=n;i++）
61. {
62. delete []M[i];
63. }
64. delete []M;
65.
66. M=0;
67.
68. cout<"<69. cout<<"最优调度是：
";
70.
71. for（int i=1;i<=n;i++）
72. {
73. cout<74. }
75. cout<76. return 0;
77.}
78.
79.void Flowshop:
:
Backtrack（int i）
80.{
81. if （i>n）
82. {
83. for （int j=1; j<=n; j++）
84. {
85. bestx[j] = x[j];
86. }
87. bestf = f;
88. }
89. else
90. {
91. for （int j = i; j <= n; j++）
92. {
93. f1+=M[x[j]][1];
94. //机器2执行的是机器1已完成的作业，所以是i-1
95. f2[i]=（（f2[i-1]>f1）?
f2[i-1]:
f1）+M[x[j]][2];
96.
97. f+=f2[i];
98. if （f < bestf）//剪枝
99. {
100. Swap（x[i], x[j]）;
101. Backtrack（i+1）;
102. Swap（x[i], x[j]）;
103. }
104. f1-=M[x[j]][1];
105. f-=f2[i];
106. }
107. }
108.}
109.
110.int Flow（int **M,int n,int bestx[]）
111.{
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.f2[i]=0,X.x[i]=i;
129. }
130. X.Backtrack
（1）;
131. delete []X.x;
132. delete []X.f2;
133. return X.bestf;
134.}
135.
136.template
137.inline void Swap（Type &a, Type &b）
138.{
139. Type temp=a;
140. a=b;
141. b=temp;
142.}
由于算法Backtrack在每一个节点处耗费O
（1）计算时间，故在最坏情况下，整个算法计算时间复杂性为O（n!
）。
程序运行结果如下：
2、符号三角形问题
（1）问题描速
下图是由14个“+”和14个“-”组成的符号三角形。
2个同号下面都是“+”，2个异号下面都是“-”。
在一般情况下，符号三角形的第一行有n个符号。
符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
（2）算法设计
解向量：
用n元组x[1:
n]表示符号三角形的第一行。
当x[i]=1时表示符号三角形第一行的第i个符号为"+"；当i=0时，表示符号三角形第一行的第i个符号为"-"；1<=x<=n。
由于x[i]是二值的，所以可以用一棵完全二叉树来表示解空间。
可行性约束函数：
在符号三角形的第一行前i个符号x[1:
i]确定后，就确定了一个由i（i+1）/2个符号组成的符号三角形。
下一步确定x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为x[1:
i+1]所相应的符号三角形。
最终由x[1:
n]所确定的符号三角形中包含"+"号个数与"-"个数同为n（n+1）/4。
因此，当前符号三角形所包含的“+”个数与“-”个数均不超过n*（n+1）/4。
无解的判断：
对于给定的n，当n*（n+1）/2为奇数时，显然不存在包含的"+"号个数与"-"号个数相同的符号三角形。
此时，可以通过简单的判断加以处理。
程序的具体代码如下：
[cpp] viewplain copy
1.#include "stdafx.h"
2.#include
3.using namespace std;
4.
5.class Triangle
6.{
7. friend int Compute（int）;
8. private:
9. void Backtrack（int i）;
10. int n, //第一行的符号个数
11. half, //n*（n+1）/4
12. count, //当前"+"号个数
13. **p; //符号三角矩阵
14. long sum; //已找到的符号三角形数
15.};
16.
17.int Compute（int n）;
18.
19.int main（）
20.{
21. for（int n=1;n<=10;n++）
22. {
23. cout<<"n="<24. cout<<"个不同的符号三角形。
"<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++;
39. }
40. else
41. {
42. for （int i=0;i<2;i++）
43. {
44. p[1][t]=i;//第一行符号
45. count+=i;//当前"+"号个数
46.
47. for（int j=2;j<=t;j++）
48. {
49. p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
50. count+=p[j][t-j+1];
51. }
52. Backtrack（t+1）;
53. for （int j=2;j<=t;j++）
54. {
55. count-=p[j][t-j+1];
56. }
57. count-=i;
58. }
59. }
60.}
61.
62.int Compute（int n）
63.{
64. Triangle X;
65. X.n=n;
66. X.count=0;
67. X.sum=0;
68.
69. X.half=n*（n+1）/2;
70. if（X.half%2==1）return 0;
71. X.half=X.half/2;
72.
73. int**p=new int*[n+1];
74.
75. for（int i=0;i<=n;i++）
76. {
77. p[i]=new int[n+1];
78. }
79.
80. for（int i=0;i<=n;i++）
81. {
82. for（int j=0;j<=n;j++）
83. {
84. p[i][j]=0;
85. }
86. }
87.
88. X.p=p;
89. X.Backtrack
（1）;
90. for（int i=0;i<=n;i++）
91. {
92. delete []p[i];
93. }
94. delete []p;
95. p=0;
96. return X.sum;
97.}
计算可行性约束需要O（n）时间，在最坏情况下有O（2^n）个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为O（n2^n）。
程序运行结果如图：
升级会员 