魔方吧·中文魔方俱乐部

标题: 【東方】把三阶魔方的状态数存入数据库列表，需要多大空间？ [打印本页]

作者: haohmaru 时间: 2009-9-27 17:57:26 标题: 【東方】把三阶魔方的状态数存入数据库列表，需要多大空间？

魔方状态数好像是4后面19个0（记错了别砖我- -）
40000000000000000000的二进制
100010101100011100100011000001001000100111101000000000000000000000
我数了一下好像是66位
那就是最少需要66bit，（也就是8个多字节）
再加上为了便于查询加的字头之类的。。。。
一个魔方状态的长度，就粗略的就按9字节算吧

那么全部状态数加起来需要：
31EB！！！！！
1EB=1024PB，1PB=1024TB，1TB=1024GB，后面大家都知道了。。。。。。

[ 本帖最后由 haohmaru 于 2009-11-3 11:50 编辑 ]

作者: Pyrenees 时间: 2009-9-27 18:04:23

完全不理解这个逻辑……

作者: lj040051 时间: 2009-9-27 18:05:16

啊需要这么多啊那非要弄多少个硬盘啊!!!!!

作者: aben306 时间: 2009-9-27 18:09:09

呵呵...是这个算法吗?

作者: chrisvana 时间: 2009-9-27 18:21:16

东方，你是不是太闲了，想到这个。。。恩，于是我想说——东方，你妈妈叫你回家吃饭了！

作者: 机器贝尔 时间: 2009-9-27 18:47:18

那假如换成图片？那要多少啊？

作者: 乌木 时间: 2009-9-27 19:42:10

可以“浓缩”的吧？一个状态代表了一批，需要时按照一定规律“稀释”出相关的一批。问题是，状态数不仅多，还不是全部都具体知道。那么，退一步，那帮子作为“代表”的态也并不全部都知道。可以知道的只是，总数多少（比如约4.3×10^19），任一态共同遵守的变化规律（三种基本的不可能变化），等等。
此外，软件解魔方好像不需要全部知道具体四千亿亿个态的吧？输入一个状态，它总可以用一定的方法解出来，不至于需要你说的那种数据库吧？

作者: pengw 时间: 2009-9-27 19:47:17

角块编号:8 ,二进制3位
角块位置:8,二进制3位
角块色向:3,二进制2位
棱块编号:12,二进制4位
棱块位置:12,二进制4位
棱块色向:2,二进制1位
中心块编号:6,二进制3位
中心块色向:4,二进制2位
-----------------
最多22个二进位约三个字节足够表示一个三阶状态,当然,记录号并不算数据（本人曾是数据库工程师），系统会自动产生,任何一种分类方法可以直接用对三个字节的状态进行计算得出.所以,总须存贮量:

=状态数*3字节=(（12!*8!*4^6* 3^7*2^11）/8)*2*3=12！*8！*2^21*3^8=265740308118466000000000字节=265740308118466G

[ 本帖最后由 pengw 于 2009-9-27 19:52 编辑 ]

作者: Zeon.C 时间: 2009-9-27 19:58:10

原帖由 pengw 于 27-9-2009 07:47 PM 发表
角块编号:8 ,二进制3位
角块位置:8,二进制3位
角块色向:3,二进制2位
棱块编号:12,二进制4位
棱块位置:12,二进制4位
棱块色向:2,二进制1位
中心块编号:6,二进制3位
中心块色向:4,二进制2位
----------------- ...

　
貌似e也不够了…

作者: haohmaru 时间: 2009-9-27 20:09:15

原帖由乌木于 2009-9-27 19:42 发表
可以“浓缩”的吧？一个状态代表了一批，需要时按照一定规律“稀释”出相关的一批。问题是，状态数不仅多，还不是全部都具体知道。那么，退一步，那帮子作为“代表”的态也并不全部都知道。可以知道的只是，总数多少 ...

