algorithm - 计算解决难题的最小步数

Question

我正在创建一款游戏，用户会看到 2 套彩色方 block 。为了确保拼图是可解的，我从一组开始，将其复制到第二组，然后将一组中的图 block 交换到另一组中。目前，(这就是我的问题所在)交换次数由用户正在玩的级别决定 - 1 级交换 1 次，2 级交换 2 次，等等。相同数量的交换被用作目标游戏。用户必须通过将一组中的一个图 block 交换到另一组来完成拼图，以使 2 组匹配(按颜色)。只要 2 组匹配，(用户)解决的拼图中的拼贴顺序并不重要。

我遇到的问题是，随着我用来生成拼图的交换次数接近每组中的拼贴数，拼图变得更容易解决。基本上，您可以按照第二组所需的任何顺序从一组中拖动，然后用大量的剩余步骤解决难题。我要做的是在拼完拼图后，计算解决拼图所需的最少步数。同样，这几乎总是少于用于创建拼图的交换数量，尤其是当交换数量接近每组中的拼贴数量时。

我的目标是计算最佳情况，然后给用户一个“软糖系数”(即最小移动次数的 1.2 倍)。解决此步数以下的难题将导致通过该级别。

关于我目前如何配置游戏的一些背景知识:

1 到 10 级:每组 9 个板 block 。 5 种不同颜色的瓷砖。第 11 至 20 级:每组 12 个方 block 。 7 种不同颜色的瓷砖。第 21 至 25 级:每组 15 个板 block 。 10 个不同颜色的方 block 。

不允许在集合内交换。

对于每个级别，将至少有 2 个给定颜色的图 block (已解决的拼图中的每个图 block 一个)。

有没有任何人可以推荐任何类型的算法来计算解决给定难题的最少步数？

Answer 1

解决难题的最少步数本质上是 shortest path从 Unresolved 状态到已解决的状态。您的游戏隐式定义了一个图，其中顶点是合法状态，并且如果存在允许该转换的合法移动，则两个状态之间有一条边。

根据搜索空间的大小，一个简单的 breadth-first search将是可行的，并且会为您提供达到任何给定状态的最少步数。事实上，您也可以通过这种方式生成问题:与其随机移动以到达某个状态并检查其与初始状态的“距离”，不如简单地以广度优先/level-order 探索搜索空间。 ，并在给定的“距离”处为您的谜题选择一个状态。

相关问题

• Rush Hour - Solving the Game
  • BFS用于解决Rush Hour，Java源码

---

备选

如果 搜索空间对于 BFS 来说太大了(我还不确定是不是)，你可以使用 iterative deepening depth-first search反而。它像 DFS 一样节省空间，但像 BFS 一样(累积)级别顺序。尽管节点会被多次访问，但它仍然与 BFS 渐进相同，但需要的空间要小得多。