7+分支限界法

《7+分支限界法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章分支限界法1．假设旅行商问题的邻接矩阵如图1所示，试用优先队列式分枝限界算法给出最短环游。画出解空间树的搜索图，并说明搜索过程。43152图1邻接矩阵图2旅行商问题解答：搜索的过程如下：B{E,F,C,D}E{F,G,H,C,I,D}F{J,G,H,K,C,I,L,D}J{G,H,N,K,C,I,L,M,D}G{H,P,N,K,C,I,L,M,D,O}H{P,N,K,C,I,L,R,M,D,O,Q}P{N,K,C,I,L,R,M,D,O,Q}N{K,C,I,L,R,M,D,O,Q}K{C,I,L,R

2、,V,M,D,O,Q,U}C{I,Y,L,R,V,X,M,D,O,Q,U,W}I{Y,L,R,V,X,Z,M,ZA,D,O,Q,U,W}Y{L,R,V,X,Z,M,ZA,ZB,D,O,Q,U,ZC,W}L{R,V,X,Z,ZD,M,ZA,ZB,ZE,D,O,Q,U,ZC,W}R{V,X,Z,ZD,M,ZA,ZB,ZE,D,O,Q,U,ZC,W}V{X,Z,ZD,M,ZA,ZB,ZE,D,O,Q,U,ZC,W}X{Z,ZD,M,ZA,ZB,ZE,D,O,ZH,Q,U,ZC,W}Z{ZD,M,ZA,ZB,ZE

3、,D,O,ZH,Q,U,ZC,W}ZD{M,ZA,ZB,ZE,D,O,ZH,Q,U,ZC,W}M{ZA,ZB,ZE,D,O,ZH,Q,U,ZC,W}ZA{ZB,ZE,D,O,ZH,Q,U,ZC,W}ZB{ZE,D,O,ZH,Q,U,ZC,W}ZE{D,O,ZH,Q,U,ZC,W}D{O,ZH,Q,U,ZC,W,ZQ,ZR,ZP}O{ZH,Q,U,ZC,W,ZQ,ZR,ZP}ZH{Q,U,ZC,W,ZQ,ZR,ZP}Q{U,ZC,W,ZQ,ZR,ZP}U{ZC,W,ZQ,ZR,ZP}ZC{W,ZQ,ZR,Z

4、P}W{ZQ,ZR,ZX,ZY,ZP}ZQ{ZR,ZZ,ZX,ZY,ZP,ZZA}ZR{ZZB,ZZ,ZX,ZY,ZP,ZZA,ZZC}ZZB{ZZ,ZX,ZY,ZP,ZZA,ZZC}ZZ{ZX,ZY,ZP,ZZA,ZZC}ZX{ZY,ZP,ZZA,ZZC}ZY{ZP,ZZA,ZZC}ZP{ZZA,ZZC}ZZA{ZZC}ZZC{}下面的解答为一典型的错误解答。（注意：此解答，最后一行，遗漏了返回出发点的最后一段的费用）1．试写出0/1背包问题的优先队列式分枝限界算法程序，并找一个物品个数是16的例子检验

5、程序的运行情况。（具体程序见附件，但理解思想是关键）2．最佳调度问题:假设有个任务要由个可并行工作的机器来完成，完成任务需要的时间为。试设计一个分枝限界算法，找出完成这个任务的最佳调度，使得完成全部任务的时间最短。解：思路一：算法执行步骤如下：1．先将任务由大到小排序2．计算n个任务需要的总时间和平均到k个机器上的时间3．将大于平均时间的任务各分配一个机器，找到最大完成时间4．将其他任务顺序安排在一台机器上，如果时间超出最大时间，则把该任务交给下一个机器，下一个任务继续在这台机器上试安排，直到所有任务都不

6、能在小于最大完成时间的情况下安排5．安排下一台机器直到所有任务安排完，6．或有可能安排某些任务找不到小于最大完成时间那么重新扫描各台机器使再加上该任务后时间最小，按此方法安排完所有任务。思路二：将n个任务按照所需时间非递减排序，得到任务序列1，2，3，4…….,n，满足时间关系t[1]

7、的时间超过这个已知的最优值，则删掉以此节点为根的子树。否则更新最优值。接下来采用优先队列分支限界算法。在活节点表中节点的优先级问题。优先级：哪台机器完成当前任务的时间越早，也就是所有机器中最终停机时间越早，优先级就越高，即被选作最小堆中的堆顶，作为扩展节点。设task[n]用来记录最优的调度顺序每个节点具有信息：{Parent：父亲节点，Level：节点所在深度加1，Ctime：运行到当前节点所用时间}当level<=k时（不能用界限函数来剪枝，也不需要判断优先级），由于机器还未装满（即前面的k个任务其实

8、是同时加入的），可以令Ctime=0，当level>k时（需要界限函数来剪枝，需要判断优先级），Ctime就是运行到当前状态所用的总时间，Ctime作为优先级函数，即从最小堆中选取Ctime最小的节点优先。当找出第一个解节点时，记录此时的Ctime作为目标函数值，以后生成的节点的Ctime大于该目标函数值时，就可以剪掉该节点，如此下去一直到最小堆为空为止。上述就是最佳调度问题的分支限界算法。解空间树的节点包括以下信息:Node