爬山演算法速度

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

編寫於一個失眠夜

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

⑵ 爬山演算法 與A演算法有什麼不同

爬山演算法從當前的節點開始，和周圍的鄰居節點的值進行比較。
A*把所有節點分成2組，一組已訪問，一組未訪問，然後選擇其中最優點加入已訪問組。
爬山演算法速度比A*快，但會舍棄部分最優解。

⑶ 爬山演算法

《混亂》

這本書提到了一個非常有效的演算法，

叫爬山演算法。

什麼叫爬山演算法？

（註：爬山演算法是人工智慧演算法的一種，

其原理是把你隨機地拋在地球上的一個點，拋在那個點以後，

你就近在最近的幾公里之內尋找最高點，然後找到最高點之後，

立刻站到這個最高點上去，再在最近的幾公里之內尋找最高點。）

用計算機模擬我們的人生，

我們的人生就是那個屏幕上，

現在屏幕中所有的坐標、高度都未知，

然後看看誰能用最快的方法找到這個屏幕上的最高點。

用什麼樣的方法找到最高點？

全球大量的計算機編程高手開始設計這套邏輯，

有的人沿著邊走，有的人直接到中心，有人用交叉、畫五角星法……

各種各樣的方法，到最後發現，

最優秀、最快能夠找到最高點的演算法只有一個，

這個演算法被稱作爬山演算法。

它的方法是什麼？

就是在整個屏幕上隨機一拋，

讓這個點落在任何一個地方，然後在能力范圍之內搜索，

在能力范圍之內盡量找到周圍最高的高度，找到最高的高度以後，

以這個最高的高度為圓心再找周圍最高的高度，然後依次循環（

找最高點周圍的下一個最高點），盡可能地找到最高的高點。

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

這個沙漠周圍的高度都差不多，沒有特別高的高度，那該怎麼辦？

這時候需要重啟，告租拿起來隨機的一拋，

重啟到另外一個地方再找另外的高度。

爬山演算法裡面有兩個核心的點：

第一個點，

是你要接受隨機的一拋，

你要接受有不確定性的發生；

第二個點，

是無論命運把你拋到什麼地方，

你都要努力地展開搜索，

盡胡悶可能地做到最好，盡可能地找到最高的高點。

這就是爬山演算法的精髓。

使用爬山演算法探褲友彎索一片屏幕，到最後發現這種方法是最快的。

就是要學會擁抱不確定性。

人生所有的煩惱、痛苦，

都是來自於我們對不確定性的抗拒。

我們希望我們的孩子按照一個模式成長，

我們希望我們的工作按照一個模式發展，

我們希望我們創業做的公司，

能夠按照一個節奏安全一個模式發展，

是這些抗拒給我們帶來大量的煩惱。

但是實際上你唯一需要做的事，是擁抱不確定性。

當不確定性發生、命運將你隨機一拋的時候，

你能夠隨時隨地、立刻展開最好的努力，

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

拚命地對標，拚命地去維權，

反而這些東西浪費了我們太多的時間。

作者  | 樊登

來源  | 筆記俠（ID：Notesman）

⑷ 遺傳演算法、數值演算法、爬山演算法、模擬退火 各自的優缺點

遺傳演算法：其優點是能很好地處理約束，跳出局部最優，最終得到全局最優解。缺點是收斂速度慢，局部搜索能力弱，運行時間長，容易受到參數的影響。

模擬退火：具有局部搜索能力強、運行時間短的優點。缺點是全局搜索能力差，容易受到參數的影響。

爬山演算法：顯然爬山演算法簡單、效率高，但在處理多約束大規模問題時，往往不能得到較好的解決方案。

數值演算法：這個數值演算法的含義太寬泛了，指的是哪種數值演算法，陣列演算法與爬山演算法一樣，各有優缺點。

(4)爬山演算法速度擴展閱讀：

注意事項：

遺傳演算法的機制比較復雜，在Matlab中已經用工具箱中的命令進行了打包，通過調用可以非常方便的使用遺傳演算法。

函數GA：［x，Fval，reason］＝GA（＠fitnessfun，Nvars，options）x為最優解，Fval為最優值，＠Fitnessness為目標函數，Nvars為自變數個數，options為其他屬性設置。系統的默認值是最小值，所以函數文檔中應該加上一個減號。

要設置選項，您需要以下函數：options＝GaOptimset（＇PropertyName1＇，＇PropertyValue1＇，＇PropertyName2＇，＇PropertyName3＇，＇PropertyValue3＇…）通過該函數，可以確定一些遺傳演算法的參數。