不知道有没有合适的软件
CE的结算结果不是最短路径

作者: haohmaru 时间: 2009-9-27 20:10:55

原帖由 pengw 于 2009-9-27 19:47 发表
角块编号:8 ,二进制3位
角块位置:8,二进制3位
角块色向:3,二进制2位
棱块编号:12,二进制4位
棱块位置:12,二进制4位
棱块色向:2,二进制1位
中心块编号:6,二进制3位
中心块色向:4,二进制2位
----------------- ...

这个思路不错！！
如果按照盲拧的思路
把任一状态按照【角方向、角位置、棱方向、棱位置】
四个数值or数组来确定
那每个状态表示起来就容易多了

作者: pengw 时间: 2009-9-27 20:54:36

8楼计算有误，正确的应该是
------------------------------------
全色魔方一个状态最少位数：8*2+12*1+6*2=16+12+12=40位=5个字节
全色魔方一个状态最少位数：8*2+12*1=28位=4个字节

[ 本帖最后由 pengw 于 2009-9-27 20:57 编辑 ]

作者: Pyrenees 时间: 2009-9-28 08:25:40

我还是不懂，这个“9字节”到底是不是魔方一个状态的大小，因为这个9字节是LZ用魔方总状态数换算出来的…不理解

作者: noski 时间: 2009-9-28 09:56:12

意思是，魔方4千亿亿个状态中的任何一个状态，都可以在这9个字节中找到一个唯一的编号与之一一对应。这样，9个字节就足以存放下这么多个状态的信息。
不知道pengw在12楼是怎样化简到那么少的字节的。。。

作者: pengw 时间: 2009-9-28 10:58:12

8个角块:用3个位可以完全标识每个角块身份,每个角块用2个位可以表示所有色向
角块共须:40位

12个棱块:用4个位可以完全标识每个棱块身份,每个棱块用1个位可以表示所有色向
棱块共须:60位

6个心块:每个心块用二个位可以标识所有色向
心块共须:12位

每个棱块或角块数据的位置映射该块当前在魔方上的位置,心块数据依序每二位对应一个心块色向状态

全色三阶魔方:8*5+12*5+12=112位,14个字节
纯色三阶魔方:8*5+12*5 =100位,13个字节

---------------------

上面几楼的分析不完整,以此贴为准,希望看到更省空间的编码方式.

显然,编码长度应大于总状态数的二进制位数,此理不言自明.

[ 本帖最后由 pengw 于 2009-9-28 11:13 编辑 ]

作者: noski 时间: 2009-9-28 11:22:23

我想一个容易使用的编码，应该是根据该编码，通过简单的运算就可以得到魔方的具体状态，而不是在一个巨大的表中去搜索。所以前面说的用8~9个字节的编码并不太实用。

楼上 8*(3+2)+12*(4+1) = 100 bit 这个编码方式，虽然多了几个字节，但极大节省了解码运算时间。

还可以稍微化简，因为用2个bit来表示角色向0~2，还有用4个bit来表示棱位置0~11，均有一点点浪费。另外根据魔方的性质，最后一个角块和最后一个棱块也可以确定。不过这样一来，由编码算出状态，就需要一点运算时间了。

作者: stray 时间: 2009-9-29 08:30:42

http://www.jaapsch.net/puzzles/compcube.htm

好像不需要存具体状态是什么样的，只需按照状态标号存2bit的离初始状态的距离即可。

作者: 乌木 时间: 2009-9-29 09:57:05 标题: 回复 17# 的帖子

那么，如果照你说的，用状态标号代替具体状态，岂非先要有个四千亿亿个态、以及各态和初态的距离（当然是指最少步）的表格？如果是的，能具体列出那四千亿亿个态的表格吗？此外，好像至今还没有解决两态之间的最少步问题吧？
当然，上面各位说的也是无法真的把四千亿亿个具体态存起来的，只是探讨总的空间该多大而已。
事情是不是这样？

