改进贪心算法

贪心算法很容易陷入局部最优，基本无法找到全局最优解，为了得到更好的解，可以考虑在贪心算法求得解的基础上，对解进行进一步改进，接下来将使用爬山法对贪心算法的解进行改进。

爬山法是一种局部搜索方法，在有一个解决方案的基础上，我们可以对解决方案进行适当地改变，这种操作也称之为领域操作，如果改变后的解决方案优于改变前的解决方案，则保持这种改变，否则做还原操作。爬山法是典型的局部搜索算法，它只接受好的改变，拒绝坏的改变，这有很大的局限性。与之相对应的是模拟退火算法，他以一定的概率接受坏的改变，可以看作一种全局优化算法。总之，使用爬山法虽然不能保证达到最优，但是能在一定程度上对解作出改进。

使用贪心求解TSP问题，与之前整数规划使用的为同一数据。

求解结果为1034，GAP=（1034-937）/ 937 = 10.4%，与贪心算法的18%的GAP相比，还是有了一定的改进。