如果你想解決一個難題，組織往往會有所幫助。例如，您可以將問題分解為幾個部分，然後首先解決較容易的部分。但這種排序是有代價的。您最終可能會花費大量時間來整理這些碎片。
這種困境與計算機科學中最著名的問題之一尤其相關：找到從網絡中給定起點到所有其他點的最短路徑。這就像您每次搬家時都需要解決的問題的升級版：了解從新家到工作地點、健身房和超市的最佳路線。
“最短路徑是一個美麗的問題，世界上任何人都可以處理，”他說。 米克爾·索魯普，哥本哈根大學計算機科學家。
直觀上，更容易找到到達附近目的地的最短路線。因此，如果您想為最短路徑問題設計最快的算法，合理的做法是首先找到最近的點，然後找到下一個最近的點，依此類推。但要做到這一點，你必須反复確定哪個點最接近。您將在進行過程中按距離對點進行排序。任何遵循這種方法的算法都有一個基本的速度限制：你的移動速度不能超過排序所需的時間。
四十年前，設計最短路徑算法的研究人員遇到了這種排序障礙。現在，一組研究人員發明了 一種新算法打破了它。它不排序，而且比任何排序算法都運行得更快。
“作者大膽地認為他們可以打破這個障礙，”他說。 羅伯特·塔爾詹，普林斯頓大學計算機科學家。 “這是一個驚人的結果。”
知識的局限性
為了從數學上分析最短路徑問題，研究人員使用圖形語言，圖形是由線連接的點或節點的網絡。節點之間的每個鏈接都標有一個稱為權重的數字，該數字可以表示該段的長度或遍歷該段所需的時間。任意兩個節點之間通常有多條路徑，最短的路徑是權重之和最小的路徑。給定一個圖和一個特定的“源”節點，該算法的目標是找到到每個其他節點的最短路徑。
這 最流行的最短路徑算法, 我創建了 它由計算機科學家先驅 Edsger Dijkstra 於 1956 年創建，從源頭開始，逐步向外發展。這是一種有效的方法，因為知道到附近節點的最短路徑可以幫助您找到到最遠節點的最短路徑。但由於最終結果是最短路徑的有序列表，因此排序障礙對算法的運行速度設置了根本限制。
