分支限界法作业答案.doc

分支限界法作业

1.旅行商问题
设有n个城市，城市之间道路的长度均大于或等于0，还可能是∞（对应城市之间无交通线路）。一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市，问他如何走才能使他走的路线最短？

要求：使用矩阵归约确定限界函数的方法，或者其他方法实现。
分析：
旅行商问题对应的解的元组为n元组，其中假设第一个城市为1，则n元组中未确定的为剩下n-1个城市，元组为（1,x2,…,xn）,每个xi的取值为{2,…,n}；约束条件为已经经过的城市不能再走，最后回到出发城市。目标函数是巡回旅行路线长度。
利用矩阵归约的方法确定限界函数：

限界函数：对任意路线上的结点d，设p是其前驱结点，则
f(d)=g(d)+h(d)，
其中，g(d)=f(p)+C’p[p][d]，h(d)=rd。C’p[p][d]是在p点规约后得到的矩阵中p点到d点的长度值，rd为d点可以归约掉的值。

算法1：(叶子结点进堆)
Input：图G；
Output：从源点1出发再回到1顶点的最短巡回旅行路线。

1.设定目标函数的限界down=r1，up=∞
2.计算初始结点1的f(1)=r1，将初始结点插入最小堆H;
3.while(H≠Φ)
4.{
5.从H中做DELETEMIN的操作，用p带回相应结点;
6.Ifp是叶子结点then
7.输出当前最优值，并从叶子结点沿parent指针输出解，退出；
8.Else
9.{产生p的所有满足约束条件的后继结点d(建树，建立指向parent的指针)
并计算f(d)；
iff(d)<upthen
{将d结点插入最小堆H中；
ifd是叶子结点then
{up=f(p);
删除活结点表(最小堆H)中函数值大于up值的结点；
}
}
}
18.}

算法2：(叶子结点不进堆)
Input：图G；
Output：从源点1出发再回到1顶点的最短巡回旅行路线。

1.设定目标函数的限界down=r1，up=∞
2.计算初始结点1的f(1)=r1，将初始结点插入最小堆H;
3.while(H≠Φ)
4.{
5.从H中做DELETEMIN的操作，用p带回相应结点;
6.产生p的所有满足约束条件的后继结点d(建树，建立指向parent的指针)
并计算f(d)；
7.while对每个结点d
8.{iff(d)<upthen
9.{ifd是叶子结点then
10.{up=f(p);
11.删除活结点表(最小堆H)中函数值大于up值的结点；
12.if(H=Φ)then
13.从叶子结点沿parent指针输出解，退出；
14.}
15.else将d结点插入最小堆H中；
16.}
17.}
18.}

2.批处理作业问题
设J1,J2,J3,J4是四项待处理的作业，它们的工序一样，即先在m1上处理，然后在m2上处理，最后在m3上处理，第i项作业在第j台机器上的处理时间为tij。找一种最佳处理顺序，使完成作业的总时间达到最短。

分析：
将问题推广到一般的n个作业，该问题对应的解的元组为n元组（x1,x2,…,xn）,每个xi的取值为{1,…,n}；约束条件为xi≠xj。
目标函数是sum3=max{sum2[n],sum3[n-1]}+tn3,
其中sum2[n]=max{sum1[n],sum2[n-1]}+tn2,
Sum1[n]=sum1[n-1]+tn1。
限界函数：设M是已经安排好的作业集合，M{1,2,...,n},|M|=k。现在要处理作业k+1，有：

其中sum1[k+1]=sum1[k]+tk+1,1
sum2[k+1]=max{sum1[k+1],sum2[k]}+tk+1,2
目标函数的下限界down=
Input：n个作业，及其在3台机器上的处理时间tij；
Output：n个作业的最佳处理顺序及其处理时间。

1.设定目标函数的限界down=，up=∞
2.计算初始结点1的sum1=0，sum2=0，db(1)=0，将初始结点插入最小堆H;
3.while(H≠Φ)
4.{
5.从H中做DELETEMIN的操作，用p带回相应结点;
6.产生p的所有满足约束条件的后继结点d(建树，建立指向parent的指针)
并计算db(d)；
7.while对每个结点d
8.{ifdb(d)<upthen
9.{ifd是叶子结点then
10.{up=db(p);
11.删除活结点表(最小堆H)中函数值大于up值的结点；
12.if(H=Φ)then
13.从叶子结点沿parent指针输出解，退出；
14.}
15.else将d结点插入最小堆H中；
16.}
17.}
18.}
3.装载问题
有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集