双向搜索与否?速度注意事项

Question

我正在实现一种算法，该算法必须快速确定2D网格中两个单元格之间是否存在路径（对于类似迷宫的游戏）。它实际上不必提供路径。该算法运行数千次，因此必须快速。

奇怪的是，两个细胞彼此非常接近（在曼哈顿距离2以内），所以对于大多数合理的迷宫来说，路径通常是微不足道的。现在我有纯粹的广度优先搜索，但我正在考虑实现双向变体。当然，问题在于，在路径不存在的情况下，双向搜索的失败速度会更慢，因为它搜索两个连接的组件而不是一个，尽管如果路径存在，它会更快地找到它（可能）。

所以我的问题是，有没有人有双向搜索的经验，以及它在上述情况下的行为方式？速度差异实际上很小吗？

Answer 1

如果不存在路径，双向搜索 [1] 比单向搜索更能完成工作的直觉通常并不成立。如果您的双向算法被编码为在向前和向后搜索的扩展节点之间频繁交替（它应该这样做），即使在源和目标之间没有路径的情况下，双向变体也有可能在单向之前返回： 假设输入图包含 2 个未连接的组件， 比如，V和W;源节点属于V，目标节点属于 W;|V|= 1000 和 |W|= 10。现在，单向搜索必须在其优先级队列为空之前展开所有 1000 个节点。在双向搜索中，只有来自 W 的 10 个节点和来自 V 的 10 个节点将被扩展，然后终止。

[1] Java实现

Answer 2

迷

宫每次都略有不同（每次都使不同的单元格无法通过）

在这种情况下，您通常可以通过节省洪水填充（宽度优先）距离来做得更好。

考虑这样的迷宫（从 + 到 *）

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（块值）的距离都是不可靠的，因此您需要重新计算这些点。 在这种情况下，这意味着在较长的路径上重复搜索。 但这并不比你做的贵

。

简而言之，如果要进行小的修改，存储泛洪填充距离可以节省时间（以内存为代价）。

这只是非常笼统的建议。 例如，我并不是说在启动时最好完全填充每个单元格。 也许在第一次成功时停止更有意义，以后再进一步填充。

换句话说，在搜索期间缓存内部结果，并明智地使缓存失效。 然后，您可以避免在迷宫中未更改的区域重复工作的成本。

Answer 3

我实现了其中之一，它几乎使我的搜索时间翻了一番。在这个双向搜索中，我没有使用bfs的队列版本，而是使用了Erik D.在他的麻省理工学院课程中教授的版本，但我看不出队列版本会有什么不同???.

另一种快速的方法是使用链接切割树。它们是通常张开树的森林，并与动态图形一起使用。