C++解TSP问题简单方法|次最优算法求解最小哈密尔顿环

C++解TSP问题简单方法|次最优算法求解最小哈密尔顿环

        给出一张无向完全图（如下图所示），六个点分别为L，MC，NY，Pa，Pe，T（六个城市），每两点之间有一条带权边，要求求解一个最优的哈密尔顿环（Optimal Cycle），保证权值总和最小。该问题属于NP-complete问题，此问题有诸多方法求解，比如暴力求解，DP算法，回溯法，DFS（深度优先遍历）算法等等，这里采用一种简便的次最优算法求解思想并附源码及注释。

题意及无向图如下：

 算法思想如下：

         简单归纳为：①初始定义：规定一个初始环Cycle（显然这个环不是最优解）  ②状态更新：在环上任取两点i和j（i和j都不是末结点，j不是起始节点），若取到 与 两边之和小于 与 之和，则新增两边 和 ，删除原C上的两边 和   ③递归优化：优化结束，输出最优解，即最短哈密尔顿回路。

        个人分析算法实现的两个难点在于：①判定条件成立后新的cycle的生成 ②当j为5时，j+1指向的位置不是6，而是cycle的首位0。

       通过分析数学规律发现，删除原边后，新的路径（新的cycle）都是从i到达j后逆时针沿j至i+1位置，再至j+1并顺时针结束，体现在数组上即为数组内下标i+1到j内的元素反转，调用库函数reverse即可（注意起始地址问题）；而对于j为5时j+1指向0的实际情况，使用取余符号%即可化解。

C++程序源码如下：

 

        如果想要输出的结果为"L -> Pa -> Pe -> T ->MC -> NY"，可使用unordered_map mp来存储，这里不做赘述。