7 分支限界法.doc

第七章分支限界法习题1 假设旅行商问题的邻接矩阵如图1所示，试用优先队列式分枝限界算法给出最短环游。画出解空间树的搜索图，并说明搜索过程。43152 图1 邻接矩阵 图2 旅行商问题解答：（较多的错误解答：最后一行，遗漏了返回出发点的最后一段的费用）2 试写出0/1背包问题的优先队列式分枝限界算法程序，并找一个物品个数是16的例子检验程序的运行情况。（具体程序见下页附件及c+源代码，关键是要充分理解分支限界的具体实现思路，自己课下认真推导，真正要理清思路。）3 最佳调度问题:假设有个任务要由个可并行工作的机器来完成，完成任务需要的时间为。试设计一个分枝限界算法，找出完成这个任务的最佳调度，使得完成全部任务的时间最短。解：思路一：1. 搜索过程中的调度时间time；限界函数f； 2. 最佳调度时间besttime；最佳调度序列bestx，其中bestxi=x，表示将第i个任务分配给第x个机器执行。解空间的表示：一个深度为N的k叉树。基本思路：搜索从开始结点（根结点）出发，以DFS搜索整个解空间。当搜索完一条路径，则记录下besttime 和bestx序列,并取此besttime为上界f，开始回溯：（1）如果在节点处的调度时间time不大于当前besttime，则如果该结点不是叶节点，就成为一个活结点，同时变当前的扩展结点；如果该节点是叶节点，则用time更新besttime、记录该序列至bestx序列中，并回溯至上层节点。（2）如果在当前的扩展结点（或叶节点）处timebesttime，则当前扩展结点就成为死结点。此时，回溯至上层结点处，并使这个活结点成为当前的扩展结点。重复回溯，直至找到一个解或全部解。注：此处的初始限界函数f可通过贪心算法等，给出一个更好的初始上界。思路二：将n个任务按照所需时间非递减排序，得到任务序列1，2，3，4.,n，满足时间关系t1t2tn.限界函数：将n个任务中的前k个任务分配给当前k个机器，然后将第k+1个任务分配给最早完成已分配任务的机器，依次进行，最后找出这些机器最终分配任务所需时间最长的，此时间作为分支限界函数，如果一个扩展节点所需的时间超过这个已知的最优值，则删掉以此节点为根的子树。否则更新最优值。优先级：哪台机器完成当前任务的时间越早，也就是所有机器中最终停机时间越早，优先级就越高，即被选作最小堆中的堆顶，作为扩展节点。设taskn用来记录最优的调度顺序每个节点具有信息：Parent：父亲节点，Level：节点所在深度加1，Ctime：运行到当前节点所用时间当levelk时（需要界限函数来剪枝，需要判断优先级），Ctime就是运行到当前状态所用的总时间，Ctime作为优先级函数，即从最小堆中选取Ctime最小的节点优先。当找出第一个解节点时，记录此时的Ctime作为目标函数值，以后生成的节点的Ctime大于该目标函数值时，就可以剪掉该节点，如此下去一直到最小堆为空为止。 上述就是最佳调度问题的分支限界算法。解空间树的节点包括以下信息:Nodeint Pathn; /节点对应的解空间树的路径，即到该节点为止的策略记录int Tk;/在本策略下的每台机器的运行时间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);/初始化fBoot.Tn=0;Boot.Time=0;Boot.Pathn=0; Boot.length=0; /初始化根节点AddHeap(Boot);/根节点加入堆中，堆中元素按照Time值由小到大排序While !Heap.empty() doP=DeleteMinHeap();/P为当前优先级最高的点for i=1 to k do/扩展P的k个子节点X=Newnode(P.Path,P.T,P.length+1);X.PathX.length=i;X.Ti=X.Ti+tX.length;X.Time=max(X.T);if X.length=n then/X为叶节点if X.Timef then/X的执行时间小于已知最优解f=X.Time;/将X设为最优解result=X;endifelse /X为中间节点if X.Timef thenAddHeap(X);endif/X的当前执行时间小于已知最优解则加入堆中，否则剪去endifendforendwhileend BestDispatch 思路三：1先将任务由大到小排序2计算n个任务需要的总时间和平均到k个机器上的时间3将大于平均时间的任务各分配一个机器，找到最大完成时间 4将其他任务顺序安排在一台机器上，如果时间超出最大时间，则把该任务交给下一个机器，下一个任务继续在这台机器上试安排，直到所有任务都不能在小于最大完成时间的情况下安排 5安排下一台机器直到所有任务安排完，6或有可能安排某些任务找不到小于最大完成时间 那么重新扫描各台机器使再加上该任务后时间最小，按此方法安排完所有任务。附件：习题2的c+代码#includeusing namespace std;int *answer;/存储解向量struct Node/活节点表中所存储的节点int level;/节点在解空间树中的深度int tag;/用于输出最优解的各个分量int cw;/当前背包装载量 int cp;/当前背包所获得的价值 float ub; /节点的上界值Node *parent;/父节点指针Node *next; /后继节点指针;class Knapprivate:Node *front;/队列队首Node *bestp;/解节点Node *first;/根节点int *p,*w,n,c,*M;/背包价值、重量、物品数、背包容量、记录大小顺序关系long best;/背包容量最优解 public:Knap(int *P,int *W,int C,int N);/构造函数，用于类的初始化Knap();/析构函数void Sort();float LUBound(int i,int cw,int cp);/计算背包的上界值Node *NewNode(Node *pa,int tagLeftChild,float uub);/生成一个新的节点,tagLeftChild=1生成左节点,tagLeftChild=0生成右节点void AddNode(Node *node);/将节点添加到队列中void DelNode(Node *node);/将节点从队列中删除Node *NextNode(); /取下一个节点void PrintResult();/输出结果void LCKnap();/背包问题求解;Knap:Knap(int *P,int *W,int C,int N) n=N;c=C;p=new intn;w=new intn;M=new intn;for(int i=0;inext=NULL;best=0;bestp=new Node1;bestp=NULL;Sort();Knap:Knap()delete front;delete bestp;delete p;delete w;float Knap:LUBound(int k,int cw,int cp)int remain_c=c-cw; float ub=(float)cp; while(kn&wk=remain_c)remain_c-=wk;ub+=pk;k+;if(klevel=(pa-level)+1;node-tag=tagLeftChild;node-ub=uub;node-parent=pa;node-next=NULL;if(tagLeftChild=1)node-cw=pa-cw+wpa-level;node-cp=pa-cp+ppa-level ;elsenode-cw=pa-cw;node-cp=pa-cp;return node;void Knap:AddNode(Node *node)Node *p=front-next,*q=front;float ub=node-ub;while(p!=NULL)if(p-ubnext=p;q-next=node;break;q=p;p=p-next;if(p=NULL)q-next=node;Node *Knap:NextNode()Node *p=front-next;front-next=p-next;return p;void Knap:Sort()int i,j,k;float temp; for(i=1;in;i+) temp=(float)(1.0*pi/wi);k=0;for(j=1;j=n-i;j+)if(temp1.0*pj/wj)temp=(float)(1.0*pj/wj);swap(pk,pj);swap(wk,wj);swap(Mk,Mj); k=j; void Knap:PrintResult()int i=0;cout最大价值是:best=1;i-) answerMi-1=bestp-tag;bestp=bestp-parent;cout对应的解向量为: ( ;for(i=1;i=n;i+)coutansweri-1 ;cout)parent=NULL;first-next=NULL;first-level=0;first-cw=0;first-cp=0;first-tag=0;ub=LUBound(0,0,0);first-ub=ub;front-next=first;while(front-next!=NULL)nextNode=NextNode();k=nextNode-level;if(k=n-1) if(nextNode-cw+wkcp+pk)best)best=nextNode-cp+pk;bestp=NewNode(nextNode,1,(float)best);if(long)(nextNode-cp)best) best=nextNode-cp;bestp=NewNode(nextNode,0,(float)best);if(kcw+wkcw+wk,nextNode-cp+pk)(float)best)ub=LUBound(k,nextNode-cw+wk,nextNode-cp+pk);AddNode(NewNode(nextNode,1,ub);ub=ub=LUBound(k,nextNode-cw,nextNode-cp);if(ubbest)AddNode(NewNode(ne