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

下载本文档

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

文档简介

1、贪心算法求解贪心算法求解(TSP)(TSP) 旅行商问题旅行商问题- 问题描述旅行商问题（Traveling Salesman Problem, TSP）：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。例如给定一个城市和城市间的距离集合，求经过所有城市恰好一次的最短回路，即；给定图G=(V，E，W)，其中V为顶点集合，|V|=n，E为边集合，W为边权函数，求集合1,2，n的一个排列使得下式最小。解决思路：借助矩阵把问题转化为矩阵中点的求解：首先构造距离矩阵，任意节点到自身节点的距离为无穷大(在这里我用100来表示无穷大)，在第一行找到最小项a1j，从而跳

2、到第j行；再找到最小值ajk，从而跳到第k行进行查找然后构造各行允许数组rown=1,1，各列允许数组colablen=0,1,1，其中1表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已被访问。如果该行或该列不允许访问，则跳过该点访问下一节点。核心算法说明：1）输入节点数n和连接矩阵a2）定义行、列允许矩阵rown=1,1、rown=1,13）赋初值：s=0,i=04）While rowi=15） j=0,m=ai0,k=06） 找到第一个允许访问的节点aij7） 寻找aijn-1中的最小元素8）End while特殊说明：程序在访问最后一个节点钱，所访问的行中至少有1个允许访问的

3、节点，依次访问这些节点找到最小即可：在访问最后一个节点后，再次访问，会返回k=0，即实现了访问源节点。所以，各个节点都被访问，且访问路径为一简单回路。实例演示：例题：以4个节点为例，演示算法运行过程（以100表示无大）：输入连接矩阵：100 3 9 23 100 1 49 1 100 72 4 7 100实例演示：运算过程：(1)(2)(3)(4)实例演示：对应连线图：运行结果：贪心选择性质(n=2)：因为旅行商问题是一个典型的NP问题，找不到一个算法能保证在多项式时间内得到最优解。所以无需证明其贪心选择性质，而本算法只要求找到近似解，而在多项式时间内结束。最优子结构性质(n=2)：设sn是此问题的最优解，那么可以把它分解为sn=s2+sn-1;假设存在sn-1为n-1规模是的最优解，则sns2+sn-1,而这与假设矛盾，所以可以得出旅行商问题具有最优子结构性质。程序实现：定义数组，节点，函数代码：程序实现：主函数代码：程序实现：程序实现：求最短距离函数代码：Than

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

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

最新文档

评论

0/150

提交评论