我正在创建一个游戏,用户将获得2套彩色瓷砖.为了确保拼图是可以解决的,我从一组开始,将其复制到第二组,然后将拼贴从一组交换到另一组.目前,(这就是我的问题所在)交换次数取决于用户正在玩的级别 - 级别1交换1次,级别2交换2次等.相同数量的交换用作目标游戏.用户必须通过将瓷砖从一组交换到另一组来完成拼图,以使2组匹配(按颜色).只要2组匹配,(用户)解决的拼图中的拼贴顺序无关紧要.
我遇到的问题是,随着我用于生成拼图的交换数量接近每组中的拼贴数量,拼图变得更容易解决.基本上,您可以按照第二组所需的顺序从一组拖动,并通过大量移动来解决难题.我想要做的是在完成拼图之后,计算解决拼图所需的最小移动次数.同样,这几乎总是小于用于创建拼图的互换数量,尤其是当互换数量接近每个集合中的拼贴数量时.
我的目标是计算最佳情况,然后给用户一个"软糖因子"(即最小移动次数的1.2倍).在这个数量的移动下解决难题将导致通过级别.
关于我目前如何配置游戏的一些背景知识:
级别1到10:每组9个瓦片.5种不同颜色的瓷砖.级别11到20:每组12个瓦片.7种不同颜色的瓷砖.等级21至25:每组15个瓦片.10种不同颜色的瓷砖.
不允许在一组内交换.
对于每个级别,将存在至少2个给定颜色的图块(在解决的拼图中每个图块一个).
是否有任何类型的算法可以推荐人来计算解决给定拼图的最小移动次数？
解决难题的最小动作本质上是从未解决状态到解决状态的最短路径.你的游戏隐式地定义一个图,其中顶点是法治国家,而且有两种状态之间的边缘,如果有一个合法的举动,使这种过渡.
根据你的搜索空间的大小,一个简单的广度优先搜索是可行的,并且会给你最少的步骤数达到任何给定的状态.事实上,你可以生成问题太这样的:不是做随机移动到一个状态到达,从初始状态检查它的"距离",只是探索广度优先/搜索空间层次顺序,并选择一个为你的谜题指定一个给定的"距离".
如果搜索空间对于BFS而言太大(我还不确定它是),则可以使用迭代深化深度优先搜索.像DFS一样节省空间,但像BFS那样(累积式)级别顺序.尽管节点将被多次访问,但它仍然与BFS渐近相同,但需要更多的空间.