第6章 分支限界法--6.7节 旅行售货员问题课件.ppt

第6章 分支限界法--6.7节 旅行售货员问题课件.ppt

ID:58451087

大小:372.50 KB

页数:12页

时间:2020-09-07

第6章 分支限界法--6.7节 旅行售货员问题课件.ppt_第1页
第6章 分支限界法--6.7节 旅行售货员问题课件.ppt_第2页
第6章 分支限界法--6.7节 旅行售货员问题课件.ppt_第3页
第6章 分支限界法--6.7节 旅行售货员问题课件.ppt_第4页
第6章 分支限界法--6.7节 旅行售货员问题课件.ppt_第5页
资源描述:

《第6章 分支限界法--6.7节 旅行售货员问题课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第6章分支限界法6.7旅行售货员问题6.7旅行售货员问题1.问题描述某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵排列树,从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。基于优先队列式分支限界的旅行售货员问题求解

2、算法解旅行售货员问题的优先队列式分支限界法用优先队列存储活结点表。活结点m在优先队列中的优先级定义为:活结点m对应的子树费用下界lcost。令Minout[i]代表顶点i的最小出边费用。lcost=cc+rcost,其中,cc为当前结点费用,rcost为当前顶点最小出边费用加上剩余所有顶点的最小出边费用和。cc:当前结点费用rcost:顶点最小出边费用和cc:6rcost:1412341234Minout[1]=4Minout[2]=5Minout[3]=5Minout[4]=4图中:如,在扩展顶点D处:当前顶点3的最小出边剩余所有顶点2和4的最

3、小出边Minout[3]+Minout[2]+Minout[4]=14rcost=3优先队列中优先级最大的活结点成为下一个扩展结点。排列树中叶结点所相应的载重量与其优先级(下界值)相同,即:叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值。cc:当前结点费用rcost:顶点最小出边费用和cc:6rcost:1412341234基于优先队列式分支限界的旅行售货员问题求解算法42.算法描述算法开始时创建一个最小堆,用于表示活结点优先队列。要找最小费用旅行售货员回路,选用最小堆表示活结点优先队列。堆中每个结点的优先级是子树费用的下界

4、lcost值。计算每个顶点i的最小出边费用并用minout[i]记录如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法结束。邻接矩阵C基于优先队列式分支限界的旅行售货员问题求解算法,采用限界函数lcost,作为优先级,不断调整搜索方向,选择最有可能取得最优解的子树优先搜索;同时,根据限界函数lcost进行剪枝,剪掉不包含最优解的分支。12341234令s表示结点在排列树中的层次(节点B为第0层)。考虑排列树层次s=n-2的情形,此时当前扩展结点是排列树中某个叶结点的父结点。算法的while循环完成对排列树内部结点的扩展。对于当前扩展结点

5、,算法分两种情况进行处理:第一种情况:邻接矩阵C④如果是,则必须更新当前最优值bestc和当前最优解bestx。B结点为第0层12341234初始时,s=0,x[0]=1,x[1:n-1]={2,3,…,n}x[n-2]x[n-1]if(cc+a[x[n-2]][x[n-1]]+a[x[n-1]][1]

6、的边和一条从顶点x[n-1]到顶点1的边。②如果这两条边都存在,则找到一条旅行员售货回路。③此时,算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。令x记录当前解,s表示结点在排列树中的层次(结点B为第0层)。当扩展结点所处的层次s

7、],x[i])的费用cc和相应的下界lcost。当lcost

8、B结点为第0层12341234因为一旦一个叶结点成为当前扩展结点,剩余活结点的下界值(lcost值),都大于等于当前叶子节点处已找到的回

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。