[ 本帖最后由乌木于 2009-9-29 10:01 编辑 ]

作者: pengw 时间: 2009-9-29 10:12:43

续15楼:
比较而言,用字母表达一个全色魔方状态至少须要60个字母,角:24,棱:24,心:12,每个字母占一个字节,共须480位,比15楼的四倍还多.

作者: stray 时间: 2009-9-29 10:23:29 标题: 回复 18# 的帖子

都存不下来，只不过提供一种方法，和二阶的计算一样，遍历之后存下所需步数的表格。

现在的2 phase算法分两个阶段，步数表格就小了很多（但还是存不下，所以现在Cube Explorer是分别建立角和楞的索引表，虽然treesearch会多算一些，但存储小多，一共几十M吧，第一次安装时创建），但是这样算下来一般是次优步数了，如需验证是最少步，计算量还是很大，需要验证很多不同的pahse1的soluton，看能不能使phase2步数变得很短。

[ 本帖最后由 stray 于 2009-9-29 10:54 编辑 ]

作者: 乌木 时间: 2009-9-29 10:55:46 标题: 回复 20# 的帖子

噢，原来这样。
那么，同辈的一批后代态完全可以有一样的步数的，它们的区别就暗藏在不同的“状态标号”之中－－不同的标号，意味着获得该态的具体转动步骤不同。至于同态，具体步骤不同，但标号应该一样。
对吗？

作者: stray 时间: 2009-9-29 11:15:18 标题: 回复 21# 的帖子

我没有看过相关理论帖子，不懂具体你的同辈，同态的定义，但我理解是和对称性相关，Cube Explorer 利用了对称性减小了table的大小，不过具体实现我没看，好像有点（编程）麻烦。

我不懂理论，不知道理论区的老大们认为三阶的最远态会有某种对称性吗？

作者: pengw 时间: 2010-4-18 10:16:35

我认为,复原状态之外的所有状态都有异块同构状态,至于对称一说,目前关于对称的定义十分混乱,我就不去追时髦了,

----------

定义1，异块同构状态：相对三阶全色而言,是指同一个公式F,在复原三阶的24个方位上分别各执行一次得到的状态的集合，集合小于或等于24,

定义2，48同态：公式F的异块同态数加上F的逆的异块同构状态数，总量小于或等于48同态

------------

这种定义的好处是，从任意已知状态出发，仅仅通过整体坐标转动即可得到其它异块同构状态，再将这些所有状态的轮换反转，色向反转，即可得另外一组异块同构。

------------

已知一个状态，我们很容易知道他的逆状态，也很容易找出它的异块同构状态

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

作者: versionxp 时间: 2010-4-22 17:25:46

不管怎样总是一个很恐怖的数字！

作者: 铯_猪哥恐鸣 时间: 2010-4-22 17:33:24

建议将此贴转移至计算机理论版

作者: pengw 时间: 2010-4-22 17:36:39

别人在哪发贴,用不着你干涉,警告你不要乱转贴子

作者: pengw 时间: 2010-4-22 17:38:16

观迎你颠覆现有的理论,但不要用胡说八道的方式,这样会自讨没趣.最小步讨论也不是你的专利,你无权干涉本版的内容

作者: pengw 时间: 2010-4-22 17:39:51

做人要有自知之明,别人的就是别人的,你的版区暴增千贴,99%与你铯无关,别人也不会发贴撒泼耍横乞求一个版主位置,人品太差了

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

作者: 铯_猪哥恐鸣 时间: 2010-4-22 17:54:05

此贴发贴时间较早，在计算机理论区成立时并没有注意到这个帖子而将它移动过去。现在处理一下也为时未晚。魔方在计算机中的表示方式，你认为属于魔方理论区吗？

作者: pengw 时间: 2010-4-22 17:59:51

真是少见的厚颜无耻，过几天，我还要发最小步理论，是不是也归你哦？哈哈哈

