魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 17427|回复: 20

“循环变换”的度量化 —— 由《智捉精灵》算法想到的 [复制链接]

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 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
 


~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 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
 
的问题来说,连秒杀的级别都够不上,几近是毫秒杀!
 


使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2018-3-19 18:52:37 |显示全部楼层

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

发表于 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).

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

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2018-3-28 08:56:56 |显示全部楼层
铯_猪哥恐鸣 发表于 2018-3-26 12:44
魔方问题不是被认为是NPC问题,而是被证明为NPC问题。
参考文献:Demaine, Erik D., Sarah Eisenstat, and ...


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

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

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

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

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

~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

发表于 2018-4-6 00:49:31 |显示全部楼层
重叠子问题(Overlapping Subproblems):即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。

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

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

发表于 2018-4-6 00:52:52 |显示全部楼层
我觉得楼主你不妨试着从三阶魔方的<U, R2, F2, D, L2, B2>子群出发,或者<U2, R2, F2, D2, L2, B2>子群出发,看看能有什么新思路。

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

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 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 个均匀分布的可度量“参照点”如何
定位如何找? 这需要大家集思广益了。


使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3923
帖子
2556
精华
6
UID
15558
性别
保密
WCA ID
2008CHEN27
兴趣爱好
理论

魔方理论探索者 国家(地区)纪录(NR) 十年元老

发表于 2018-4-16 01:25:57 |显示全部楼层
本帖最后由 铯_猪哥恐鸣 于 2018-4-16 01:29 编辑
对于魔方的循环变换球面网来说,我们可以先找到 N 个均匀分布的可度量“参照点”,然后分别测出这 N 个“参照点”到待求状态的方位,从而锁定待求状态到初始状态的最少步。


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

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

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

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2018-4-18 09:17:50 |显示全部楼层


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

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




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


~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 15:19

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部