“循环变换”的度量化 —— 由《智捉精灵》算法想到的

ggglgq

　　
　　魔方最少步的问题，往往被认为是 NPC 问题，从而被“束之高阁”无人问津。
　
　　但我不这么认为，我认为至少对于空间对称的魔方而言，他们的状态构造的网络应该是可度量的，
　
而这个可度量的工具，必然与“循环变换”及其构造的“循环变换球面网”有关。
　
　　如何度量化“循环变换”，我现在还没有一个清晰的思路，主要是对高维空间的度量化不了解。
　
或许，下面几个链接的内容可以引导帮助我们进入度量化“循环变换”的神秘殿堂！
　
http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=34872
　
http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=34840
　
https://www.jaapsch.net/puzzles/hamilton.htm
　

ggglgq

　　
　　《智捉精灵》游戏大家可以在下面的帖子里下载：
　
http://bbs.mf8-china.com/forum.p ... page%3D1&page=4
　
　　对于《智捉精灵》的算法，感兴趣的魔友可以参考
　
http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=241
　
　　也可以先自己按通常思路研究一下。
　
　　我想，如果没有上述帖子的引导，大多数程序员会认为《智捉精灵》算法是一个不比魔方算法简单的
　
NPC 问题。 对于《智捉精灵》的 N 排山洞来说， N 不用很大，比如 N = 10000 ，它的分支数据就
　
远复杂于任何现有魔方！ 如果按通常思路求解， N = 1000 对于计算机来说都是天文数字般的无底洞，
　
令计算机无法在有限的时间(以天为单位)内算出最优解！
　
　　但根据
　
http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=241
　
的“度量化 N 排山洞”求解，却能让这个貌似“NPC 问题”瞬间变成为“O(n)问题”，对于 N = 10000
　
的问题来说，连秒杀的级别都够不上，几近是毫秒杀！
　

ggglgq

　　　
　　当然，《魔方最少步的问题》和《智捉精灵》的算法是不一样的，我这里只是“类比”地让大家思考
　
“魔方最少步的度量化”，比如如何度量化魔方的“循环变换”等来解决魔方最少步问题！
　

铯_猪哥恐鸣

魔方问题不是被认为是NPC问题，而是被证明为NPC问题。
参考文献：Demaine, Erik D., Sarah Eisenstat, and Mikhail Rudoy. "Solving the Rubik's Cube Optimally is NP-complete." arXiv preprint arXiv:1706.06708 (2017).

魔方问题与智捉精灵问题其最本质的区别在于，魔方的最少步求解过程并不存在子问题重叠的特性。

ggglgq

铯_猪哥恐鸣 发表于 2018-3-26 12:44
魔方问题不是被认为是NPC问题，而是被证明为NPC问题。
参考文献：Demaine, Erik D., Sarah Eisenstat, and ...

    感谢 铯 的回复， 不然这个帖子可能会“石沉大海”了！

    冥冥之中总感觉，至少对于空间对称的魔方而言，它是有“规律”的，这个“规律”一旦被发现，
并被用于快速解决魔方最少步，魔方最少步的问题就不再是 NPC 问题了。

    换言之，我的确对那个“证明”持怀疑态度！ 虽然我也想承认 魔方最少步的问题 是 NPC 问题，
这样大家就解脱了。  这不应也不必是我们去考虑或争论的！

    这里需要请教 铯 一下，“子问题重叠的特性”是个什么特性，能举例说明一下吗？ 麻烦占用你
的宝贵时间详细说明一下在 魔方问题 与 智捉精灵问题 的区别。

    当然，有必要的话，另开个主题讨论也可以，我会视若珍宝的！

铯_猪哥恐鸣

重叠子问题（Overlapping Subproblems）：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

智捉精灵每一步的最优解都会作为后续决策的子问题被重复用到。
最少步数求解魔方则不存在这类子问题。
注意，必须是“最少步数求解”，如果是形如二阶段算法之类计算非最优解，那么这是一个已经解决的问题。

铯_猪哥恐鸣

