分支限界法作业答案.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) + Cppd， h(d) = rd。Cppd是在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. If p是叶子结点 then 7. 输出当前最优值，并从叶子结点沿parent指针输出解，退出；8. Else 9. 产生p的所有满足约束条件的后继结点d(建树，建立指向parent的指针)并计算f(d)；10. if f(d)up then 11. 将d结点插入最小堆H中；12. if d是叶子结点 then 13. up=f(p);14. 删除活结点表(最小堆H)中函数值大于up值的结点；15. 16. 17. 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 对每个结点d8. if f(d)up then 9. if d是叶子结点 then10. 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；约束条件为xixj。目标函数是sum3=maxsum2n,sum3n-1+tn3,其中sum2n=maxsum1n,sum2n-1+tn2, Sum1n=sum1n-1+tn1。限界函数：设M是已经安排好的作业集合，M1, 2, ., n, |M|=k。现在要处理作业k+1，有：其中sum1k+1=sum1k+ tk+1,1sum2k+1=maxsum1k+1, sum2k + 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 对每个结点d8. if db(d)up then 9. if d是叶子结点 then10. 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的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。分析：该问题的解决可以简化为尽量装满第一艘轮船，再将剩余集装箱装入第二艘轮船。这样就只需考虑第一艘轮船的装入就可以了。分析问题类似于只有体积限制的背包问题，因此可以模仿背包问题的解法。考虑如何将n个集装箱装入到载重量为C1的轮船上，尽可能将C1装满，此时如果剩余集装箱的重量小于等于C2，则找到一种装载方案，否则没有可行的装载方案。因此问题对应的解为n元组(x1,x2,xn),xi=0,1,与0/1背包问题类似，1代表装入，0代表不装入，约束条件为：。限界函数为：f(p)=g(d)+h(d),g(d)为已经装入第一艘轮船的重量，h(d)为剩余未考虑的集装箱重量。Input：n个集装箱，及其重量wi；两艘轮船的载重量C1，C2。Output：一种装载方案，没有输出没有解。1. 设定目标函数的限界down=w1，up= ，flag=false(标记是否找到解)2. 计算初始结点1的f(1)=up和g(1)=0，将初始结点插入最大堆H,堆中存储f值为结点键值;3. while (H ) 4. 5. 从H中做DELETEMAX的操作，用p带回相应结点;6. If g(p)=C1 and up-g(p)=C2 then 7. 沿parent指针输出装入第一艘轮船的集装箱，剩余装入第二艘轮船，flag=true，exit (结束程序)；8. Else if g(p)C2 9. if p为叶子结点 then 10. if 堆H为空then 输出没有解, exit (结束程序)；11. else if f(p)down then down=f