魔方吧·中文魔方俱乐部

标题: 【原创】东方说：列出2阶全部态只需要几十MB！ [打印本页]

作者: haohmaru 时间: 2009-11-5 17:06:45 标题: 【原创】东方说：列出2阶全部态只需要几十MB！

考虑这些的起因是想列出二阶全部的态
那就必然会用到计算机
用程序计算的话肯定要给二阶的状态编码
包括状态编码和转动编码
这样不但方便计算、储存，而且便于校验重复态和统计数据

二阶没有中心和棱，只有8个角
而且每个角都是唯一的
所以只要捏住一个角，比如BLD，通过RUF三个面的转动就可以达到任何状态
并且不会有遗漏的态
因此，只需要给7个角编码就可以了

又因为是通过固定一个角，转动其他角来实现状态转换的
所以其他7个角中，只要确定6个角的位置和方向，最后一个角肯定也是确定的
于是，在我的这套系统里
只需要给6个角编码就可以唯一表示二阶的某个态了

初步想法是用123456编码位置，然后再编码颜色
后来想到了魔方的配色问题
只需要给颜色编码（白=1，黄=2，3。。。6），按某一顺序（顺时针or逆时针）的颜色表示角块
就可以唯一确定角块的位置了，同时方向也自然通过颜色表示了！

又是因为配色的关系，只需要确定顺时针（或逆时针）的两个颜色
就可以知道第三个颜色了！
举例：某角块顺时针是“黄绿x”那x肯定是红色

1~6的二进制分别是：001、010、011、100、101、110
那么表示二阶一个角就是一个六位的二进制数（两个颜色）
刚才说了表示二阶某个太只需要确定6个角
那就是36Bit，也就是4.5Byte（字节）

就算它5字节吧
那1kb可以表示二阶的200个态
1mb可以表示200000多个态
二阶总共400多万个状态，就算他500万，
也不过是25Mb

（楼下更新：如何用程序列出二阶的全部状态表）

作者: haohmaru 时间: 2009-11-5 17:07:19

接下来说说如何用计算机程序实现“列举出二阶魔方的全部状态”
状态编码已经说过了
现在介绍一下我的思路，关于“如何实现转动编码”

我的状态转换系统里只有RUF三个面的9种转动：
R、U、F、R'、U'、F'、R2、U2、F2

刚才说了每个状态是用6个角的颜色表示，每个角用2个颜色
但是在计算过程中每个角还是需要用3个颜色表示的，这样便于推导转动后的编码

========================================

【举例】转动R的编码转换：
R的转动实际上就是右边四个角块进行了位置轮换
用我的编码方式来说，就是RUF的三个颜色编码，变成了RUB的颜色编码，并且转换了一下顺序
其他3个角块同样
只需要简单的语句就可以给9种转动进行编码转换定义了

========================================

计算状态转换完成之后，进行重复状态校验
这步很容易，
首先去掉每个角块每个颜色的第三位编码，用转换后状态编码去校对已经存在的状态编码
如有重复，就删除此状态，进入下一步骤
如果没有重复，就进行储存

储存的时候可以给列表分类：
0步态=还原态
1步态=（状态编码。。。。）（状态数量=9）
2步态=（状态编码。。。。）（状态数量=？？）
3步态=。。。
。。。。
以此类推

直到进行到了n步态
在计算n+1步态的时候，发现经过9种转动的结果都是重复的态
那么n就是二阶魔方的最远步数
n步态对应的几种状态，就是二阶的最远态
最远态的数量自然也就出来了

列出二阶全部态可以得到以下精确结果：
二阶最远步数是多少？
最远态有几种？分别是什么情况？（直接根据编码就能复制出来）
二阶每个步态有多少种？分别是什么？
当然，二阶总共有多少种状态也被准确的列出来了！

[ 本帖最后由 haohmaru 于 2009-11-5 17:25 编辑 ]

作者: haohmaru 时间: 2009-11-5 17:08:14

给楼下的理论达人们留个地儿。。。。。

作者: ursace 时间: 2009-11-5 17:21:46 标题: 第一句就错了

原帖由 haohmaru 于 2009-11-5 17:06 发表
考虑这些的起因是想列出二阶全部的态
那就必然会用到计算机

其实手写也可以

作者: kexin_xiao 时间: 2009-11-5 17:51:44

