雙向搜索還是不是？速度考慮

我正在實現一種算法，它必須快速確定2D網格中兩個單元格之間是否存在路徑（對於迷宮式遊戲）。它實際上並不需要提供路徑。該算法運行數千次，所以它必須快速。雙向搜索還是不是？速度考慮

奇怪的是，這兩個單元格非常接近（曼哈頓距離爲2），所以對於大多數合理的迷宮來說，路徑通常是微不足道的。現在我有純粹的廣度優先搜索，但我正在考慮實施雙向變體。當然，問題是，在路徑不存在的情況下，雙向搜索將會失敗較慢，因爲它搜索兩個連接的組件，而不是一個，但是如果存在路徑，它會更快地找到它（可能）。

所以我的問題是，有沒有人有任何雙向搜索的經驗，以及如何在上述情況下的行爲？速度差異實際上是相當邊際的嗎？

來源

2013-10-14 bombax

你是指雙向Dijkstra？ – Kunal

爲什麼不將地圖拆分爲連接的組件，以便搜索可以快速失敗？ –

速度的大部分問題最好通過與典型數據集進行基準比較來解決，除非您更擔心比典型數據更糟糕的情況。 –

迷宮略有不同，每次（不同的細胞由非差強人意每次）

在這種情況下，你可以經常做的節省您的洪水填充（廣度優先）距離更好

。

考慮這樣的迷宮（從+到*），其具有

XXXXXXX 
X+ *X 
X XXX X 
X  X 
XXXXXXX

洪水填充距離

XXXXXXX 
X+123*X 
X1XXX7X 
X23456X 
XXXXXXX

阻斷點Z給出

XXXXXXX 
X+123*X 
X1XXX7X 
X23Z56X 
XXXXXXX

，並且因爲在值Z是4，比最短路徑（3）大，你馬上知道Z不會影響解，沒有進一步的搜索。

另一種情況下，如果在方框Y，

XXXXXXX 
X+1Y3*X 
X1XXX7X 
X23456X 
XXXXXXX

你知道大於2（封端值）的任何距離是不可靠的，並因此需要重新計算這些點。在這種情況下，這意味着重複搜索更長的路徑。但那不會比你無論如何都要貴。簡而言之，如果您進行小的修改，存儲填充距離可以節省時間（以內存爲代價）。

這只是非常一般的建議。例如，我並不是說最好在開始時完全填滿每個單元格。這可能是停止第一次成功更有意義，稍後進一步填補。

換句話說，在搜索過程中緩存內部結果並且對於使緩存無效是聰明的。那麼你可以避免在沒有改變的迷宮區域複製工作的成本。

來源

2013-10-15 00:29:38

直覺如果沒有路徑存在，雙向搜索[1]比單向做更多的工作，一般不成立。如果您的雙向算法被編碼爲在向前和向後搜索的擴展節點之間頻繁地交替（正如它應該那樣），則即使在源和目標之間沒有路徑的情況下，雙向變體也有可能在單向之前返回：假設輸入圖包含2個未連接的組件，例如，V和W;源節點s屬於V，目標節點屬於W; | V | = 1000和| W | = 10。現在，單向搜索必須在其優先級隊列爲空之前擴展所有1000個節點。在雙向搜索中，只有來自W的10個節點和來自V的10個節點將被展開，然後它終止。

[1]Java implementation

來源

2014-03-16 11:04:01 coderodde

我實現了其中的一個，它幾乎增加了一倍我的搜索時間。我沒有在這個雙向搜索中使用bfs的隊列版本，而是使用了Erik D.在他的MIT課程中教授的版本，但是我沒有看到隊列版本會如何改變這種差異。

另一種快速的方法是鏈接切割樹。它們是通常展開樹木的森林，並與動態圖形一起使用。

來源

2015-08-10 19:16:40 mszlazak

雙向搜索還是不是？速度考慮

回答

相關問題