[其他] 演算法Dijkstra被證明是普遍最優

https://www.qbitai.com/2024/10/212282.html 十三 本科經典演算法Dijkstra，證明是普遍最優了：最壞情況性能也最優！ FOCS'24最佳論文 時隔近 70年 ，那個用來解決 最短路徑問題 的經典演算法── Dijkstra ，現在有了新 突破： 被證明具有普遍最優性（Universal Optimality）。 什麼意思？ 這意味著不論它面對多複雜的圖結構，即便在 最壞情況下都能達到理論上的最優性能！ 而這還是學術界 首次 將此概念應用於任何序列演算法。 。 對於Dijkstra演算法，想必很多人肯定不會陌生，畢竟它是每個電腦 本科生必學 的內容 。 而且從它誕生至今，已經在廣泛地應用於我們的日常生活中，例如在 谷歌地圖 、 蘋果 地圖 ，Dijkstra演算法就被用來計算從用戶當前位置到目的地的最優路線。 在電腦網路中，被廣泛應用於 路由協定 中；例如開放最短路徑優先（OSPF）協定就是基 於Dijkstra演算法來計算網路中資料包的最優傳輸路徑。 再如 通訊網路設計 、 機器人路徑規劃 和 物流運輸優化 等領域，也是處處都有它的身 影。 （相關教學可參考：https://www.youtube.com/watch?v=EFg3u_E6eHU） 而這項集結了蘇黎世聯邦理工、CMU、普林斯頓等頂尖高校科研人員之力的研究，一舉讓 這個經典演算法達到了前所未有的高度。 哥倫比亞大學電腦科學家Tim Roughgarden看完論文後直呼： 這也太神奇了，我無法想像還有比這更吸引人的研究。 據悉，這篇論文已經斬獲下週即將舉辦的 理論計算機頂會FOCS 2024 （計算機科學基礎 研討會）的 最佳論文 。 一言蔽之，現在的Dijkstra演算法，已經被證明是解決單源最短路徑問題的「近乎理想」 的方法。 那麼這項研究又是如何證明和優化的呢？ 70年經典演算法新突破 首先，我們先透過一個例子，簡單回顧一下Dijkstra演算法。 如下圖所示，Dijkstra演算法尋找最短路徑的方法，大致可以分為四個步驟： 從起點出發 ：選擇起點A。計算從A到鄰近點的距離，例如到B的距離為1，到C的距離 為5。選擇較短的路徑，即先前往B。 繼續探索 ：從新的點（B）繼續找出鄰近點的距離，並將這些距離加上從A到B的距離 。例如，從A到B的距離是1，B到D的距離是1，因此A到D的總距離為2（1 + 1 = 2）。更新 已知的最短路徑。 記錄新的最短路徑 ：在探索過程中發現較短的路徑時，更新記錄。例如，A到C的原 始距離是5，但經過B和D的路徑到C的總距離是3（1 + 1 + 1 = 3），比原來的距離短，因 此更新A到C的距離為3 。 重複步驟，直到覆蓋所有點 ：演算法繼續遍歷，直到所有節點的最短路徑都被確定 。每次優先選擇距離最短的路徑進行下一步計算，逐步優化到每個點的最短路徑。 最終，Dijkstra演算法可以快速找到網路中從起始點到其他所有節點的最短路徑。 在最初的Dijkstra演算法論文中使用到了一個簡單且關鍵的數據結構—— 堆（Heap） ， 而這就為後來的計算機科學家們留下了改進的餘地。 例如1984年，兩位電腦科學家設計了一個巧妙的堆資料結構，使得Dijkstra演算法在解決 單源最短路徑問題所需的時間上達到了理論極限或「下限」。 從某種特定意義上來說，這個版本的Dijkstra演算法已經可以說是最好的，也是近40年來 的一種「標準」。 而這次的最新論文，研究人員的 突破口 依舊是這個堆資料結構。 因為他們發現，像Fibonacci堆等常用的資料結構雖然在理論上具有較好的最壞情況時間 複雜度（Worst-case time complexity），但在許多情況下未能充分利用圖的局部結構特 性。 這就導致在處理某些類型的圖表時，仍然需要高昂的計算代價。 但如果在1984年設計的堆基礎上加入對最近插入項快速訪問的能力，就可以顯著提升算法 的效率。 為此，研究人員提出了一種全新的堆疊資料結構－具備特殊的 「工作集屬性」（ Working Set Property） 。 所謂「工作集屬性」 ，指的是堆能夠充分利用操作的局部性，從而優先處理最近插入的 元素，降低提取最小元素的成本。 這個概念類似於我們在管理待辦事項時，會優先處理那些剛剛新增的緊急任務，更有效率 地完成工作。 若是用公式化的表述，就如下圖所示。 對於在堆中插入並隨後被提取的任意元素x，其工作集Wx包括了在x被插入後、在x被提取 前插入的所有元素，以及x本身。 https://www.qbitai.com/wp-content/uploads/replace/ce6d76e44dba4992e6de32fe97ecb42c.png 借助這種“工作集屬性”，新設計的堆數據結構能夠顯著提升Dijkstra算法的整體性能， 尤其是在具有局部性特徵的圖上。 也成功地讓Dijkstra演算法具備了普遍最優性，不僅在最壞情況下具有最優性，還能在任 何圖結構上表現出色。 不僅如此，這項工作還提供了 精確的複雜度分析 。 例如，作者證明了Dijkstra演算法在具有工作集屬性的堆上的比較次數是 O(OPTQ(G)+n+max∈WG∣FG,w∣)。 其中，OPTQ(G)是解決距離排序問題的最優演算法所需的比較次數，n是頂點數，∣FG,w∣ 是前向邊的數量。 這也為演算法的效能提供了更精確的界限。 總而言之，這些成果不僅推動了圖演算法的研究，也為實際應用中的演算法設計提供了新 的視角和工具。 喝咖啡時誕生的演算法 關於Dijkstra演算法誕生的故事，其實是始於一次意外的靈感。 1956年，年僅26歲的荷蘭電腦科學家 Edsger Dijkstra 當時正試圖為一台新型電腦ARMAC 編寫一個程序，來展示它的運算能力。 這篇論文介紹了他提出最短的路徑演算法，後來成為了電腦科學中 被引用最多的論文之 一 。 儘管Dijkstra的演算法十分優雅，但當時幾乎沒有電腦科學期刊，發表過程十分困難，最 後他選擇將其發表於新創刊Numerische Mathematik上。 Dijkstra在職業生涯中贏得了極高的聲譽，並於1972年獲得電腦科學領域最負盛名的圖靈 獎。 他不僅在程式語言、作業系統和並發控制等領域做出了許多基礎性貢獻，還以其對程式方 法的深入思考而聞名。 他強調程式的正確性，認為程式應該從一開始就正確地設計，而不是透過調試來達到正確 。 不過同時，Dijkstra的性格也非常獨特，他既被讚賞也被批評，是一位充滿爭議的人物。 他對於電腦科學的教育和研究有著強烈的觀點，常常發表極具挑戰性的言論。 例如，他反對使用goto語句，並在1968年發表了著名的文章Go To Statement Considered Harmful，這篇文章引發了廣泛的爭議，但最終他的觀點得到了普遍認可。 Dijkstra演算法不僅可以計算從起始點到一個目的地的最短路徑，還可以給出從起始點到 所有其他節點的排序，這正是單源最短路徑問題的解。 它的核心思想是不斷探索目前距離最短的路徑，更新每個節點的最短距離，直到所有節點 的距離都確定。 這種演算法的簡潔性和高效性使得它成為經典的路徑規劃工具。 麻省理工學院的電腦科學家Erik Demaine曾評論： 這是一個偉大的演算法，速度非常快，簡單易實現。 但演算法的成功不僅歸功於其核心思想，還離不開資料結構的選擇，在幾十年的發展中， 研究人員不斷改進堆資料結構，使得演算法的整體效能不斷提升。 而這一次，改良堆資料結構，可以說是再次立功了。 論文地址： https://arxiv.org/abs/2311.11793 參考連結： [1]https://www.quantamagazine.org/computer-scientists-built-the-best-way-to-traverse-a-graph-20241025/ [2]https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.253.165.148 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1730032237.A.247.html