00算法笔记记录回溯法批作业调度问题及符号三角形问题doc.docx
《00算法笔记记录回溯法批作业调度问题及符号三角形问题doc.docx》由会员分享，可在线阅读，更多相关《00算法笔记记录回溯法批作业调度问题及符号三角形问题doc.docx（28页珍藏版）》请在冰点文库上搜索。
00算法笔记记录回溯法批作业调度问题及符号三角形问题doc
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]viewplaincopy
1.#include"stdafx.h"
2.#include
3.usingnamespacestd;
4.
5.classFlowshop
6.{
7.friendintFlow（int**M,intn,intbestx[]）;
8.private:
9.
void
Backtrack（
inti）;
10.
11.
int
**M,
//
各作业所需的处理时间
cout<<
"（";
for（intj=1;j<3;j++）
cout<"";
cout<<
"）";
12.
*x,
//
当前作业调度
13.
*bestx,
//当前最优作业调度
14.
15.
*f2,
//
机器2完成处理时间
16.
f1,
//
机器1完成处理时间
17.
f,
//
完成时间和
18.
19.
bestf,
//当前最优值
20.
n;
//作业数
21.};
22.
23.
intFlow（int
**M,intn,intbestx[]）;
24.
25.
template
26.
inline
void
S&a,Type&b）;
27.
28.intmain（）
29.{
30.intn=3,bf;
31.intM1[4][3]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};
32.
33.int**M=newint*[n+1];
34.
35.for（inti=0;i<=n;i++）
36.{
37.M[i]=newint[3];
38.}
39.cout<<"M（i,j）值如下：
"<40.
41.for（inti=0;i<=n;i++）
42.{
43.for（intj=0;j<3;j++）
44.{
45.M[i][j]=M1[i][j];
46.}
47.}
48.
49.intbestx[4];
50.for（inti=1;i<=n;i++）
51.{
52.
53.
54.
55.
56.}
57.
58.bf=Flow（M,n,bestx）;
59.
60.for（inti=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（inti=1;i<=n;i++）
72.{
73.cout<74.}
75.cout<76.return0;
77.}
78.
79.voidFlowshop:
:
Backtrack（inti）
80.{
81.if（i>n）
82.{
83.for（intj=1;j<=n;j++）
84.{
85.bestx[j]=x[j];
86.}
87.bestf=f;
88.}
89.else
90.{
91.for（intj=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（f99.{
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.intFlow（int**M,intn,intbestx[]）
111.{
112.intub=30000;
113.
114.FlowshopX;
115.X.n=n;
116.
X.x=
newint
[n+1];
117.
X.f2=
newint
[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（inti=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.returnX.bestf;
134.}
135.
136.template
137.inlinevoidS&a,Type&b）
138.{
139.Typetemp=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]viewplaincopy
1.#include"stdafx.h"
2.#include
3.usingnamespacestd;
4.
5.classTriangle
6.{
7.friendintCompute（int）;
8.private:
9.
void
Backtrack（inti）;
10.
int
n,
//第一行的符号个数
11.
half,
//n*（n+1）/4
12.
count,
//当前"+"号个数
13.
**p;
//符号三角矩阵
14.longsum;//已找到的符号三角形数
15.};
16.
17.intCompute（intn）;
18.
19.intmain（）
20.{
21.for（intn=1;n<=10;n++）
22.{
23.
cout<<
"n="<24.
cout<<
"个不同的符号三角形。
"<25.}
26.return0;
27.}
28.
29.voidTriangle:
:
Backtrack（intt）
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（inti=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（intj=2;j<=t;j++）
54.{
55.count-=p[j][t-j+1];
56.}
57.count-=i;
58.}
59.}
60.}
61.
62.intCompute（intn）
63.{
64.TriangleX;
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）return0;
71.X.half=X.half/2;
72.
73.int**p=newint*[n+1];
74.
75.for（inti=0;i<=n;i++）
76.{
77.p[i]=newint[n+1];
78.}
79.
80.for（inti=0;i<=n;i++）
81.{
82.for（intj=0;j<=n;j++）
83.{
84.p[i][j]=0;
85.}
86.}
87.
88.X.p=p;
89.X.Backtrack
（1）;
90.for（inti=0;i<=n;i++）
91.{
92.delete[]p[i];
93.}
94.delete[]p;
95.p=0;
96.returnX.sum;
97.}
计算可行性约束需要O（n）时间，在最坏情况下有O（2^n）个结点需
要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间
为O（n2^n）。
程序运行结果如图：
升级会员 