artificial-intelligence - 如何使用 A* 算法实现解锁我的游戏？

Question

我想用java编写一个程序来解决给定状态的“解锁我”游戏（假设块和棋盘的初始状态作为输入给出），我的目标是给出最小的移动次数需要使用 A* 算法解锁红色块。

我正在考虑为这个问题设计一个好的启发式，我想出了我认为是一个很好的曼哈顿距离女巫，但我不知道是否有更好的。我遇到的另一个问题是我不知道如何通过编码找到给定状态的可能下一个状态。我希望在你的帮助下我能在这篇文章中得到好的想法！

如果你不熟悉，这里是游戏的链接：

标签： artificial-intelligence

Answer 1

这个特殊的谜题对人来说很难，但对计算机来说通常并不难。因此，如果您以前没有实现过类似的东西而不是 A*，我建议您使用广度优先搜索或深度优先搜索。

BFS：对于广度优先搜索，数据结构相对容易——您可以使用双端队列，从前面删除并添加到后面。您可能想要检查重复项，这需要像哈希表这样的东西来避免多次生成相同的状态。

DFS：对于深度优先搜索，您将使用深度优先迭代深化。也就是说，您将限制 DFS 最多采取 1 次移动，然后最多 2 次移动，依此类推，直到找到解决方案。这仍然保证了最优解。在 DFS 中您唯一需要做的就是避免将移动返回给您的父级，因为这会使搜索效率大大降低。

生成动作：要生成动作，您需要考虑拼图中的每一块以及它可能移动的四个方向。（上/下/右/左）如果棋子旁边的单元格都是空白的，那么它可以朝那个方向移动。移动通常在数据结构中定义为一个棋子加上一个方向。通常，您可以编写一个返回合法移动列表的函数，然后您可以在搜索过程中应用它们。如果您知道最后一步，那么您可以避免轻松应用相反的移动（因为它将是同一块但方向相反）。

启发式：如果你想使用 A*，每件的曼哈顿距离会很好。如果您想要比这更好的东西，您可以从拼图中移除 2-3 块来解决拼图，并使用更简单拼图的解决距离作为完整拼图的启发式。但是，正如我上面所说，这些谜题通常非常简单，不需要强大的启发式方法来解决它们。