占楼仔细学习一下，理论问题以学习为主

作者: noski 时间: 2009-11-5 18:43:05

原帖由 ursace 于 2009-11-5 17:21 发表

其实手写也可以

这句话来头可就大了。。

作者: doris5200 时间: 2009-11-5 18:49:57

占个前排好学习达人们的理论

作者: K_daSh 时间: 2009-11-5 19:06:50

这有点深奥，数学问题呀

作者: william_khs 时间: 2009-11-5 19:25:45

考慮二階魔方共有3674160個狀態，
假如要完整儲存整個魔方狀態，
1個狀態就需要 8個byte
而二階魔方的所有狀態共佔用(3 674 160 x 8byte)=29 393 280byte = 28.03mb(取至小數點後兩個位)

當然，要簡化它的話也不是沒有方法，
簡單的說就是利用魔方的狀態有限制，就像二階不能單單一隻角翻色

作者: raka 时间: 2009-11-5 19:46:05

努力学习，需要时间领会

作者: Cielo 时间: 2009-11-5 23:30:19

记得以前G老师发过一个程序的，可以列出所有的最远态。

隐约记得是11或者12步吧~

作者: conwood 时间: 2009-11-6 00:34:54

不太明白你想做什么，是想用一种格式存储二阶魔方的所有状态，然后通过一个程序来读取这种格式的数据，最终列出所有状态吗？
这样的话，存储可以不需要任何状态，只要写个程序把所有状态列举出来就行了啊。

原帖由 haohmaru 于 2009-11-5 17:06 发表
考虑这些的起因是想列出二阶全部的态
那就必然会用到计算机
用程序计算的话肯定要给二阶的状态编码
包括状态编码和转动编码
这样不但方便计算、储存，而且便于校验重复态和统计数据

二阶没有中心和棱，只有8个 ...

作者: haohmaru 时间: 2009-11-6 08:51:08

原帖由 conwood 于 2009-11-6 00:34 发表
不太明白你想做什么，是想用一种格式存储二阶魔方的所有状态，然后通过一个程序来读取这种格式的数据，最终列出所有状态吗？
这样的话，存储可以不需要任何状态，只要写个程序把所有状态列举出来就行了啊。

计算机只认识两个数：0和1

作者: pengw 时间: 2009-11-6 10:10:08

对二阶来说,应说明每一个块的身份,位置,色向:

8个块的位置最少要:3个位
8个块的身份最少要:3个位
每个块的色向最少要:2个位

因此,一个二阶状态要64个位，8个字节

所有状态所须容量=8!*3^7/24*8=29293280字节=29.29MB

如果要用色向来标志块的身份则六个颜色须要三个位，每个块三个色，则需要9个位，则每个状态须要：96个位，12字节，约是前者的1.5倍

作者: pengw 时间: 2009-11-6 10:20:12

对于3674160个二阶状态，编个程序穷举也要不了一分钟，这种事连小学生都会做，何须ggglgq费力

作者: erictrui 时间: 2009-11-6 10:29:28

太深奥了…………看都看不懂

作者: 铯_猪哥恐鸣 时间: 2009-11-6 14:10:44

表示每个二阶魔方的状态至少需要22bit，总计需要：22*3674160bit=10103940byte<=10M，理由不解释。具体实现的话，如果要求运算速度不慢多少，我感觉以我现在的能力我只能做到每个状态存30bit，总计约13.14M。

作者: william_khs 时间: 2009-11-6 16:56:02 标题: 回复 14# 的帖子

對於pengw版主的這句 : "所有状态所须容量=8!*3^7/24*8=29293280字节=29.29MB"，小弟想補充一點，
就是1Mb=1024KB,1KB=1024byte=1024 字節

作者: pengw 时间: 2009-11-6 20:11:01

谢谢楼上兄弟的精细,兄弟可能不了解IT这一行的习惯，行内就习惯这种快捷的近拟计算，不过，你的一个二阶状态用4.5字节就表达了，你能不能举一个用位来表示的实例，我觉得好像不可能，4.5个字节即将36个位，分给八个块，都分不匀，你认为二阶每个块在状态表达不对等？就算你说的5个字节，则5位/块，位置至少了要占三位，余下二位只够表示色向三个状态（如果你要用6个色的编码，位数差得更远），已经没有其它位表示块的身份，也就是说，你的5节字只能说明每个位置是什么色向，根本无法区分块的身份，难到你表达的状态不关心置换？希望看到一个完整的40位状态实例。

