【原创】东方说：列出2阶全部态只需要几十MB！

kexin_xiao

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

铯_猪哥恐鸣

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

conwood

还是不明白。

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

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

Cielo

原帖由 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²¹比总状态数要少！

gb57

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

pengw

二阶每个块:
位置: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 编辑 ]

铯_猪哥恐鸣

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

小笨檸

嘻~!東方,好久沒見了
結婚以後就不練單手啦..?
有空交流一下

pengw

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

铯_猪哥恐鸣

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