當前位置:首頁 » 操作系統 » 樊登爬山演算法

樊登爬山演算法

發布時間: 2023-07-29 14:53:25

演算法式和爬山法的區別

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

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

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

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

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

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

編寫於一個失眠夜

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

熱點內容
android漂亮的listview 發布:2025-03-14 13:40:26 瀏覽:390
android路線規劃 發布:2025-03-14 13:23:22 瀏覽:302
poi瀏覽器島風go緩存 發布:2025-03-14 13:10:24 瀏覽:187
具體可要說存儲在鋼瓶中是因為 發布:2025-03-14 13:00:36 瀏覽:440
汽車空調壓縮機不轉了 發布:2025-03-14 12:55:45 瀏覽:30
安卓和平營地cp怎麼組 發布:2025-03-14 12:55:40 瀏覽:604
時序模式演算法 發布:2025-03-14 12:50:45 瀏覽:203
爐石傳說標准模式多腳本 發布:2025-03-14 12:47:53 瀏覽:210
密碼鎖用密碼打不開是什麼原因 發布:2025-03-14 12:31:25 瀏覽:196
低溫存儲測試 發布:2025-03-14 12:10:22 瀏覽:245