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

贪心算法求解(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规模是的最优解，则sns2+s’n-1,而这与假设矛盾，所以可以得出旅行商问题具有最优子结构性质。程序实现：定义数组，节点，函数代码：程序实现：主函数代码：程序实现：程序实现：求最短距离函数代码：Thankyou!