贪心算法求解TSP旅行商问题ppt课件.ppt_第1页
贪心算法求解TSP旅行商问题ppt课件.ppt_第2页
贪心算法求解TSP旅行商问题ppt课件.ppt_第3页
贪心算法求解TSP旅行商问题ppt课件.ppt_第4页
贪心算法求解TSP旅行商问题ppt课件.ppt_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

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

文档简介

贪心算法求解 TSP 旅行商问题 问题描述 旅行商问题 TravelingSalesmanProblem TSP 有一个推销员 要到n个城市推销商品 他要找出一个包含所有n个城市的具有最短路程的环路 例如给定一个城市和城市间的距离集合 求经过所有城市恰好一次的最短回路 即 给定图G V E W 其中V为顶点集合 V n E为边集合 W为边权函数 求集合 1 2 n 的一个排列使得下式最小 解决思路 借助矩阵把问题转化为矩阵中点的求解 首先构造距离矩阵 任意节点到自身节点的距离为无穷大 在这里我用100来表示无穷大 在第一行找到最小项a 1 j 从而跳到第j行 再找到最小值a j k 从而跳到第k行进行查找 然后构造各行允许数组row n 1 1 各列允许数组colable n 0 1 1 其中1表示允许访问 即该节点未被访问 0表示不允许访问 即该节点已被访问 如果该行或该列不允许访问 则跳过该点访问下一节点 核心算法说明 1 输入节点数n和连接矩阵a2 定义行 列允许矩阵row n 1 1 row n 1 1 3 赋初值 s 0 i 04 Whilerow i 15 j 0 m a i 0 k 06 找到第一个允许访问的节点a i j 7 寻找a i j n 1 中的最小元素8 Endwhile特殊说明 程序在访问最后一个节点钱 所访问的行中至少有1个允许访问的节点 依次访问这些节点找到最小即可 在访问最后一个节点后 再次访问 会返回k 0 即实现了访问源节点 所以 各个节点都被访问 且访问路径为一简单回路 实例演示 例题 以4个节点为例 演示算法运行过程 以100表示无大 输入连接矩阵 100392310014911007247100 实例演示 运算过程 1 2 3 4 实例演示 对应连线图 运行结果 贪心选择性质 n 2 因为旅行商问题是一个典型的NP问题 找不到一个算法能保证在多项式时间内得到最优解 所以无需证明其贪心选择性质 而本算法只要求找到近似解 而在多项式时间内结束 最优子结构性质 n 2 设sn是此问题的最优解 那么可以把它分解为sn s2 sn 1 假设存在s n 1为n 1规模是的最优解 则sn s2 s n 1 而这与假设矛盾 所以可以得出旅行商问题具有最优子结构性质 程序实现 定义数组 节点 函数代码 程序实现 主函数代码 程序实现 程序实现 求最
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论