计算最小移动来解决谜题
我正在创建一个游戏，在这个游戏中，用户将看到两组彩色瓷砖。 为了确保拼图是可以解决的，我从一套开始，将它复制到第二套，然后将拼图从一套交换到另一套。 目前（这是我的问题所在）交换次数取决于用户正在玩的级别 - 1级交换1级，2级交换2级等。交换次数相同时用作目标游戏。 用户必须通过将拼图从一组替换为另一组来完成拼图，以使两组拼图（按颜色）。 只要2组匹配，（用户）解决的拼图中拼贴的顺序就无关紧要。
我遇到的问题是，由于我用来生成拼图的互换次数接近每套拼图的数量，所以拼图变得更容易解决。 基本上，你可以从第一组所需的任何顺序拖动一组，然后用大量的动作解决这个难题。 我期望做的是在完成拼图之后，计算解决拼图所需的最小移动次数。 再次，这几乎总是少于创建拼图的交换次数，特别是当交换次数接近每组中拼贴的数量时。
我的目标是计算最佳案例情景，然后给用户一个“模糊因素”（即最小移动次数的1.2倍）。 在这个步骤下解决难题将会导致关卡的通过。
关于我目前如何配置游戏的一点背景：
级别1至10：每组9个瓷砖。 5种不同颜色的瓷砖。 11到20级：每组12个瓷砖。 7种不同颜色的瓷砖。 等级21至25：每组中有15个瓷砖。 10种不同颜色的瓷砖。
不允许在一组内交换。
对于每个关卡，至少有2个给定颜色的拼图（每个拼图一个拼图）。
有没有人可以推荐任何类型的算法来计算解决给定难题的最小移动次数？
解决谜题的最小步骤基本上是从未解决状态到解决状态的最短路径。 你的游戏隐含地定义了一个图，其中顶点是合法状态，如果有一个合法的移动来启用这个转换，那么两个状态之间就存在一条边。
根据搜索空间的大小，简单的广度优先搜索将是可行的，并且会为您提供达到任何特定状态所需的最少步骤数。 事实上，您也可以通过这种方式产生问题：不是随机移动到达状态并检查其与初始状态的“距离”，只需以广度优先/级别顺序探索搜索空间，然后选择在给定的“距离”为你的谜题状态。
相关问题
替代
如果搜索空间对于BFS来说太大（而且我还不确信它），那么可以使用迭代加深深度优先搜索。 它像DFS一样具有空间效率，但（像BFS一样）（高达）级别顺序。 尽管节点将被多次访问，但它仍然与BFS渐近一致，但需要更多的空间。
我不太了解你描述中的难题，但是解决这类难题通常有用的两个一般想法是回溯和分支和界限。
A *搜索算法。 这个想法是，你有一些衡量位置与解决方案有多接近的度量。 然后，A *是一个“最好的第一”搜索，它在每一步考虑从目前发现的最佳位置移动。 这取决于你是否接近解决方案的某种程度。 （它不一定是准确的，它只是一种启发式指导搜索。）在实践中，它往往比纯粹的广度优先搜索表现得更好，因为它总是以您的亲密评分函数为指导。 但是，如果不了解您的问题描述，很难说。 （一条经验法则是，如果在进行拼图时有一种“进步”的感觉，而不是在最后突然聚集在一起，那么A *就是一个不错的选择。）
链接地址: http://www.djcxy.com/p/40209.html上一篇: Calculate minimum moves to solve a puzzle
下一篇: In the game 2048, what is the biggest theoretical tile?