[ 本帖最后由 pengw 于 2009-11-6 20:42 编辑 ]

作者: william_khs 时间: 2009-11-6 23:28:55

IT需要的就只是近似值吧? 也對...
不過我們數學的就要求高精度....

對於樓主的見解我還未能有一套完整的思路可以表示贊同或反對。
首先嘛，假如要將整個2階魔方的狀態複製、轉譯成資料檔，
共需6*4=24 byte...(還是bit....?)，總共需56.06mb來儲存所有狀態。
其中有些24byte這個數字所代表的是6面4格不同的顏色，
但可以被簡化。
二階魔方的特性為:
1. 每兩角塊可作任意交換
2. 單一角塊不能翻色
所以要簡化記憶，相信分開色向與位置來編碼比較好，
而對於色向與位置，二階對應的特色為(2) 及 (1)。
其中可知，只有色向記憶可簡化。

我們現在在談二階所有狀態需要多少容量，
準確地說，最少需要的容量上界是28.03mb。
而其下界就是本貼所討論的。
但可以肯定的是，就如標題所說，列出2階全部態就只需幾十MB(<30)

作者: smok 时间: 2009-11-7 09:12:16

楼上，6个颜色编码至少要3个位，24个色块要24*3个位=72个位，所有状态容量=8!*3^7*1/24*72=264539520.000bit，费了九牛二虎之力终于算到小数点后面3位！！约31.536MB,楼上看看你的计算是不是太粗了还是概念错了？什么时候才能将魔方看成块而不用技工的“片“概念？哈哈哈

[ 本帖最后由 smok 于 2009-11-7 09:36 编辑 ]

作者: smok 时间: 2009-11-7 09:56:47

简化？不错的想法，我们的编码可以容纳8!*3^8个状态,其中1/72才是有效不重复状态,但是,单单对一个块而言,谁又能举出其在某个位子的不可能状态?

[ 本帖最后由 smok 于 2009-11-7 10:00 编辑 ]

作者: william_khs 时间: 2009-11-7 11:01:20

原帖由 smok 于 2009-11-7 09:12 发表
楼上，6个颜色编码至少要3个位，24个色块要24*3个位=72个位，所有状态容量=8!*3^7*1/24*72=264539520.000bit，费了九牛二虎之力终于算到小数点后面3位！！约31.536MB,楼上看看你的计算是不是太粗了还是概念错了？什么 ...

"6个颜色编码至少要3个位"? 為甚麼6個顏色編碼至少要三個位(bit?!)?
我說的是byte....(我對bit,byte的概念有點不清....),
假如說byte的話，"B",Y","O"...算是一個byte 吧?
假如說bit的話..."B",Y","O"...算是8個bit 吧?

我的說法是將整個魔方呈摺紙圖樣般攤開，
然後將每一格的顏色編碼, 如:"Y,O,B,R...."
那麼，是你曲解我的意思嗎?

作者: smok 时间: 2009-11-7 12:44:27

其一:
哦,难怪,原来你不能区分bit 与byte, 即然如此,在这里讲一下基本概念,位(bit)是计算机可以操作的最小单位,每个位有0和1二个状态,8个位为一个byte,所以用位操作更省空间.
其二:
前面说过,每个位有二种状态(0,1),二个位可以表示2*2种状态,三个位可以表示2*2*2个状态,所以必须用三个位表示6个颜色,明白?
其三:
一个一个的方片编码更费空间
---------------------------------------------
所以,只要明白bit的概念,才能确定更省的存贮方案

[ 本帖最后由 smok 于 2009-11-7 12:57 编辑 ]

作者: xpboy 时间: 2009-11-7 12:47:30

我也同意陈霜的30bit的说法，不知道是不是也是用盲解的思路，角位置和方向分开记忆

定义一个基准角块，剩下的七个角块，记录六个角块位置3bit*6，六个角块朝向2bit*6
第七个角块的位置和朝向不记录

再简化的话，可以从朝向入手，三个角块的朝向用5个bit来记录，这样最终可以用28bit来存储

