魔方吧·中文魔方俱乐部

标题: “循环变换”的度量化 —— 由《智捉精灵》算法想到的 [打印本页]

作者: ggglgq 时间: 2018-3-19 18:52:04 标题: “循环变换”的度量化 —— 由《智捉精灵》算法想到的

　　
　　魔方最少步的问题，往往被认为是 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 时间: 2018-3-19 18:52:18

　　
　　《智捉精灵》游戏大家可以在下面的帖子里下载：
　
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 时间: 2018-3-19 18:52:37

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

作者: 铯_猪哥恐鸣 时间: 2018-3-26 12:44:44

本帖最后由铯_猪哥恐鸣于 2018-3-26 12:48 编辑

魔方问题不是被认为是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-28 08:56:56

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

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

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

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

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

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

作者: 铯_猪哥恐鸣 时间: 2018-4-6 00:49:31

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

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

作者: 铯_猪哥恐鸣 时间: 2018-4-6 00:52:52

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

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

作者: ggglgq 时间: 2018-4-8 08:53:10

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

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

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

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

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

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

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

附件: N个均匀的可度量参照点（三维空间）.jpg (2018-4-8 08:52:47, 31.41 KB) / 下载次数 90
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0MzA3fGMzNjlhNTcxfDE3MzI0NTA5OTV8MHww

附件: 循环变换球面网三维空间简易模型.gif (2018-4-8 08:52:30, 266.38 KB) / 下载次数 97
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0MzA2fGJmMWQxMmMyfDE3MzI0NTA5OTV8MHww

作者: 铯_猪哥恐鸣 时间: 2018-4-16 01:25:57

本帖最后由铯_猪哥恐鸣于 2018-4-16 01:29 编辑

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

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

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

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

作者: ggglgq 时间: 2018-4-18 09:17:50

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

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

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

作者: ggglgq 时间: 2018-4-18 09:18:58

本帖最后由 ggglgq 于 2018-4-18 09:20 编辑

2×2 平面魔方态态关系网
http://bbs.mf8-china.com/viewthread.php?tid=153&extra=page%3D1&page=6

2×2 平面魔方的“循环变换球面网”为“正八面体的循环变换球面网”（如图）。

2×2 平面魔方有 4 种操作 U 、 D 、 L 、 R 。
请各位魔友注意，图中 A --> B 箭头表示：从 A 到 B 但还需要整体旋转后才能得到 B 。图中不带箭头的可以互相转换；
但带箭头的是不能互相转换的，转换后还需整体旋转。

我们不妨分别用 U 、 U+ 、 U2 、 U- 表示（D 、 L 、 R 操作同理）：
U 表示操作 U 后不需要再做整体旋转；
U+ 表示操作 U 后再做顺时针整体旋转；
U2 表示操作 U 后再做整体旋转 180 度；
U- 表示操作 U 后再做逆时针整体旋转。

作者: ggglgq 时间: 2018-4-18 09:24:31

0123 魔方的正六面体循环变换球面网
http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=5798

0123 魔方有 3 种基本操作 U 、 L 、 R 。

但为了更好地体现旋转“同态”，我们分别用 U 、 U+ 、 U- 表示（L 、 R 操作同理）：

U 表示操作 U 后不需要再做旋转；
U+ 表示操作 U 后再做顺时针旋转 120 度；
U- 表示操作 U 后再做逆时针旋转 120 度。

0123 魔方的正六面体循环变换球面网

0123循环网.PNG

附件: 0123循环网.PNG (2018-4-18 09:22:04, 109.13 KB) / 下载次数 69
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0NjExfDNhNjNkYzIwfDE3MzI0NTA5OTV8MHww

附件: 0123.PNG (2018-4-18 09:21:39, 12.81 KB) / 下载次数 67
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0NjEwfDZiZjBkZjQzfDE3MzI0NTA5OTV8MHww

作者: ggglgq 时间: 2018-4-18 09:30:19

正十二点四连循环变换球面网
http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=30650

0123双环魔方.PNG

正十二点四连循环变换球面网
正十二点四连循环变换球面网.PNG