我觉得楼主你不妨试着从三阶魔方的<U, R2, F2, D, L2, B2>子群出发，或者<U2, R2, F2, D2, L2, B2>子群出发，看看能有什么新思路。

第一个子群的大小应该现在的计算机差不多够完整的装下，你可以试着按照你的思路写一个最少步求解器，并和现在已有的求解器做个对比。

ggglgq

    对于三维空间魔方最少步数求解，如果按照 48 同态（亦或 96 同态）的方法进行的话，每一个子问题至少
要被使用 48 x n 次（n 为循环变换的长度）啊。 也可能是我们对重叠子问题的理解有出入。算了，反正《魔方
最少步的问题》和《智捉精灵》的算法是不一样的，讨论这个也没太大意义。


    我感觉利用正六面体三阶魔方的<U, R2, F2, D, L2, B2>子群或者<U2, R2, F2, D2, L2, B2>子群出发来
寻求正六面体三阶魔方最少步的效果不会很大，毕竟二者相差甚远，找找规律还可以。

    我之所以提出度量化“循环变换”的概念，是基于下面的思路：

循环变换球面网三维空间简易模型


N个均匀的可度量参照点（三维空间）



    对于魔方的循环变换球面网来说，我们可以先找到 N 个均匀分布的可度量“参照点”，然后分别测出这 N 个
“参照点”到待求状态的方位，从而锁定待求状态到初始状态的最少步。

    关键的问题是，魔方的循环变换球面网几乎全是超高维空间的东西， N 个均匀分布的可度量“参照点”如何
定位如何找？ 这需要大家集思广益了。

铯_猪哥恐鸣

对于魔方的循环变换球面网来说，我们可以先找到 N 个均匀分布的可度量“参照点”，然后分别测出这 N 个“参照点”到待求状态的方位，从而锁定待求状态到初始状态的最少步。

为了避免无意义讨论，我试着去理解你的各种表述方式和符号。我试着在吧里搜索了一下，发现你提到的几个名词都没有准确定义。我根据你的表述做了一些猜测，并提出了一系列疑问。

1. 【循环变换球面网】是一个图，其中点代表状态，边代表状态之间通过1步转动可以互相转换，对吗？
2. 【参照点】是否是指特定的某个状态？还是别的概念？
3. 假设我们已经找到了N个参照点，那么对于某个待求解的状态，【参照点到待求状态的方位】这个概念是什么意思？在欧氏空间中【方位】是个可以精确定义的概念，但循环变换球面网所在的空间不一定是欧氏空间，【方位】可能不存在。
4. 如何根据【参照点到待求状态的方位】确定待求解状态的最少步？

5. 你提到了3维循环变换球面网的示意图，你想表达的是你将状态集合映射到了3维欧氏空间中的一些点，对吗？还是说你不关心最后具体映射到了3维欧氏空间还是别的空间，只希望表示状态之间的转换关系？

ggglgq

    1、2  两个问题你的理解可能是对的，我在论坛中发过多个主题探讨过。可惜的是经过近十年的岁月，论坛的数次变迁，
我当年的研究成果（图片）很多都不翼而飞了，我还得整理一下那些主题。

    3、4、5 三个问题合并解释一下：
    很多东西都是设想的，还没有具体思路不成体系，因此也就没给出相关名词（亦或不准确的概念）的定义。  我在 8 楼也
特地说明了：
    魔方的循环变换球面网几乎全是超高维空间的东西， N 个均匀分布的可度量“参照点”如何定位如何找？ 这需要大家
集思广益了。




    为了让大家更好地了解 8 楼的不成体系的想法，我把以前发过的几个构成三维空间循环变换球面网的“魔方”及其对应的三维
空间循环变换球面网再展示给大家看看。  再次强调一下： 魔方的循环变换球面网几乎全是超高维空间的东西，这几个三维空间的
循环变换球面网是凤毛麟角的特特例！ 之所以举三维空间的例子，是为了让大家对比地抽象理解那些高维空间的循环变换球面网！！！