尋路：如何有效檢查路徑是否可行？

Question

我正在使用Dijkstra算法來求解理想路徑。作爲該程序的一部分，該算法被稱爲幾千次。

超過一半的時間路徑是不可能的，迪傑斯特拉需要很長的時間來解決這個問題（在一個小測試中，可能的路徑總共解決了2秒，而不可能的路徑總共需要25個）

因此，我想知道是否有一種方法可以非常有效地檢查在浪費時間與算法之前是否有可能找到2個節點之間的路徑。有沒有非常有效的方法來做到這一點？

感謝， 丹

Answer 1

你運行在同一個圖形中的多個路徑查找？如果是這樣，您需要在圖中保留一組不相交的連續空間。這可以通過以下方式實現：

1. 從每個不成功的路徑確定中保持連續的空格，因爲從起始節點完整的閉合集合;
2. 構建一個數據結構，該數據結構能夠高效搜索一次計算出的連續空間;和
3. 確定開始節點和目標節點是否在相同的已知連續空間中，在兩個不同的連續空間中，還是在每個路徑確定之前未知。

（2）的精確最佳機制與圖的性質密切相關，所以我將其留作另一個問題。

Answer 2

沒有約束，一次性使用

在沒有約束的圖形，該計劃以前從未（甚至之前的部分）看見了，不會再看到。關於您唯一可以做的事情是廣度優先搜索或深度優先搜索。

如果內存有問題，您可以考慮使用增量式深度優先搜索。

您可能會考慮在圖上啓動多個線程以查看不同的分支。您需要進行協調，以便他們不必重複工作，只需擁有一個可以安全地檢查和寫入的併發共享數據結構。在併發的情況下，你可以有一些從頭到尾搜索的線程，以及從頭到尾搜索的其他線程。

在一個包含循環的圖上，您會希望將節點標記爲已訪問，以便不執行無限循環。

約束，一次性使用

想想你的圖表和你的目標。

圖形密集還是稀疏？

是否存在負邊權重？負總和週期？

它遵循梯形法則嗎？

是否有最大距離超過了你不在乎有沒有路徑？

圖形是否非循環？

圖形「簡單」？

通過一些工作，您可能會找到一種比dfs更好的方法來處理圖形。其他時候，您可能能夠以不同的方式構建圖形，從而使dfs更快。有時，優勢可能來自搜索過程中不必存儲太多數據。

限制，多采用

如果它是值得的，你可能會遇到弗洛伊德 - 沃肖爾解決每對節點之間的最短路徑。該算法需要一些時間，但是當您只需執行關鍵部分中最短路徑的查找時可能會有所幫助。

您可以通過在圖形上執行初始dfs，爲連接的組件預先解決問題，而不是預先求解最短路徑。

如果圖表可以更改但不是很激烈，那麼您可能只需修改預先計算的結果，而不是在每次開始時重新開始。

，最後思念

圖形的大小和複雜性是重要的考慮因素。對於大型稀疏圖或樹，小型密集連接圖的最佳算法將會不同。