贪心算法求解TSP(旅行商问题).ppt

- 贪心算法求解(TSP) 旅行商问题 问题描述 旅行商问题（Traveling Salesman Problem, 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和连接矩阵a 2）定义行、列允许矩阵row[n]={1,…,1}、row[n]={1,…,1} 3）赋初值：s=0,i=0 4）While row[i]=1 5） j=0,m=a[i][0],k=0 6） 找到第一个允许访问的节点a[i][j] 7） 寻找a[i][j~n-1]中的最小元素 8）End while 特殊说明： 程序在访问最后一个节点钱，所访问的行中至少有1个允许访问的节点，依次访问这些节点找到最小即可：在访问最后一个节点后，再次访问，会返回k=0，即实现了访问源节点。所以，各个节点都被访问，且访问路径为一简单回路。 实例演示： 例题： 以4个节点为例，演示算法运行过程（以100表示无大）： 输入连接矩阵： 100 3 9 2 3 100 1 4 9 1 100 7 2 4 7 100 实例演示： 运算过程： (1) (2) (3) (4) 实例演示： 对应连线图： 运行结果： 贪心选择性质(n=2)： 因为旅行商问题是一个典型的NP问题，找不到一个算法能保证在多项式时间内得到最优解。所以无需证明其贪心选择性质，而本算法只要求找到近似解，而在多项式时间内结束。 最优子结构性质(n=2)： 设sn是此问题的最优解，那么可以把它分解为sn=s2+sn-1; 假设存在s’n-1为n-1规模是的最优解，则sns2+s’n-1, 而这与假设矛盾，所以可以得出旅行商问题具有最优子结构性质。 程序实现： 定义数组，节点，函数代码： 程序实现： 主函数代码： 程序实现： 程序实现： 求最短距离函数代码： Thank you !