争夺魔方的难度有多大?

 
魔方魔方40年来一直是世界上最受欢迎的拼图之一。正如无数书籍中所解释的，已经设计出几种不同的方法来解决它。专业的“ speedcubers”可以在几秒钟内解决。
除了这些惊人的技巧之外，还有许多与魔方有关的有趣的数学问题。立方体的移动包括将六个面之一旋转90度，180度或270度。通过将一系列移动应用于已求解状态，可以获得惊人的43,252,003,274,489,856,000个可能状态。
尽管存在这种复杂性，但在2010年证明，无论初始状态如何，Rubik’s Cube都可以在20步或更短的时间内完成求解。该数字称为“上帝的数字”，因为人类使用的所有已知解决方法通常都比该最佳值使用更多的移动。
但是相反的问题呢：加扰一个已解决的多维数据集需要多少步?乍一看，这听起来比计算上帝的数字容易得多。毕竟，与解决多维数据集不同，加扰无需任何技巧。
类似的问题已成功解决了洗牌问题。一个著名的例子是1990年数学家Dave Bayer和Perci Diaconis对“浅滩混洗”的研究。如果一副纸牌的顺序是随机的，则将其定义为“混合”，每种可能的顺序都有相同的出现概率。拜耳(Bayer)和迪亚科尼斯(Diaconis)表明，七次浅滩混洗是足够的，足以混合标准扑克牌。
去年，数学家对15个难题进行了类似的研究，该难题由一个4×4的正方形组成，里面装有15个滑动瓷砖和一个空白空间。
一个典型的人试图打乱魔方会反复对其执行随机移动。结果产生的随机状态序列是数学家称为马尔可夫链的特殊情况。关键属性是给定当前状态，下一个状态将是什么的概率不取决于任何先前状态。
将马尔可夫链理论应用到多维数据集加扰中，可以得出结论，随着随机移动次数的增加，处于任何一种特定状态的可能性越来越接近1 / 43,252,003,274,489,856,000。数学家称其为“均匀概率分布”，因为每种可能的状态都以相同的概率发生。
经过任意给定的随机移动次数后，多维数据集的状态将是随机的，但其概率分布将不完全均匀。一些州比其他州更可能发生。
令d(t)描述t次随机移动后的概率分布与均匀概率分布有多少不同。随着随机移动次数(t)的增加，d(t)的值将减小。被加扰的立方体对应于小的d(t)。
马尔可夫链蒙特卡洛
在马尔可夫链理论中，d(t)的这种减少称为“混合”。除了卡片改组和拼图加扰之外，马尔可夫链混合理论也有非常严格的实际应用。蒙特卡洛方法是现代科学和工程学中最重要的计算工具之一。就像著名的赌场一样，这种方法从根本上依赖偶然性。本质上，它尝试使用多个随机猜测来近似解决难题。
实际上，马尔可夫链通常用于产生这些随机状态。为了理解这些马尔可夫链蒙特卡罗方法的准确性，关键任务是估计随着t的增加d(t)减少的速度。
口袋立方体
研究标准3x3x3魔方的加扰问题目前是一个引人入胜的未解决挑战。但是，如果我们将注意力转向较小的2x2x2版本(称为“口袋立方体”)，它将变得非常容易管理。
在此立方体中，不存在边缘和中心部分，仅保留了角部分。口袋立方体只有3,674,160个可能的状态，而其上帝的数目只有11个。
在下图中，我们为袖珍立方体绘制了d(t)。经过11次移动后，d(t)仍然非常大，为0.695。产生d(t)值低于0.25(在马尔可夫链理论中通常称为“混合时间”)的t的第一个值为19。经过25次移动后，d(t)为0.092;在移动25时，d(t)为0.092。 50次移动后为0.0012;而100移动后为0.00000017。

 
那么，您应该使用几步来完全打乱一个口袋立方呢?答案取决于您希望d(t)的大小。但是，神的举动不足是不言而喻的。最低限度，一个人应该使用少于19个动作。此处提供了更多详细信息，包括用于计算d(t)的代码。
当然，一旦您对多维数据集进行了打乱，剩下要做的就是再次解决它。