魔方吧·中文魔方俱乐部

标题: 讨论：魔方状态的最小表示方法 [打印本页]

作者: aubell 时间: 2010-5-1 21:28:28 标题: 讨论：魔方状态的最小表示方法

普通三阶，六色，无图案的魔方，
表示它的状态，最少需要多少bit ？
无论是否方便操作。

（直接拿总状态数向2取对数吗？
要比这个小才行。
直接取对数的结果是 65.23 ，
也就是说要 66 位。
假如可以少两位，就可以利用一个 64 位整数表示了。
48同态用上，可以少5位，用61位。不知是否这样？
欢迎大家讨论：具体怎样实现64位存储，或61位？
或者更少的位数？
）

作者: aubell 时间: 2010-5-1 21:31:28

把棱方向、角方向、棱排列、角排列的几个整数乘乘加加，串起来？
有其它方法吗？

作者: 夜雨听风 时间: 2010-5-1 21:34:10

色相色位不知道可以不

作者: imlei2008 时间: 2010-5-1 21:55:58

虽然听不懂但还是顶一个

作者: imlei2008 时间: 2010-5-1 21:57:30

看是不是考虑对称了之后可以减少

作者: 宇枫幽蓝 时间: 2010-5-1 22:27:14

貌似东方有个帖子讲这个的，LZ去找下吧。

作者: Cielo 时间: 2010-5-1 22:52:56

原帖由 329774632 于 2010-5-1 22:27 发表
貌似东方有个帖子讲这个的，LZ去找下吧。

是的，就在这个帖子下面几个

http://bbs.mf8-china.com/viewthread.php?tid=39680

作者: yq_118 时间: 2010-5-1 23:06:03

理论上讲是用一个整数表示，整数的范围是[0,n-1]，其中n是魔方总变化数。
48同态感觉并不能压缩一种状态的大小，因为用上了就是一种表示多种状态。

作者: 铯_猪哥恐鸣 时间: 2010-5-1 23:11:44

48同态的表示肯定是可以的，CE就用了16同态的表示（虽然其实我感觉处理的时候有点局部伪压缩的意思），就给了我们用48同态压缩魔方的可能。具体怎么压缩，或者说压缩了以后对具体搜索过程的帮助，还在思考中。

作者: yq_118 时间: 2010-5-1 23:16:15

48同态可以减少某些表的大小，例如距离表，两种状态如果是48同构的话（貌似加上逆可以达到96），那么它们的最少步还原步数就一样多，就可以节约存储空间。

作者: yq_118 时间: 2010-5-1 23:24:02

不过这个48同态用起来不知道怎么样。
对于一些自同够（感觉叫同构合理些），例如对称棋盘的状态，不管怎么用旋转，镜像，取逆，都是它本身，这样就是在压缩后还是占1种状态。而对于一些不具有对称性的状态，96种可以压缩到一种。
实际操作起来应该很复杂。

这点在OLL，PLL中也能够体现出来。

作者: 骰迷 时间: 2011-5-26 20:30:17

我不是很懂优化，但我会以打乱步骤表示状态。

作者: jshyhzj 时间: 2011-6-27 21:18:48 标题: 实战经验

我的魔方还原软件用了6个Int32来表示，每个Int32表示一个面：每个面有8个可动的块，每个色块可以有6种颜色，因此4位表示一个色块的颜色。这样都是半字节，处理起来很快速，所以我用穷举能够非常快速地搜索。
http://www.telossoft.com.cn/OtherRubikCube.aspx

对于4阶魔方我也考虑过了，可以用6个Int64表示，同样每个色块半字节。
4阶魔方旋转估计需要通过查表处理，3阶我通过位运算在处理。

作者: 小明的马甲 时间: 2011-6-28 15:59:11 标题: 回复 13# 的帖子

是否考虑过预处理？

另外你的非常快速。。有多快？

作者: jshyhzj 时间: 2011-7-7 22:04:15 标题: 熵的概念

单纯讨论最少多少位能记录魔方的所有状态是没有任何意义, 关于熵信息论有全套的计算公式

作者: 52封3 时间: 2011-7-7 22:18:37

看不懂啊...我还以为讨论魔方的最少状态呢

作者: 小明的马甲 时间: 2011-7-7 22:19:15 标题: 回复 15# 的帖子

请教楼上，你说的你的软件计算速度极快，有多快，每秒可以搜索到多少个状态？

作者: jshyhzj 时间: 2011-7-8 09:46:40 标题: 回17楼

去我网站上下一个跑下就晓得了，PC机上可以搜索到千万级别，你也可以下载源代码，设置为.net 4.0性能又可以提高50%，如果平台设为Intel 64能够搜索更多节点。通常得到的解在30步以内，三分钟以内搜到，和参数设置相关，单纯追求快速，可以在数秒内得到解，只是这时质量比较差，50步左右

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