-1

我设法用 RNG 蛮力解决了这个问题，即使工作网格是 3x3，也需要大约 4-5 秒才能找到最佳解决方案。

我想知道如何在没有蛮力的情况下生成与蛮力相同的动作。

我将列出 2 个示例和蛮力找到的解决方案。我试图分析解决方案以找出它选择它们的原因，但我什么也想不通。

该游戏通过在两个方向（从左到右）和（从右到左）上使用循环旋转来工作

从左到右循环旋转这样做
If [a, b, c] then [b, c, a]
从右到左循环旋转这样做
If [a, b, c] then [c, a, b]

游戏数据可以这么说（它可以是 1 到 9 的任何排列）
例如
Data = 7, 2, 6, 1, 5, 4, 3, 8, 9

我可以用 8 种不同的方式移动桌子上的棋子。
1）基于行的循环旋转（从左到右）。
2）基于Row的循环旋转（从右到左）。
3) 基于列从上到下。
4) 基于列的自下而上。
现在 5 到 8 不需要 Column 或 Row，因为它们是对角线设置的。
5) 从左上到右下（从左到右）。
6）从左上到右下（从右到左）。
7）从右上到左下（从左到右）。
8) 从右上到左下（从右到左）。

数据加载如下

  • 007 | 002 | 006
  • 001 | 005 | 004
  • 003 | 008 | 009


解决方案蛮力：
1）。[Top-Right] 到 [Bottom-Left]（从右到左）
2）。从下到上，列：0
3)。从左到右，行：1

这是模拟的解决方案

1）。[Top-Right] 到 [Bottom-Left]（从右到左）

  • 007 | 002 | 003
  • 001 | 006 | 004
  • 005 | 008 | 009

2）。从下到上，列：0

  • 001 | 002 | 003
  • 005 | 006 | 004
  • 007 | 008 | 009

3）。从左到右，行：1

  • 001 | 002 | 003
  • 004 | 005 | 006
  • 007 | 008 | 009


这是示例 2，需要 6 步才能解决

  • 009 | 008 | 007
  • 006 | 005 | 004
  • 003 | 002 | 001

解决方法：（6 步）
1）。[Top-Right] 到 [Bottom-Left]（从右到左）
2）。从上到下，列：1
3)。从下到上，列：0
4)。[Top-Left] 到 [Bottom-Right]（从左到右）
5)。从左到右，行：1
6)。从右到左，行：2

所以这是一个非常简单的难题，但找到有效的解决方案并不是一项简单的任务。有人可以指导我正确的方向。

4

2 回答 2

2

与其使用随机数生成器解决方案，不如更有条理。

广度优先搜索(BFS) 易于实施，并保证您找到最佳解决方案。BFS 只是简单地测试当前状态的所有后续状态，然后递归地测试所有这些状态的所有后续状态，直到找到解决方案。更直接地说，BFS 测试解决方案长度为 1 的所有移动，然后测试解决方案长度为 2 的所有移动，等等，直到找到解决方案。

幼稚的实现有多次测试同一位置的下降，但您可以通过存储所有先前的状态及其在搜索中的深度并跳过存储值低于当前深度的任何重复来防止这种情况。BFS 有很多改进，但是为了这个游戏的简单性（只有 9 个！状态），使用更复杂的算法你不会看到太多改进。

于 2013-07-27T22:26:09.080 回答
1

如果您想尝试比 BFS 更好的东西（也许您想毕业到 14 拼图或其他东西），请尝试研究启发式搜索方法，例如 A*（发音为 A-star）。这些算法使用某种规则作为评估哪些路径可能成功的代理。在 A* 的情况下，最坏的情况是它会简化为广度优先搜索。

具有挑战性的部分是想出一个很好的启发式来使用。对于 A*，您需要一个永远不会高估路径的好坏而只会低估路径的启发式方法。因此，您通常可以通过想象最佳情况或放松对问题的限制来提出良好的启发式方法。例如，如果您试图找到从一个点到另一个点的最短路径，那么点之间的直线距离是一个很好的启发式方法。在 8 拼图的情况下，您需要某种指标，随着您越来越接近解决拼图，该指标会逐渐提高。

于 2013-07-31T19:17:36.497 回答