李世春
21步:归零难,难于上青天
2021-8-13 09:49
阅读:1138

李白说:蜀道难,难于上青天。可以理解为李白走过蜀道,而没有上过青天。

博客.png

2010年,一个研究小组使用Google公司的计算机,耗费35CPU年,计算了魔方的1,090,175,792,696,524,800种状态。魔方的总状态为43,252,003,274,489,856,000。他们根据对称性简化了计算,少计算40倍,因为43,252,003,274,489,856,000/1,090,175,792,696,524,80039.6。也就是说,他们只计算了魔方状态的1/40,耗费了35CPU年。

 

实际上,他们只给出了1个新数据,就是15步的数据:91,365,146,187,124,313

因为16、17、18、19、20步没有给出准确的数据,因此,他们无法归零,即他们得不到21步的魔方状态数是0。

既然已经耗费了35CPU年,为什么就不能给出16、17、18、19、20步的准确数据呢?

问题的答案就是有一个难点,什么难点呢?这个难点就是不计算就得不到准确的数据。

我以16步为例,看看16步的基因串有多大?

183,105,468,750×43,046,721=7,882,090,026,855,468,750

16步字母串(魔方状态的基因型表达)有约7.9×10^18个,可操作出同样数目的魔方状态(表现型),但是,这7.9×10^18个魔方状态,不是独立的,有相同的,也有和以前各步(1步、2步、3步、4步、5步、6步,---15步)的魔方状态相同。

看看,计算16步的准确数据,需要多大的计算量:

1)7.9×10^18个魔方状态,相互比较,消除相同的;

2)7.9×10^18个魔方状态,和18个1步数据比较,消除相同的;

3)7.9×10^18个魔方状态,和2432步数据比较,消除相同的;

4)7.9×10^18个魔方状态,和3,2403步数据比较,消除相同的;

5)7.9×10^18个魔方状态,和43,2394步数据比较,消除相同的;

6)7.9×10^18个魔方状态,和574,9085步数据比较,消除相同的;

7)7.9×10^18个魔方状态,和7,618,4386步数据比较,消除相同的;

8)7.9×10^18个魔方状态,和100,803,0367步数据比较,消除相同的;

9)7.9×10^18个魔方状态,和1,332,343,2888步数据比较,消除相同的;

10)7.9×10^18个魔方状态,和17,596,479,7959步数据比较,消除相同的;

11)7.9×10^18个魔方状态,和232,248,063,31610步数据比较,消除相同的;

12)7.9×10^18个魔方状态,和3,063,288,809,01211步数据比较,消除相同的;

13)7.9×10^18个魔方状态,和40,374,425,656,24812步数据比较,消除相同的;

14)7.9×10^18个魔方状态,和531,653,418,284,62813步数据比较,消除相同的;

15)7.9×10^18个魔方状态,和6,989,320,578,825,35814步数据比较,消除相同的;

16)7.9×10^18个魔方状态,和91,365,146,187,124,31315步数据比较,消除相同的;

 

参考文献段落:

How We Did It

How did we solve all 43,252,003,274,489,856,000 positions of the Cube?

  • We partitioned the positions into 2,217,093,120 sets of      19,508,428,800 positions each.

  • We reduced the count of sets we needed to solve to      55,882,296 using symmetry and set covering.

  • We did not find optimal solutions to each position, but      instead only solutions of length 20 or less.

  • We wrote a program that solved a single set in about 20      seconds.

  • We used about 35 CPU years to find solutions to all of      the positions in each of the 55,882,296 sets.

Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result, which has since been independently confirmed by another researcher.

十年回看《魔方》第12回:基因断魔方:基因型计算和表现型计算_哔哩哔哩_bilibili

十年回看《魔方》第1回:魔方软兼硬,五十年不衰_哔哩哔哩_bilibili

十年回看《魔方》第2回:上帝之数的铆钉_哔哩哔哩_bilibili

十年回看《魔方》第3回:没有匈牙利数学就没有匈牙利魔方_哔哩哔哩_bilibili

十年回看《魔方》第4回:魔方的缘分和缘分的魔方_哔哩哔哩_bilibili

十年回看《魔方》第5回:河出图,洛出书,圣人则之_哔哩哔哩_bilibili

十年回看《魔方》第6回:睡仙躺平千古事,华山陈抟传洛书_哔哩哔哩_bilibili

十年回看《魔方》第7回:清代保其寿的五魔方和宋代杨辉的魔圆_哔哩哔哩_bilibili

十年回看《魔方》第8回:15子棋的爹是此人时常到,他要来收银”_哔哩哔哩_bilibili

十年回看《魔方》第9回:三条路线演绎魔方_哔哩哔哩_bilibili

十年回看《魔方》第10回:夸克断魔方:无解_哔哩哔哩_bilibili

十年回看《魔方》第11回:夸克断魔方:有解_哔哩哔哩_bilibili


转载本文请联系原作者获取授权,同时请注明本文来自李世春科学网博客。

链接地址:https://m.sciencenet.cn/blog-2321-1299536.html?mobile=1

收藏

分享到:

当前推荐数:2
推荐人:
推荐到博客首页
网友评论0 条评论
确定删除指定的回复吗?
确定删除本博文吗?