4

我正在尝试找到一种方法，在合理的时间和动作中以编程方式解决 24 块滑动拼图。这是我正在描述的难题中已解决状态的示例：

5x5 解决滑动拼图

我已经发现 IDA* 算法可以很好地完成 15 个拼图（4x4 网格）的任务。IDA* 算法能够在非常合理的时间内为任何 4x4 滑动拼图找到最少的移动次数。我对此进行了改编测试 4x4 滑动拼图的代码，并且能够通过使用 PyPy 进一步显着减少运行时间。不幸的是，当此代码适用于 5x5 滑动谜题时，它的运行速度非常慢。我运行了一个多小时，最终放弃了看到它完成，而它在 4x4 网格上只运行了几秒钟。我理解这是因为随着网格的增加，需要搜索的节点数量呈指数增长。但是，我并不是要找到 5x5 滑动拼图的最佳解决方案，而只是寻找接近最佳的解决方案。例如，如果给定谜题的最佳解决方案是 120 步，那么我会对任何少于 150 步并且可以在几分钟内找到的解决方案感到满意。

是否有任何特定的算法可以做到这一点？

4

3 回答 3

5

已经证明，找到 n-Puzzle 的最少移动数是 NP-Complete，请参阅Daniel Ratner 和 Manfred Warmuth , The (n2-1)-Puzzle and Related Relocation Problems , Journal of Symbolic Computation (1990) 10, 111 -137。

Graham Kendall， NP-Complete Puzzles 调查，2008 年回顾了有趣的事实：

  • 8-puzzle可以用A*算法解决；
  • 15-puzzle 不能用 A* 算法解决，但IDA* 算法可以；
  • 使用 IDA* 算法无法在合理时间内生成 24 谜题的最优解。

因此，停止计算以改变方法是正确的做法。

似乎在多项式时间内有一种可用的算法可以找到次优解决方案，请参阅Ian Parberry , Solveving the (n^2−1)-Puzzle with 8/3n^3 Expected Moves , Algorithms 2015, 8(3), 459-465。这可能是您正在寻找的东西。

于 2020-03-22T14:38:51.623 回答
4

IDA* 非常适合 4x4 拼图，因为那只是 16！(20,922,789,888,000) 个可能的状态。一个 5x5 的拼图有 25 个！(15,511,210,043,330,985,984,000,000) 个可能的状态，大 74 万倍。

你需要转换策略。“最简单”的方法是先解决顶行然后左列的谜题，重复，直到你有一个 3x3 的谜题，这可以使用现有技术轻松解决。

解决难题涉及您交替使用的 3 个不同阶段：

  1. 解决第一行（将第 1 - N-2 列的棋子移动到位，然后将 N-1 列的棋子移到 N 列，将 N 列的棋子移到 N 列，但在下一行，完成该行）
  2. 解决左列（将第 2 - N-2 行的棋子移动到位，然后将第 N-1 行的棋子移到第 N 行，将第 N 行的棋子移到第 N 行，但向右移动一列，完成该列）
  3. （剩余 2 行 3 列）：使用 A* 求解余数。

因此，阶段 1 和阶段 2 交替进行，直到您可以运行阶段 3；在解决前 5 个图块（第 1 阶段）后，您解决其他行（第 2 阶段）最左边的 4 个图块，然后是拼图其余部分的顶行（4 个图块，第 1 阶段），然后是左列（ 3 个瓷砖，第 2 阶段），然后解决第 3 阶段。第 1 阶段和第 2 阶段基本相同，只是方向不同，第 2 阶段的第一个瓷砖已经到位。

使用查找表可以轻松解决阶段 1 和阶段 2，无需搜索；您正在移动特定的瓷砖并且不关心其他任何事情：

  • 找到所需的瓷砖
  • 获取瓷砖旁边的间隙（这取决于移动的方向，哪一边最好）
  • 将瓷砖移动到位；有标准的移动可以在任何方向移动瓷砖（垂直或水平移动 5 个，对角线移动 6 个）。

这不会为您提供解决方案的最短路径，但是如果没有状态搜索，问题就会受到严格限制，并且已知最坏的情况。以这种方式解决 5x5 拼图的第一行和第一列最多需要 427 步，下一行和下一列最多需要 256 步。

这个算法最早是由Ian Parberry 在 1995 年的一篇题为A real-time algorithm for the (n2 − 1)-puzzle的论文中描述的。我认为DSolving: a novel and efficient smart algorithm for large-scale slippinguzzles by GuiPing Wang Ren Li仍然描述了一种更有效的查找表方法，但由于该论文尚未免费提供，因此我尚未研究它。

于 2020-03-22T16:03:57.173 回答
1

可能会起作用的两个字符的更改是将启发式方法乘以 2（或其他一些常数）。它不再可接受，但找到的解决方案将在最佳值的 2 倍范围内。这个技巧称为加权 A*/静态加权。

于 2020-03-24T17:33:13.480 回答