附件: 正十二点四连循环变换球面网.PNG (2018-4-18 09:29:46, 106.56 KB) / 下载次数 71
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0NjEzfDJkYmEzMmNmfDE3MzI0NTA5OTV8MHww

附件: 0123双环魔方.PNG (2018-4-18 09:29:34, 27.66 KB) / 下载次数 83
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0NjEyfGI2NGU5ODA1fDE3MzI0NTA5OTV8MHww

作者: 铯_猪哥恐鸣 时间: 2018-4-19 00:02:20

超高维空间的话，你说的是N维欧式空间吗？
还是说你在实际用的时候根本不关心是几维空间，只关心各个状态和状态之间的转换关系？

作者: ggglgq 时间: 2018-4-19 15:28:02

本帖最后由 ggglgq 于 2018-4-19 15:30 编辑

铯_猪哥恐鸣发表于 2018-4-19 00:02
超高维空间的话，你说的是N维欧式空间吗？
还是说你在实际用的时候根本不关心是几维空间，只关心各个状态和 ...

“魔方的循环变换球面网”是一个不以人们对意志为转移的“客观存在”，而“...氏”空间只是一个工具而已。
我还真的对“...氏”空间的这个工具很感兴趣，如果我们能够发明一种比如“铯氏”空间，而“铯氏”空间能够解决魔方
循环变换球面网的最少步数速解问题，那“魔方的循环变换球面网”就是“铯氏”空间的东西。但这并不影响它是还是不是
“欧氏空间”、“法氏空间”、“美氏空间”......

如果我不关心它是几维空间的循环变换球面网，还会屡屡强调“几乎全是超高维空间的东西”吗？！

作者: 铯_猪哥恐鸣 时间: 2018-4-19 19:24:24

不不不，“循环变换球面网”是你提出来的东西，你没有给出精确的定义，只是举了几个例子。你的语境中，“空间”，“维”，“网”，“球面”，可能都和传统意义下的这几个词有着不同的含义。我实在无法通过这几个例子理解你到底要定义一个什么概念。

作者: ggglgq 时间: 2018-4-20 08:52:17

铯_猪哥恐鸣发表于 2018-4-19 19:24
不不不，“循环变换球面网”是你提出来的东西，你没有给出精确的定义，只是举了几个例子。你的语境中，“空间”，“维”，“网”，“球面”，可能都和传统意义下的这几个词有着不同的含义。我实在无法通过这几个例子理解你到底要定义一个什么概念。

这不是个问题，因为“魔方的循环变换球面网”是一个不以人们对意志为转移的“客观存在”，随着人们对“循环变换”
的深入理解，“魔方的循环变换球面网”的概念也会越来越被人们所接受的，到时候总会有人给出一个系统而全面的定义的。

我年龄也大了，思维也跟不上你们年轻人了，只想提出这么个“魔方的循环变换球面网”的概念，让大家对魔方中存在
这么样一个“璀璨的明珠”有一个认识就足矣！（“璀璨的明珠”是否也要定义一下呢？！）

铯一直在纠结“魔方的循环变换球面网”是不是“欧氏空间”的问题，是不是，这并不重要，重要的是能不能解决问题！
既然 “维”、“空间”、“球面”、“网”等这些“欧氏空间”的概念拿来用，至少是可以让人们形象地理解这颗“璀璨的明珠”，
我们为什么不（理解为“欧氏空间”）拿来用用呢？！在一个概念无法给出系统而全面的定义之前，我认为这么做是合理的！

作者: 铯_猪哥恐鸣 时间: 2018-4-20 12:08:09

本帖最后由铯_猪哥恐鸣于 2018-4-20 13:34 编辑

ggglgq 发表于 2018-4-20 08:52
这不是个问题，因为“魔方的循环变换球面网”是一个不以人们对意志为转移的“客观存在”，随着 ...

这真的是个问题。
循环变换球面网是不是客观存在，对不起我不知道，除了你之外我没看到有别人承认它的存在性。不是任何一个概念都客观存在的，比如“大于零的最小实数”这个东西就是不存在的。
我只能从你的描述中看到Cayley graph的概念。如果循环变换球面网就是Cayley graph，那我们之后的讨论全都针对后者就好了，也不用管什么空间了。如果不是，那希望你能指出它们之间的区别，而不是随便提了个轻易看不懂的名词。

