算法设计与分析课件 45 旅行商问题_第1页
算法设计与分析课件 45 旅行商问题_第2页
算法设计与分析课件 45 旅行商问题_第3页
算法设计与分析课件 45 旅行商问题_第4页
算法设计与分析课件 45 旅行商问题_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTS旅行商问题旅行商问题在无向带权图G=（V，E）中，结点代表景点，直接到达的景点有边相连，边上的数字代表景点之间的路径长度。找出从出发地开始的一个景点排列，按照这个顺序不重复地走遍所有景点回到出发地，所经过的路径长度最短。旅行商问题（1）定义问题的解空间解的形式为n元组：{x1，x2，…，xi，…，xn}，分量xi表示第i个要去的旅游景点编号，景点的集合为S={1，2，…，n}。因为景点不可重复走，因此在确定xi时，前面走过的景点{x1，x2，…，xi-1}不可以再走，xi的取值为S−{x1，x2，…，xi-1}，i=1，2，…，n。旅行商问题（2）解空间的组织结构问题解空间是一棵排列树，树的深度为n=4。旅行商问题（3）搜索解空间· 约束条件用二维数组g[][]存储无向带权图的邻接矩阵，如果g[i][j]≠∞表示城市i和城市j有边相连，能走通。· 限界条件cl<bestl，cl的初始值为0，bestf的初始值为+∞。cl：当前已走过的城市所用的路径长度。bestl：表示当前找到的最短路径的路径长度。旅行商问题· 搜索过程如果采用普通队列式的分支限界法，除了最后一层外，所有的结点都会生成，普通队列式的分支限界法是不可行的。可以使用优先队列式分支限界法，提高搜索速度。设置优先级：当前已走过的城市所用的路径长度cl。cl越小，优先级越高。从根结点开始，以广度优先的方式进行搜索。根节点首先成为活结点，一次性生成所有孩子结点，判断孩子结点是否满足约束条件和限界条件，如果满足，则将其加入队列中；反之，舍弃。然后再从队列中取出一个元素，作为当前扩展结点，搜索过程队列为空时为止。旅行商问题从1号景点出发，经过所有景点一次且只有一次，求最短路径。旅行商问题旅行商问题（1）时间复杂度最坏情况下，除了最后一层外，有1+n+n(n−1)+…+(n−1)(n−2)…2≤n（n−1）!个结点需要判断约束函数和限界函数，判断两个函数需要O(1)的时间，因此耗时O(n!)，时间复杂度为O(n!)。（2）空间复杂度程序中我们设置了每个结点都要记录当前的解向量x[]数组，占用空间为O(n)，结点的个数最坏为O(n!)，所以该算法的空间复杂度为O(n*n!)。旅行商问题算法优化拓展算法开始时创建一个用于表示活结点优先队列。每个结点的费用下界zl=cl+rl值作为优先级。cl表示已经走过的路径长度，rl表示剩余路径长度的下界，rl用剩余每个结点的最小出边之和来计算。初始时先计算图中每个顶点i的最小出边并用minout[i]数组记录，minsum记录所有结点的最小出边之和。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法立即结束。旅行商问题（1）约束条件用二维数组g[][]存储无向带权图的邻接矩阵，如果g[i][j]≠∞表示城市i和城市j有边相连，能走通。（2）限界条件zl<bestl。zl=cl+rl。cl：当前已走过的城市所用的路径长度。rl：当前剩余路径长度的下界。best

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论