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

编写于一个失眠夜

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

随着“回归自然”的呼声日益高涨，许多人在休闲时越来越多选择了野外爬山等有益身心健康的运动。但我们在爬山时应注意以下几点：

1、强度不宜过大 爬山的强度不宜过大，心率保持在120～140次/分钟，一般每周锻炼3～4次为宜。

2、不渴先喝水 爬山一般选择清晨为好。运动时要注意补充水分，在满足解渴的基础上再适当多饮些水，或者在运动前

10至15分钟饮水400至600毫升，这样就可以减轻运动时的缺水程度了。饮料应选择含有适当糖分及电解度（并最好选择含有维生素C）的，以尽快减轻疲劳感，恢复体力。

3、先热身，后放松 开始爬山锻炼时，切不可一上来就加大运动量，要循序渐进。通常要先做一些简单的热身运动，然后按照一定的呼吸频率，逐渐加大强度，避免呼吸频率在运动中发生突然变化。锻炼结束时，要放松一下，这样才能更好地保护肌群能力，使血液从肢体回到心脏。

4、维生素“热补” 爬山时由于能量与各种营养物质的消耗都比较大，维生素的供给不可缺少，特别应注意每天补充适量的维生素A、维生素B及维生素D。另外，食物应易于消化，少食含粗纤维和易产气的食物（芹菜、韭菜、大豆等），多吃碱性食物蔬菜、水果，海带等。

---