0028算法笔记回溯法批作业调度问题和符号三角形问题.docx
- 文档编号:8747535
- 上传时间:2023-05-14
- 格式:DOCX
- 页数:13
- 大小:140.76KB
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)。 程序运行结果如图:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 0028 算法 笔记 回溯 作业 调度 问题 符号 三角形