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

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

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

TSP问题分为两类： 对称TSP （Symmetric TSP）以及 非对称TSP （Asymmetric 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)，城市间形成有向图

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

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

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

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

必要解释详见注释

此处根据经纬度计算城市间距离的公式，请参考 Calculate distance between two latitude-longitude points? (Haversine formula)

此处初始化数据源可以使用 TSPLIB 中所提供的数据，此程序大致阐述爬山算法的实现。

编写于一个失眠夜

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

《混乱》

这本书提到了一个非常有效的算法，

叫爬山算法。

什么叫爬山算法？

（注：爬山算法是人工智能算法的一种，

其原理是把你随机地抛在地球上的一个点，抛在那个点以后，

你就近在最近告租的几公里之内寻找最高点，然后找到最高点之后，

立刻站到这个最高点上去，再在最近的几公里之内寻找最高点。）

用计算机模拟我们的人生，

我们的人生就是那个屏幕上，

现在屏幕中所有的坐标、高度都未知，

然后看看谁能用最快的方法找到这个屏幕上的最高点。

用什么样的方法找到最高点？

全球大量的计算机编程高手开始设计这套逻辑，

有的人沿着边走，有的人直接到中心，有人用交叉、画五角星法……

各种各样的方法，到最后发现，

最优秀、最快能够找到最高点的算法只有一个，

这个算法被称作爬山算法。

它的方法是什么？

就是在整个屏幕上随机一抛，

让这个点落在任何一个地方，然后在能力范围之内搜索，

在能力范围之内尽量找到周围最高的高度，找到最高的高度以后，

以这个最高的高度为圆心再找周围最高的高度，然后依次循环（

找最高点周围的下一个最高点），尽可能地找到最高的高点。

如果你今天特别倒霉，掉到一片沙漠中间，

这个沙漠周围的高度都差不多，没有特别高的高度，那该怎么办？

这胡闷时候需要重启，拿起来随机的一抛，

重启到另外一个地方再找另外的高度。

爬山算法里面有两个核心的点：

第一个点，

是你要接受随机的一抛，

你要接受有不确定性的发生；

第二个点，

是无论命运把你抛到什么地方，

你都要努力地展开搜索，

尽可能地做到最好，尽可能地找到最高的高点。

这就是爬山算法的精髓。

使用爬山算法探索一片屏幕，到最后发现这种方法是最快的。

就是要学会拥抱不确定性。

人生所有的烦恼、痛苦，

都是来自于我们对不确定性的抗拒。

我们希望我们的孩子按照一个模式成长，

我们希望我们的工作按照一个模式发展，

我们希望我们创业做的公司，

能够按照一个节奏安全一个模式发展，

是这些抗拒给我们带来大量的烦恼。

但是实际上你唯一需要做的事，是拥抱不确定性。

当不确定性发生、命运将你随机一抛的时候，

你能够随时裤友弯随地、立刻展开最好的努力，

而不是待在原地拼命地抱怨，

拼命地对标，拼命地去维权，

反而这些东西浪费了我们太多的时间。

作者  | 樊登

来源  | 笔记侠（ID：Notesman）

---