7 分支限界法.doc

第七章分支限界法习题 假设旅行商问题的邻接矩阵如图1所示，试用优先队列式分枝限界算法给出最短环游。画出解空间树的有哪些信誉好的足球投注网站图，并说明有哪些信誉好的足球投注网站过程。 图1 邻接矩阵 图2 旅行商问题 解答： （较多的错误解答：最后一行，遗漏了返回出发点的最后一段的费用） 试写出0/1背包问题的优先队列式分枝限界算法程序，并找一个物品个数是16的例子检验程序的运行情况。 （具体程序见下页附件及c++源代码， 关键是要充分理解分支限界的具体实现思路， 自己课下认真推导，真正要理清思路。） 最佳调度问题:假设有个任务要由个可并行工作的机器来完成，完成任务需要的时间为。试设计一个分枝限界算法，找出完成这个任务的最佳调度，使得完成全部任务的时间最短。 解：思路一： 1. 有哪些信誉好的足球投注网站过程中的调度时间time；限界函数f； 2. 最佳调度时间besttime最佳调度序列bestx[]，其中bestx[i]=x，表示将第i个任务分配给第x个机器执行。 解空间的表示：一个深度为N的叉树。 基本思路：有哪些信誉好的足球投注网站从开始结点（根结点）出发，以DFS有哪些信誉好的足球投注网站整个解空间。有哪些信誉好的足球投注网站完一条路径则记录下besttime 和bestx[]序列,开始结点就成为一个活结点，同时当前的扩展结点如果在当前的扩展结点处，则当前扩展结点就成为死结点。此时，结点处，并使这个活结点成为当前的扩展结点直至找到一个解或全部解。将n个任务按照所需时间非递减排序，得到任务序列1，2，3，4…….,n，满足时间关系t[1]t[2]……t[n].将n个任务中的k个任务分配给当前k个机器，然后将第k+1个任务分配给最早完成已分配任务的机器，依次进行，最后找出这些机器最终分配任务所需时间最长的，此时间作为分支限界函数，如果一个扩展节点所需的时间超过这个已知的最优值，则删掉以此节点为根的子树。否则更新最优值。优先级：哪台机器完成当前任务的时间越早，也就是所有机器中最终停机时间越早，优先级就越高，即被选作最小堆中的堆顶，作为扩展节点。 每个节点具有信息： {Parent：父亲节点，Level：节点所在深度加1，Ctime：运行到当前节点所用时间} 当level=k时（不能用界限函数来剪枝，也不需要判断优先级），由于机器还未装满（即前面的k个任务其实是同时加入的），可以令Ctime=0， 当levelk时（需要界限函数来剪枝，需要判断优先级），Ctime就是运行到当前状态所用的总时间，Ctime作为优先级函数，即从最小堆中选取Ctime最小的节点优先。当找出第一个解节点时，记录此时的Ctime作为目标函数值，以后生成的节点的Ctime大于该目标函数值时，就可以剪掉该节点，如此下去一直到最小堆为空为止。 上述就是最佳调度问题的分支限界算法。 解空间树的节点包括以下信息: Node{ int Path[n]; //节点对应的解空间树的路径，即到该节点为止的策略记录 int T[k]; //在本策略下的每台机器的运行时间 int Time; //本策略的总执行时间，为每台机器运行时间的最大值 int length; //本节点的深度,即当前处理的作业 } Proc BestDispatch(int n,int k,int t[]) Node Boot,X,P,result; //Boot为根节点，result保存最优解 int f; //记录当前最优解的执行时间 f=n*max(t[]); //初始化f Boot.T[n]={0}; Boot.Time=0; Boot.Path[n]={0}; Boot.length=0; //初始化根节点 AddHeap(Boot); //根节点加入堆中，堆中元素按照Time值由小到大排序 While !Heap.empty() do P=DeleteMinHeap(); //P为当前优先级最高的点 for i=1 to k do //扩展P的k个子节点 X=Newnode(P.Path[],P.T[],P.length+1); X.Path[X.length]=i; X.T[i]=X.T[i]+t[X.length]; X.Time=max(X.T[]); if X.length==n then //X为叶节点 if X.Timef then //X的执行时间小于已知最优解 f=X.Time; //将X设为最优解 result=X; end{if} else //X