新算法可以更快地找到最短路徑

原來的版本 的 這個故事 出現了 廣達雜誌。

如果你想解決一個難題，它通常有助於組織。例如，它可以將問題分解成多個部分，然後首先處理最簡單的部分。但這種排序是有成本的。您最終可能會花費太多時間來將各個部分按順序排列。

這種困境與計算機科學中最虛擬的問題之一尤其相關：從網絡中的特定起點盡快找到彼此。這就像您每次搬家時都需要解決的問題的一個版本：了解從新家到工作場所、健身房和超市的最佳路線。

“最短路徑是一個美麗的問題，可以與世界上任何人聯繫在一起” 米克爾·托魯普哥本哈根大學計算機科學家。

在內部，應該更容易找到到達附近目的地的最短路線。因此，如果你想為較短疾病的問題規劃最快的算法，從找到最近的點開始，然後是下一個經典點，依此類推似乎是合理的。但要做到這一點，您需要反復了解哪個點最接近。您將在進行過程中按距離對點進行排序。任何遵循這種方法的算法都有一個基本的速度限制：你不能比排序所需的速度更快。

四十年前，研究人員規劃的較短路線算法與這種“障礙排序”相悖。現在，一組研究人員設計出了 打破它的新算法。它的排序和運行速度並不比它製作的任何算法都快。

“作者大膽地相信他們可以打破這個障礙，”他說 羅伯特·塔漢普林斯頓大學計算機科學家。 “這是一個驚人的結果。”

知識的邊界

為了分析較短數學路線的問題，研究人員使用與線連接的語言網絡或節點。節點之間的每個鏈接都通過一個稱為權重的數字突出顯示，該數字可能表示該段的長度或穿過該段所需的時間。兩個節點之間通常有很多條路由，並且盡快將權重添加到較小數量的路由。給定一個圖和一個特定的“源”節點，算法的目標是找到到任何其他節點的最短路徑。

這 最著名的較短路線算法; 發明了 從1956年計算機科學家先驅Edsger Dijkstra開始，他從源頭開始，一步步摸索。這是一種有效的方法，因為了解到附近節點的較短路徑可以幫助您找到更遠的節點的最短路徑。但由於最終結果是較短路線的排序列表，因此排序障礙為算法的運行速度設置了基本限制。