爬山算法（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 中所提供的数据，此程序大致阐述爬山算法的实现。

编写于一个失眠夜

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

我在百度上找的！～～

简介

爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 属于人工智能算法的一种。

算法：

function HILL-CLIMBING(problem) returns a state that is a local maximum

inputs: problem, a problem

local variables: current, a node

neighbor, a node

current <- MAKE-NODE(INITIAL-STATE[problem])

loop do

neighbor <- a highest-valued successor of current

if VALUE[neighbor]<= VALUE[current] then return STATE[current]

current <- neighbor

算法解释：

从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。

算法优缺点

优点

避免遍历，通过启发选择部分节点，从而达到提高效率的目的。

缺点

因为不是全面搜索，所以结果可能不是最佳。

爬山算法一般存在以下问题：

1）、局部最大：某个节点比周围任何一个邻居都高，但是它却不是整个问题的最高点。

2）、高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。

3）、山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。

其他相关算法

stochastic hill climbing

First-choice hill climbing

Ramdom-restart hill climbing

Simulated annealing search

Local beam search

如果您认为本词条还有待完善，需要补充新内容或修改错误内容，请 编辑词条

《混乱》

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

叫爬山算法。

什么叫爬山算法？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

它的方法是什么？

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

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

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

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

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

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

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

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

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

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

第一个点，

是你要接受随机的一抛，

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

第二个点，

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

你都要努力地展开搜索，

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

这就是爬山算法的精髓。

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

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

人生所有的烦恼、痛苦，

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

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

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

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

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

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

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

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

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

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

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

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

作者  | 樊登

来源  | 笔记侠（ID：Notesman）

---