樊登爬山演算法

㈠ 演算法式和爬山法的區別

爬山演算法是一種簡單的貪心搜索演算法，該演算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。爬山演算法實現很簡單，其主要缺點是會陷入局部最優解，而不一定能搜索到全局最優解。

演算法式：把解決問題的方法一一進行嘗試，最終找到解決問題的答案。特點冊鏈：問題解決的系列搜索，採用試誤州巧孫的方式解決問題，優點：一定可以找到某種解決問題的方法，缺點：耗時耗力。

爬山法與手段目的分析法的區別：

使用爬山法的每一步都在逐漸接近最終目標，不存在中途折回的情況；在使用手段目的分析法時，人們有時為了達到目的，不得不暫時擴大目標狀態與初始狀態的差異，以有利於達到最終目標。

比如，兩兵交戰，若敵我力量懸殊，我軍可採取迂迴戰術曲線救國，先假裝寬咐投降，獲取情報，再一舉反攻。

㈡ 爬山演算法（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 中所提供的數據，此程序大致闡述爬山演算法的實現。

編寫於一個失眠夜

菜鳥一枚，歡迎評論區相互交流，加速你我成長•ᴗ•。