我正在尝试开发一个程序来解决 C 中的魔方。我为此使用了回溯技术。这是一个非常漫长的过程，需要大量的迭代，所以我无法解决它。
请给我关于如何更有效地解决这个问题的建议 - 例如其他技术或采用回溯本身。在谷歌中，我找到了很多解决这个问题的捷径，但我不想通过使用捷径来解决这个问题。
问问题
36689 次
5 回答
7
为什么不使用以人为本的解决方案并对此进行编程。
您需要一些模式匹配，但这并不难。（此外还有解决 1000x1000x1000 的程序）。
基本思想是分阶段工作：
- 第一层
- 第二层
- 第三层
对于每一层，您都实现了几个将模式 X 转换为模式 X' 的算法。阶段中的每一步都应该使立方体接近求解。您可以通过向每个模式添加一个值来做到这一点（其中更高的值被赋予更多未解决的立方体）。您还可以添加难度（例如转数），以便您可以根据每个难度的最佳价值增益选择算法（或以最少的转数达到最佳结果）。
这种方法的乐趣在于，您可以根据需要添加新算法并测试它们的使用频率。所以你可以测试每个算法的有用性。
如果您真的想获得这些极客点，请创建一种单独的语言来描述算法和它们正在解决的模式。
于 2011-04-06T08:55:25.983 回答
4
有很多算法可以解决魔方问题，但是，您可以参考这个最优的 http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube
于 2011-04-06T09:03:22.780 回答
1
我不确定我是否理解您的问题以及您所说的快捷方式是什么意思。如果您正在使用某种动态编程方法来解决魔方问题，您需要确保您正在查看足够多的步骤以达到解决方案。我相信，如果您只支持 2 种类型的移动（向右旋转、向上旋转），则在决定每次移动之前，您需要提前 12 步（不确定）以确保解决方案。
如果你正在做这样的事情并且你发现你的内存空间不足，那么请记住，你只需要保留你正在遍历的路径，以便决定正确的解决方案（而不是整个树）。
我成功地使用这种方法解决了 Java 中的魔方，所以 C 应该没有问题（就内存占用而言）。
于 2011-04-06T08:56:55.627 回答
1
魔方的状态空间大小约为 2 65。盲目搜索状态空间的回溯算法可能需要在找到解决方案之前检查大部分状态空间，因此显然简单的回溯算法不会很好地工作。但是，这个问题已经解决了很多次了。参见例如http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf
于 2011-04-07T04:53:38.330 回答
0
如果您不关心所涉及的移动次数，这里有一种拆分状态空间的方法，以便您的蛮力方法起作用。
为假人寻找魔方解决方案
- 首先暴力破解所有rubix方面，但将角落放入位置
- 然后找到让不变的那些方面的移动（例如（fgf-1.g-1）^ 3）。其实两步就够了。要找到它们，请考虑角和非角子立方体所涉及的排列，然后迭代角循环长度的 ppcm 以获得角上的不变性）
- 使用您的回溯算法将角落定位（但它们仍然需要旋转以对齐颜色）
- 找到使同一段上的立方体一起旋转的魔法动作。没有任何动作
于 2011-04-17T13:54:41.563 回答