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

Question

在我的一门大学类(class)(数据结构和算法)中，我们得到了一个基于推箱子游戏的奖励作业:

有一个主要异常(exception):我们只有一个 crate 可以插入我们的目标。

Example input

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 中的红点)，! 箱子， + 是我们的位置。

我们被要求输出拼图的最短解。 (请注意，一个谜题可能无法解决。)我们将其输出为两行，第一行告诉我们有多少步，第二行告诉我们正确的路径。例如，这将是:

Example Output

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 个数量级的提升......

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

Answer 1

是的，您的综合 BFS 搜索将缓慢。您将大量的树木搜索花费在完全浪费的移动上，您的玩家在迷宫区域四处乱窜无济于事。

改变目标的重点:首先，解决 crate 的迷宫，而不是让玩家四处奔波。包括将 crate 移近目标点的启发式方法。确保 crate 可以移动:每次移动都有一个可用的“推自”点。

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

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

在这里，您首先要尝试找到合法的插入力，以沿着路径 654321? 移动盒子。您还可以通过对任何方向更改进行惩罚(移动玩家而不插入)来更新此设置。

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

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

这对您有帮助吗？