7 分支限界法

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

1、第七章分支限界法习题1．假设旅行商问题的邻接矩阵如图1所示，试用优先队列式分枝限界算法给出最短环游。画出解空间树的搜索图，并说明搜索过程。43152图1邻接矩阵图2旅行商问题解答：（较多的错误解答：最后一行，遗漏了返回出发点的最后一段的费用）1．试写出0/1背包问题的优先队列式分枝限界算法程序，并找一个物品个数是16的例子检验程序的运行情况。（具体程序见下页附件及c++源代码，关键是要充分理解分支限界的具体实现思路，自己课下认真推导，真正要理清思路。）2．最佳调度问题:假设有个任务要由个可并行工作的机器来完成，

2、完成任务需要的时间为。试设计一个分枝限界算法，找出完成这个任务的最佳调度，使得完成全部任务的时间最短。解：思路一：1.搜索过程中的调度时间time；限界函数f；2.最佳调度时间besttime；最佳调度序列bestx[]，其中bestx[i]=x，表示将第i个任务分配给第x个机器执行。解空间的表示：一个深度为N的k叉树。基本思路：搜索从开始结点（根结点）出发，以DFS搜索整个解空间。当搜索完一条路径，则记录下besttime和bestx[]序列,并取此besttime为上界f，开始回溯：（1）如果在节点处的调度

3、时间time不大于当前besttime，则如果该结点不是叶节点，就成为一个活结点，同时变当前的扩展结点；如果该节点是叶节点，则用time更新besttime、记录该序列至bestx序列中，并回溯至上层节点。（2）如果在当前的扩展结点（或叶节点）处time>besttime，则当前扩展结点就成为死结点。此时，回溯至上层结点处，并使这个活结点成为当前的扩展结点。重复回溯，直至找到一个解或全部解。注：此处的初始限界函数f可通过贪心算法等，给出一个更好的初始上界。思路二：将n个任务按照所需时间非递减排序，得到任务序列1

4、，2，3，4…….,n，满足时间关系t[1]

5、点具有信息：{Parent：父亲节点，Level：节点所在深度加1，Ctime：运行到当前节点所用时间}当level<=k时（不能用界限函数来剪枝，也不需要判断优先级），由于机器还未装满（即前面的k个任务其实是同时加入的），可以令Ctime=0，当level>k时（需要界限函数来剪枝，需要判断优先级），Ctime就是运行到当前状态所用的总时间，Ctime作为优先级函数，即从最小堆中选取Ctime最小的节点优先。当找出第一个解节点时，记录此时的Ctime作为目标函数值，以后生成的节点的Ctime大于该目标函数值时

6、，就可以剪掉该节点，如此下去一直到最小堆为空为止。上述就是最佳调度问题的分支限界算法。解空间树的节点包括以下信息:Node{intPath[n];//节点对应的解空间树的路径，即到该节点为止的策略记录intT[k];//在本策略下的每台机器的运行时间intTime;//本策略的总执行时间，为每台机器运行时间的最大值intlength;//本节点的深度,即当前处理的作业}ProcBestDispatch(intn,intk,intt[])NodeBoot,X,P,result;//Boot为根节点，result保

7、存最优解intf;//记录当前最优解的执行时间f=n*max(t[]);//初始化fBoot.T[n]={0};Boot.Time=0;Boot.Path[n]={0};Boot.length=0;//初始化根节点AddHeap(Boot);//根节点加入堆中，堆中元素按照Time值由小到大排序While!Heap.empty()doP=DeleteMinHeap();//P为当前优先级最高的点fori=1tokdo//扩展P的k个子节点X=Newnode(P.Path[],P.T[],P.length+1);

8、X.Path[X.length]=i;X.T[i]=X.T[i]+t[X.length];X.Time=max(X.T[]);ifX.length==nthen//X为叶节点ifX.Time