[ 本帖最后由 xpboy 于 2009-11-7 12:49 编辑 ]

作者: xyb718378 时间: 2009-11-7 12:54:42

东方的话再次引起众多论坛元老的激烈讨论。。。。。

作者: smok 时间: 2009-11-7 13:06:16

又是一个分不清字节与位谁更大的跟贴,1号块在2号位保持3号色向,则二阶用24个数字就标记了一个状态,一个数字在计算机中要用8个位来表示,则一个状态要用192个位!不参与楼主岳飞杀张飞的争闹了

[ 本帖最后由 smok 于 2009-11-7 13:11 编辑 ]

作者: william_khs 时间: 2009-11-7 18:55:51

感謝smok的指教...受益了!
請注意喔...小弟所說的是最大需要多少空間

作者: smok 时间: 2009-11-7 21:50:41

不客气,我没有发现你犯的低级提问错误,哈哈哈.最大就不好说,你问:自已回家最多走多远?你可以绕着自已家转无数圈再进门,所以你最多可以走无穷远再回家,就不知有几个人能活着看你活着进家门,哈哈哈.

[ 本帖最后由 smok 于 2009-11-7 21:53 编辑 ]

作者: Paracel_007 时间: 2009-11-8 20:54:01

又在讨论这个问题了，很复杂的样子~

作者: kexin_xiao 时间: 2009-11-8 22:34:59

每次理论问题都会引来大师们的争论

作者: 铯_猪哥恐鸣 时间: 2009-11-9 16:07:43

回25楼，我刚找到用22bit的极限空间表示每个状态的方法，不过速度方面会因为加、解码慢差不多3倍左右。。

作者: conwood 时间: 2009-11-9 16:27:33

还是不明白。

原帖由 haohmaru 于 2009-11-6 08:51 发表

计算机只认识两个数：0和1

作者: Cielo 时间: 2009-11-10 22:04:25

原帖由 xpboy 于 2009-11-7 12:47 发表
我也同意陈霜的30bit的说法，不知道是不是也是用盲解的思路，角位置和方向分开记忆

定义一个基准角块，剩下的七个角块，记录六个角块位置3bit*6，六个角块朝向2bit*6
第七个角块的位置和朝向不记录

再简化的话 ...

不明白3个朝向用5bit表示……
P.S:你的头像居然是海星mm

原帖由 铯_猪哥恐鸣 于 2009-11-9 16:07 发表
回25楼，我刚找到用22bit的极限空间表示每个状态的方法，不过速度方面会因为加、解码慢差不多3倍左右。。

赞啊~不过我也不懂如何做到的……
22确实是极限了，2[sup]21[/sup]比总状态数要少！

作者: gb57 时间: 2010-4-5 18:36:25

这个问题很有意思，我只能想到用30个bit的方法，
我是这么想的，如果把红白蓝角固定到左下前位置，再有一个角不编码，另外6个角按顺序排列，如果位置在上面是0，位置在左面是0，位置在前面是0，颜色红或橙朝上下为00，朝左右为01，朝前后为10
那当红绿黄角在上右后位置的时候，编码就是01100 ，6个角一共30bit
但这么干010**和***11没有用到
不知22bit是用的什么方法

作者: pengw 时间: 2010-4-5 19:01:25

二阶每个块:
位置:3位,2*2*2,代表8个可能的位置
身份:3位,2*2*2,代表8个块
色向:2位,2*2,代表3个色向

一个二阶状态至少应该64位,8个字节

所有二阶状态:8!*3^7*/24*8=29393280 BYTE=29MB