作者: pengw 时间: 2010-4-22 18:04:26

难怪如此凶悍的G老师也沉默了，原来，不要命的怕不要脸的，哈哈哈

作者: 铯_猪哥恐鸣 时间: 2010-4-22 18:09:22

最少步理论属于最少步区，也不属于该区。你不帮忙移我找超版移吧

作者: pengw 时间: 2010-4-22 18:12:53

你干脆把这里的贴子都移到你的版区

作者: pengw 时间: 2010-4-22 18:13:23

我现在才知道，真正的不要脸是个什么味道

作者: speedz 时间: 2010-4-22 18:21:13

1024GB
我只看到了这个- -

作者: aubell 时间: 2010-4-22 22:32:49

按照摩尔定律，36年以后，我们的处理器、存储器可以达到这个要求。

作者: aubell 时间: 2010-4-22 22:35:04

36年以后，可以用最简单的穷举程序了！

作者: pengw 时间: 2010-4-22 22:43:33

还好，计算机再厉害，也仅仅只是一种工具，不会自动产生魔方知识，不过有些学计算机学傻了的家伙相信计算机会给他魔方知识

[ 本帖最后由 pengw 于 2010-4-22 22:45 编辑 ]

作者: aqianaqian 时间: 2010-4-22 23:53:54

好没劲啊。每次想好好看看帖子都看到口水战。不觉得很没劲么。

作者: 又闻落花风 时间: 2011-4-24 17:05:30

e``````神人

作者: 刀田一日 时间: 2011-8-30 18:33:32

首先，我的计算机知识并不丰富，望专家耐心看看，更有耐心的就指点一二吧
其次，说我的想法：

1，原则：以最少的数位（二进制）表示一个魔方状态
2，实质：加密解密。即，以加密算法将一个魔方状态表示为一串"0"、"1"，在读取时按解密算法进行
3，加密算法：把每个魔方的块看作一个色子，只记录色子上方数字、前色相对数据（11棱，7角）。每转一动，视为魔方的块位置不动，原地翻色。例：F动作，视作F面的4棱4角原地做F动作。
4，解密算法：依次读取，记算所需目标面的数字
5，前色相对：定义默认块上前右左后下：012345。设上色号为s，则令q=(s+1)%3+3*(s>2.5)，q在前右后左时，相对数据分别取0123.
6，位数：s--6种，q--4种，每块5位，5×（11+7）=80，总计10字节
7，优化：s--012345，03各计2位，1245各计3位。则复原态可以表示为9字节

4*10^20 /2^60 =347(E)

作者: zeoly 时间: 2011-8-30 18:34:25

本单位大型机硬盘都是EB级的路过

作者: jinxian 时间: 2011-8-30 22:36:39

　　
　　

本不想回帖，但还是稍微说一下吧。

这个“仁者见仁，智者见智”了，请参考：

http://bbs.mf8-china.com/viewthread.php?tid=79174&page=6#pid1422385

采用不同的优化工具，最后会有不同的结论！
　　
　　
　　
　　

作者: lfy126 时间: 2011-10-31 09:48:05

博起了啊………… 真是闲的蛋疼了啊

作者: wonstar969 时间: 2011-11-16 15:50:55

一个好的算法并不依赖硬件

作者: 向左看齐 时间: 2012-1-7 17:26:47

还有人探究这个问题吗?
如果依据对称性，把对称的模式过滤掉，剩下的模式应该不多吧？
哪位能指点一下，去掉对称模式之后，4千亿亿个模式会剩多少呢？

作者: jinxian 时间: 2012-1-9 12:28:47

　　
　　

剩下的个数接近于：  43252003274489856000 / 96  ，也是天文数字！

相关内容请参考：

http://www.changhai.org/articles/science/mathematics/rubikcube.php

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

http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=25682&ptid=2339
　
　　
　　
　　
　　
　　
　　

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