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]view plain copy1.#include "stdafx.h"2.#include <iostream>ing namespace std;4.5.class Flowshop6.{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 <class Type>26.inline void S &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)值如下："<<endl;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<<M[i][j]<<" ";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<<endl<<"最优值是："<<bf<<endl;69. cout<<"最优调度是：";70.71.for(int i=1;i<=n;i++)72. {73. cout<<bestx[i]<<" ";74. }75. cout<<endl;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.else90. {91.for (int j = i; j <= n; j++)92. {93. f1+=M[x[j]][1];94.//机器2执行的是机器1已完成的作业，所以是i-195. 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 <class Type>137.inline void S &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]view plain copy1.#include "stdafx.h"2.#include <iostream>ing namespace std;4.5.class Triangle6.{7.friend int Compute(int);8.private:9.void Backtrack(int i);10.int n, //第一行的符号个数11. half, //n*(n+1)/412. 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="<<n<<"时，共有"<<Compute(n);24. cout<<"个不同的符号三角形。

"<<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++;39. }40.else41. {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)。