旅行商問題 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 中所提供的數據，此程序大致闡述爬山算法的實現。
編寫於壹個失眠夜
菜鳥壹枚，歡迎評論區相互交流，加速妳我成長。