[ 本帖最后由 pengw 于 2010-4-5 19:04 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2010-4-6 00:27:55

回楼上诸位，本问题的本质就是状态压缩，从状态压缩的理论上讲，存在从状态空间到相应数量的数字的一一对应，而我的二阶搜索程序也做了这个事情，最后只用了不到20M的内存，大家可以检验。

作者: 小笨檸 时间: 2010-4-6 00:37:36

嘻~!東方,好久沒見了

結婚以後就不練單手啦..?

有空交流一下

作者: pengw 时间: 2010-4-6 07:06:24

相对二十几MB的空间,优化价值不大,去做三阶更有意义

作者: 铯_猪哥恐鸣 时间: 2010-4-6 08:10:03

三阶已经可以证明它所需要的空间在理论上不可能被压缩在可接受范围内，所以能做得无非就是用带冲突的哈希表局部近似压缩罢了。

作者: pengw 时间: 2010-4-6 09:49:54

这些都不是问题的关键，关键是你解决最小步的理论依据，其次才是算法

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:00:47

额，和当前理论知识内的思路刚好相反，现在的主要想法是：算法是肯定的，搜索，不论是深搜还是广搜。至于理论，只是用于优化减少搜索量。
理由是，当前的理论对于最少步求解还没有任何思想方面的意义，只是优化方面的意义。

作者: pengw 时间: 2010-4-6 10:04:51

压缩并不等于缩减信息量，只是节省存贮空间，信息量不减，搜索量也不减，不清楚你是如何凭压缩减少搜索量，如果你认为算法可以，你应该证明你的说法，而不是仅有结论

[ 本帖最后由 pengw 于 2010-4-6 10:17 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:13:57

回楼上，压缩不会减少搜索量，但算法可以，如果用双向广搜，解某个魔方只有算最多十的十二次。
另外，理论减少搜索量，就是在处理对称态方面，只要搜索对称态中的代表元即可

作者: pengw 时间: 2010-4-6 10:14:48

用色片来表达一个二阶状态
-----------------------------------
每块三色，每色有六色可能性，则表示一个块的身份及色向最少须要：9个位，加上3个位用于位置，则一个块最少须要：12个位，8个块则是96个位，显然用色块表达魔方状态并不是最好的选择

作者: pengw 时间: 2010-4-6 10:16:25

回44楼：
双向搜索与对称排除与压缩应该没有关系，怎么会扯到一起来了？

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:17:10

回楼上，你所说得是魔方的层次，我之前就讨论层次与效率的问题，真正搜索的时候别说色片慢，即使是色块层也已经变得不可行。

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:18:01

回46，虽然没关系，但本质都是一样的，希望减少搜索量

作者: pengw 时间: 2010-4-6 10:19:05

为个么硬要用色片，难到魔方状态非要用色片表达不可？

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:22:19

魔方的有些部分的处理用色片会更容易一些，且不容易出错，这个属于预处理部分，所以可以慢些没关系，真正搜索的时候魔方的表达是纯数字编码式的，已经完全脱离魔方本身了。

作者: pengw 时间: 2010-4-6 10:22:38

“没有关系，本质上又一样”，你这句话到底是什么意思？

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:26:52

本质的思想。。。

作者: pengw 时间: 2010-4-6 10:29:44

水火没有关系，但本质上是一样，你如何理解这句话？

作者: pengw 时间: 2010-4-6 10:31:00

这里不是谈哲学，是讨论实实在在的魔方，每一个变换都是可见，怎么让你说得如此空虚神秘？

作者: pengw 时间: 2010-4-6 10:35:00

你的每一个论证为什么不用魔方变换来证明？

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:36:04

因为在你的意义下的魔方变换是无法证明我所需要的结论的，这就是为什么我要引入广义变换。

作者: pengw 时间: 2010-4-6 10:37:51

你认为魔方上那一种变换是魔方自身说不清楚的，进而要定义一个魔方上无法实现的变换来说明？

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:40:13

没错，若不然你试着帮我说一下S0变换如何用自身来描述？

作者: pengw 时间: 2010-4-6 10:41:33

你的S0用非魔方变换来定义，你到底是在说魔方还是魔方无关的东西？

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:45:45

这个问题好像不该在这里讨论。。窘，偏题了。。上面的你看着删或者移到那个帖子里吧

作者: pengw 时间: 2010-4-6 10:50:20

稍稍强调上下文逻辑上，问题就出来了，什么样的魔方问题非要坐在镜子面前才能解决或表达？

作者: 铯_猪哥恐鸣 时间: 2010-4-6 10:53:11

当然不是，我之前回避了镜子用公式定义你又不让，这回用广义公式你还不让，可问题是在原有理论范围是不可能定义出那个S0变换的

作者: pengw 时间: 2010-4-6 10:54:27

我没阻拦你任何行动，我只要在魔方上看到实例，难到魔方问题不是由魔方来证明？

作者: 龙魔 时间: 2010-9-17 10:38:50

没有想到这个帖子引起这么大的讨论，大师们都来了

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