你也说了，重要的是能不能解决问题。好，现在请你告诉我，为什么我要相信你定义的概念能解决问题？我看不出它除了哗众取众之外的作用，除非你证明给我看。
请记住，现在的情况是，你要说服别人在你定义的概念上花时间进一步探索。如果你说服不了，对不起我的时间很宝贵，比起虚无缥缈的概念，我更愿意花时间在其他更有前景的方向。

作者: ggglgq 时间: 2018-4-20 15:18:25

铯_猪哥恐鸣发表于 2018-4-20 12:08
这真的是个问题。
循环变换球面网是不是客观存在，对不起我不知道，除了你之外我没看到有别人承认它的存在性。不是任何一个概念都客观存在的，比如“大于零的最小实数”这个东西就是不存在的。
我只能从你的描述中看到Cayley graph的概念。如果循环变换球面网就是Cayley graph，那我们之后的讨论全都针对后者就好了，也不用管什么空间了。如果不是，那希望你能指出它们之间的区别，而不是随便提了个轻易看不懂的名词。

你也说了，重要的是能不能解决问题。好，现在请你告诉我，为什么我要相信你定义的概念能解决问题？我看不出它除了哗众取众之外的作用，除非你证明给我看。
请记住，现在的情况是，你要说服别人在你定义的概念上花时间进一步探索。如果你说服不了，对不起我的时间很宝贵，比起虚无缥缈的概念，我更愿意花时间在其他更有前景的方向。

真是不可救药了！你从在我的这个主题上出现，就摆出这么一副“盛气凌人”的架势，想吵架去找别人去，恕我不奉陪！！！

我的“魔方的循环变换球面网”是不是客观存在，我在 11、12、13 楼的例子已经说明一切了，不容你在这里巧舌诋毁！

我就纳闷了，你一个劲地攻击“魔方的循环变换球面网”，为什么不攻击“魔方的循环变换”呢？！你是和那个叫 pengw 的
换着班地折腾我啊！记得你当初还发帖子支持我的“魔方循环变换理论”，我至今心存感激，你怎么今天变成这个样子了？！

即便是我无法给出“魔方的循环变换球面网”的定义，你也不能肆意否定“魔方的循环变换球面网”的客观存在啊。又即便
“魔方的循环变换球面网”是 Cayley graph ，我在“魔方的循环变换”的架构下，叫它“魔方的循环变换球面网”又有何不妥？！
再者“魔方的循环变换球面网”可以看成是“欧氏空间”的可度量几何体，我用 “维”、“球面”、“网”形象描述又有何不妥？！

我的“魔方的循环变换理论”只需要真正搞学术研究的人来讨论，不需要一个吃现成“定义”动不动就怨天怨地的人来发牢骚。

作者: 铯_猪哥恐鸣 时间: 2018-4-20 15:59:04

本帖最后由铯_猪哥恐鸣于 2018-4-20 16:03 编辑

好的，再见。

我为我在这个帖子上花费的时间表示遗憾，下不为例。

作者: ggglgq 时间: 2018-5-2 09:59:38

本帖最后由 ggglgq 于 2018-5-2 10:01 编辑

循环变换理论概论已经发表10余年，但还有很多人对这个理论尤其是“魔方循环变换球面网”不怎么理解，这是
我对这个理论宣传的不够，例子太少的缘故。我们应该多举例普及循环变换理论，使得大家理解这个理论，并能用它
解决一些问题。

这里给出一个关于“魔方循环变换球面网”的描述性的说明（因暂时还无法证明）：循环变换的几何意义是个
“圆”，魔方的所有循环变换构成一个“球面”，我们称它为“魔方循环变换球面网”（“魔方循环变换球面网”几乎
全是超高维空间的东西）。魔方的所有循环变换都是这个“球面网”上大大小小的“圆”。

这里的“圆”不是指我们平面上的圆，而是指它在某一平面上的投影是一个圆。

http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=109359

利用五一假期，我为大家制作了一些简单实用的“魔方循环变换球面网”的例子，和大家交流探讨共同提高。

过几天我再给出 N 维空间循环变换球面网的存在性及证明，这两天在做相关的准备工作。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)