分支限界法详解.ppt

《分支限界法详解.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、5分支限界法1学习要点α-β剪枝技术分支限界法的剪枝搜索策略应用范例（1）流动推销员问题（2）单源最短路径问题（3）装载问题；（4）布线问题；（5）0-1背包问题；（6）同顺序加工任务安排问题（7）八数码问题25.1图的广度优先遍历对于图G=(V,E),从任意一点r开始，依次检查所有与r有关联的边(r,a1),(r,a2),…,(r,ak),当上面k条边检查完毕后，再依次检查所有与a1,a2,…,ak相关联的(a1,a11),(a1,a12),…,(a1,a1m),(a2,a21),(a2,a22),…,(a2,a2m)，……，(ak,ak1),(ak,ak2),

2、…,(ak,akm)。依次类推，直到所有的边被检查，即所有顶点均被访问为止。3广度优先搜索的示例广度优先搜索过程广度优先生成树广度优先遍历序列：ABCDEFGHI4广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。为避免重复访问，需要一个辅助数组visited[]，给被访问过的顶点加标记。5图的广度优先搜索算法:templatevoidGr

3、aph::BFS(intv){int*visited=newint[NumVertices];for(inti=0;iq;q.EnQueue(v);//访问v,进队列6while(!q.IsEmpty()){//队空搜索结束v=q.DeQueue();//不空,出队列intw=GetFirstNeighbor(v);//取顶点v的第一个邻接顶点wwhile

4、(w!=-1){//若邻接顶点w存在if(!visited[w]){//若该邻接顶点未访问过cout<

5、术α-β剪枝技术是一种技巧。比如，7根火柴，A、B两人依次从中取出1根或2根，但不能不取，最后一个将取尽的便是赢家。85.3分支限界法通常以广度优先或最小耗费（最大效益）优先的方式，搜索问题的解空间树。可以这样理解：分支定界法与广度优先方法的不同在于，往往不用遍历整个图，而是将不可能得到解或不可能得到最优解的树枝剪掉（即下界估计），从而提高搜索效率。关键：下界估计95.3.1分支限界法的基本思想（1）求解目标：分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（2）搜索方式：以广度优先或以最小耗费优先的方式搜索解空

6、间树。10分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。115.3.2分支限界法示例（1）单源最短路径问题（2）布线问题（3）八数码问题（4）对称流动推销员问题（5）非对称流动推销员问题12例1：单源最短路径问题1.问题

7、描述在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。a=2b=3c=4d=7e=2f=9g=2h=2i=6j=7k=3l=5m=1n=50=8p=2q=1r=2u=313用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。142.算法思想解单源最短路径问题的优先队列式分支限界法用一小顶堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长

8、的结点作为