爬山算法（Hill Climbing）解决旅行商问题（TSP）

何为TSP问题？

旅行商问题 TSP（Travelling Salesman Problem）是数学领域中著名问题之一。

• 场景：一个旅行商人需要拜访n个城市
• 条件：要选择一个路径能够拜访到所有的城市，且每个城市只能被拜访一次，最终回到起点
• 目标：求得的路径路程为所有路径可能之中的最小值

TSP问题被证明是NP完全问题，这类问题不能用精确算法实现，而需要使用相似算法。

TSP问题分为两类：对称TSP（Symmetric TSP）以及非对称TSP（Asymmetric TSP）

对称与非对称TSP区别

本文解决的是对称TSP
假设：A表示城市A，B表示城市B，D(A->B)为城市A到城市B的距离，同理D(B->A)为城市B到城市A的距离
对称TSP中，D(A->B) = D(B->A)，城市间形成无向图
非对称TSP中，D(A->B) ≠ D(B->A)，城市间形成有向图

什么情况下会出现非对称TSP呢？

现实生活中，可能出现单行线、交通事故、机票往返价格不同等情况，均可以打破对称性。

何为爬山算法（Hill Climbing）？

爬山算法是一种局部择优的方法，采用启发式方法。直观的解释如下图：

一系列山峰与峡谷的剖面图

爬山算法，顾名思义就是爬山，找到第一个山峰的时候就停止，作为算法的输出结果。所以，爬山算法容易把局部最优解A作为算法的输出，而我们的目的是找到全局最优解B。

如何让算法有更大的可能性搜索到全局最优解B呢？

如下图所示，尽管在这个图中的许多局部极大值，仍然可以使用模拟退火算法（Simulated Annealing）发现全局最大值。

运行result

编写于一个失眠夜

---

菜鸟一枚，欢迎评论区相互交流，加速你我成长•ᴗ•。