我正在创建一个游戏，向用户展示2套彩色瓷砖。为了确保拼图是可解决的，我从一组开始，将其复制到第二组，然后从一组切换到另一组。当前，(这就是我的问题所在)交换数量由用户所玩的级别决定-1个级别交换1个级别，2个级别交换2个级别，依此类推。相同的交换数量被用作目标游戏。用户必须通过将一个图块从一组替换为另一组以使2组匹配(按颜色)来完成拼图。只要(两组)匹配，(用户)解决的难题中的图块顺序就无关紧要。
我遇到的问题是，随着我用来生成拼图的交换次数接近每个集合中的瓦片数，拼图变得更容易解决。基本上，您可以按照第二组所需的任何顺序从一组拖出，并通过向左移动来解决难题。我要做的是在完成拼图后，计算解决拼图所需的最小移动数。同样，这几乎总是少于用于创建难题的交换数量，尤其是当交换数量接近每个集合中的图块数量时。
我的目标是计算最佳情况，然后为用户提供一个“忽悠系数”(即最小移动次数的1.2倍)。在此步数下解决难题将导致通过关卡。
关于我目前如何配置游戏的一些背景知识:
1至10级:每组9个图块。 5种不同颜色的瓷砖。
11至20级:每组12个磁贴。 7种不同颜色的瓷砖。
21至25级:每组15个磁贴。 10种不同颜色的瓷砖。
不允许在集合中交换。
对于每个级别，将至少有2个给定颜色的图块(已解决难题中的每组1个)。
有没有人会建议您计算出解决给定难题的最小移动次数的算法？
最佳答案
解决难题的最小 Action 实质上是从未解决状态到已解决状态的shortest path。您的游戏隐式定义了一个图，其中的顶点是合法状态，如果有合法的移动可以实现过渡，则两个状态之间会存在一条边。
根据搜索空间的大小，一个简单的breadth-first search将是可行的，并且将为您提供达到任何给定状态的最少步骤。实际上，您也可以通过这种方式产生问题:与其进行随机移动以到达一个状态并检查其与初始状态的“距离”，不如简单地在宽度优先/level-order中探索搜索空间，然后在处选择一个状态。给你的难题一个给定的“距离”。
相关问题
选择
如果对于BFS而言搜索空间太大(并且我尚未确信是这样)，则可以使用iterative deepening depth-first search代替。它像DFS一样节省空间，但(像)BFS一样(累加)是层级的。即使节点将被访问很多次，它在渐近性上也与BFS相同，但是需要更多的空间。