c# - 如何为 1 箱推箱子实现快速最短路径搜索？

Question

在我的一门大学课程（数据结构和算法）中，我们得到了一个基于推箱子游戏的奖励作业：

有一个主要例外：我们只有一个板条箱可以推动我们的目标。

示例输入

8 8
MMMMMMMM
M.....?M
M....TTM
M....TTM
M..!...M
M....+.M
M......M
MMMMMMMM

这里第一行给出了b x h电路板的尺寸 ( )（在本例中为 8 x 8）。后面是h行哦b字符。这些字符的含义如下：.可步行的空间，?目标（gif 中的红点），!板条箱，+是我们的位置。

我们被要求输出拼图的最短解。（请注意，一个谜题可能无法解决。）我们将其输出为 2 行，第一行告诉我们移动了多少，第二行告诉我们正确的路径。例如，这将是：

示例输出

10
WWNNNWNEEE

现在，找到一个有效的算法并不是一个真正的问题。看到我们正在寻找最短路径，并且这个特定图表上的节点本质上是未加权的，我已经实现了广度优先搜索。概括地说，我当前的实现如下所示：

0. Since the maze doesn't change, describe each state as a whole number based on the coordinates 
     of the crate and the player. - This defines a state uniquely and reduces memory costs.
1. Create a dictionary of visited states.
2. Get the input positions of the goal, crate and player.
3. Set up a Queue of move sequences.
4. Pop a move sequence from the Queue.
5. If this move sequence wins the game, go to step 8.
6. Make new move sequences which are copies of the original, each with a different legal move appended.
7. Append these new move sequences to the Queue.
8. Go to step 4
9. Print the output.

这当然是一个相对简单的算法。问题是速度不够快。在最后一个测试用例中，我们被抛出了一个196 x 22类似“关卡”的迷宫，它有一个需要 2300 步的解决方案。我们被要求在 10 秒内解决这个级别，但我的算法需要 10 多分钟。

正因为如此，我有点不知所措。我已经设法将算法的速度提高了 10 倍，但我还有 2 个数量级要走……

因此我为什么要在这里问：是什么让这个算法这么慢，我怎样才能加快它的速度？

标签： c#algorithmperformanceshortest-pathpath-finding

Answer 1

是的，您的全面 BFS 搜索会很慢。您将大量的树搜索花费在完全浪费的动作上，您的玩家在迷宫区域周围翻来覆去无济于事。

改变目标的重点：首先，为箱子解决迷宫，而不是让玩家四处走动。包括将板条箱移近目标点的启发式方法。确保板条箱移动是可能的：每个移动都有一个“从”点可用。

一个初始的启发式方法是通过到目标的原始距离来填充迷宫，从目标开始（我在这里所做的）并增加穿过迷宫的步骤，或者从盒子开始并从那里增加。

MMMMMMMM
M54321?M
M6543TTM
M7654TTM    
M876567M   <== crate is on the farther 6
M987678M   <== player is on the nearer 7
Ma98789M
MMMMMMMM

在这里，您将首先尝试找到合法的推动，以沿着路径 654321? 移动框。您还可以通过对任何方向改变进行惩罚（移动玩家而不推动）来更新此信息。

这些启发式方法将为您提供一个非常好的解决方案上限；然后，您可以回溯决策点以尝试其他路径，始终保持任何位置的“最短解决方案”。

还要跟踪你去过的地方，这样你就不会在位置循环上浪费时间：永远不要重复移动（位置和方向）。

这对你有帮助吗？