🌘 歷史算法幫助解鎖最短路徑問題突破 | 新聞 | 通訊ACM
➤ 組合技術幫助復興早期算法以解決最短路徑問題
✤ https://cacm.acm.org/news/275684-historic-algorithms-help-unlock-shortest-path-problem-breakthrough/fulltext
一項突破性的組合技術顯示瞭如何復興早期算法，以解決最短路徑問題。這些問題提供了許多應用，從導航到芯片佈局，但當路徑具有負權重時，Dijkstra算法會失效。Bellman-Ford算法可以處理負權重，但效率較低。最近的突破是基於梯度下降的機制，將計算時間降至幾乎線性性能。研究人員還發現，將輸入圖分為低直徑子圖，然後使用價格函數進行重構，可以幾乎完全使用Dijkstra算法進行處理。
+ 這是一個很好的技術突破，可以幫助解決最短路徑問題，並且可以應用於許多領域。
+ 這種技術可能很難實現和理解，但如果能夠成功應用，將會有很大的價值。
#算法 #最短路徑問題 #Dijkstra算法 #Bellman-Ford算法 #線性代數 #梯度下降 #低直徑圖