0

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

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

所以我的问题是，是否有人对双向搜索有任何经验，以及在上述情况下它的表现如何？速度差异实际上是很小的吗？

4

3 回答 3

1

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

[1] Java实现

于 2014-03-16T11:04:01.650 回答
0

迷宫每次都略有不同（每次都会使不同的牢房无法通过）

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

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

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-15T00:29:38.947 回答
0

我实现了其中一个，它几乎使我的搜索时间翻了一番。我没有在这个双向搜索中使用 bfs 的队列版本，而是使用了 Erik D. 在他的 MIT 课程中教授的版本，但我看不出队列版本会如何产生如此大的差异？？？。

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

于 2015-08-10T19:16:40.977 回答