魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: cube_master

离初始状态最远的图案 [复制链接]

红魔

北斗

Rank: 4

积分
1585
帖子
1379
精华
0
UID
63950
性别
保密
发表于 2009-11-11 09:23:54 |显示全部楼层
楼上的计算数据是哪来的

使用道具 举报

Rank: 2

积分
536
帖子
410
精华
0
UID
82971
性别
发表于 2010-4-14 02:16:59 |显示全部楼层
哈哈,这个帖子里都是前辈啊,膜拜膜拜~~~
西安电子科技大魔友2群:15595804

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2010-8-9 10:08:59 |显示全部楼层
  
  
  
    请大家参考: http://www.cube20.org/
   
    看样子这个问题貌似有些眉目了,继续关注!
    
  
God's Number is 20
Superflip, the first position proven to require 20 moves.
Every position of Rubik's Cube™ can be solved in twenty moves or less.
With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves. Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube. One algorithm might use a sequence of moves to solve the top face, then another sequence of moves to position the middle edges, and so on. There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves. One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this is known as God's Algorithm. The number of moves this algorithm would take in the worst case is called God's Number. At long last, God's Number has been shown to be 20. It took fifteen years after the introduction of the Cube to find the first position that provably requires twenty moves to solve; it is appropriate that fifteen years after that, we prove that twenty moves suffice for all positions. A History of God's NumberBy 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions. The first upper bound was probably around 80 or so from the algorithm in one of the early solution booklets. This table summarizes the subsequent results.   
DateLower boundUpper boundGapNotes and Links
July, 1981185234Morwen Thistlethwaite proves 52 moves suffice.
April, 1992184224Hans Kloosterman improves this to 42 moves.
May, 1992183921Michael Reid shows 39 moves is always sufficient.
May, 1992183719Dik Winter lowers this to 37 moves just one day later!
January, 1995182911Michael Reid cuts the upper bound to 29 moves by analyzing Kociemba's two-phase algorithm.
January, 199520299Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves.
December, 200520288Silviu Radu shows that 28 moves is always enough.
April, 200620277Silviu Radu improves his bound to 27 moves.
May, 200720266Dan Kunkle and Gene Cooperman prove 26 moves suffice.
March, 200820255Tomas Rokicki cuts the upper bound to 25 moves.
April, 200820233Tomas Rokicki and John Welborn reduce it to only 23 moves.
August, 200820222Tomas Rokicki and John Welborn continue down to 22 moves.
July, 201020200Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki prove that God's Number for the Cube is exactly 20.
  How We Did ItHow 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.
PartitioningWe broke the problem down into 2,217,093,120 smaller problems, each comprising 19,508,428,800 different positions. Each of these subproblems was small enough to fit in the memory of a modern PC, and the way we broke it down (mathematically, using cosets of the group generated by {U,F2,R2,D,B2,L2}, or more concisely, cosets of H) allowed us to solve each set rapidly.
SymmetryIf you take a scrambled Cube and turn it upside down, you have not made it any more difficult; it will still take the same number of moves to solve. Instead of solving both of these positions, you can simply solve one, and then turn the solution upside down for the other. There are 24 different ways you can orient the Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving. Using similar symmetry arguments and by finding a solution to a large "set cover" problem, we were able to reduce the number of sets that needed solving from 2,217,093,120 down to 55,882,296.
Good vs. Optimal Solutions
Random positionsCosets of H
Optimally0.362,000,000
20 moves or less3,9001,000,000,000
Solution rate, in positions/second

An optimal solution to a position is one that requires no more moves than is required. Since a position that required 20 moves was already known, we did not need to optimally solve every position; we just needed to find a solution of 20 moves or less for each sequence. This is substantially easier; the table at left show the rate a good desktop PC has when solving random positions. Fast Coset Solving ProgramUsing a combination of mathematical tricks and careful programming, we were able to solve a complete coset of H, either optimally, or with sequences of twenty moves or less, on a single desktop PC, at the rates shown in the table at left.
Lots of ComputersFinally, we were able to distribute the 55,882,296 cosets of H among a large number of computers at Google and complete the computation in just a few weeks. Google does not release information on their computer systems, but it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation.
What are the Hardest Positions?
DistanceCount of Positions
01
118
2243
33,240
443,239
5574,908
67,618,438
7100,803,036
81,332,343,288
917,596,479,795
10232,248,063,316
113,063,288,809,012
1240,374,425,656,248
13531,653,418,284,628
146,989,320,578,825,358
1591,365,146,187,124,313
16about 1,100,000,000,000,000,000
17about 12,000,000,000,000,000,000
18about 29,000,000,000,000,000,000
19about 1,500,000,000,000,000,000
20about 300,000,000
We have known for fifteen years that there are positions that require 20 moves; we have just proved that there are none that require more.
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. We hope to have that independently confirmed by another researcher within the month. To date we have found about twelve million distance-20 positions. The following position was the hardest for our programs to solve:
The hardest position for our programs.

ContactOur group consists of Morley Davidson, a mathematician from Kent State University, John Dethridge, an engineer at Google in Mountain View, Herbert Kociemba, math teacher from Darmstadt, Germany, and Tomas Rokicki, a programmer from Palo Alto, California. Email may be sent to rokicki@gmail.com or to davidson@math.kent.edu.
Rubik's Cube is a registered trademark of Seven Towns, Ltd.
Thanks to Werner Randelshofer for use of the Cube applet on this page.

  
  
  
  
    
  
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 4

积分
2557
帖子
2231
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2010-8-10 10:48:26 |显示全部楼层
DistanceCount of Positions
01
118
2243
33,240
443,239
5574,908
67,618,438
7100,803,036
81,332,343,288
917,596,479,795
10232,248,063,316
113,063,288,809,012
1240,374,425,656,248
13531,653,418,284,628
146,989,320,578,825,358
1591,365,146,187,124,313
16about 1,100,000,000,000,000,000
17about 12,000,000,000,000,000,000
18about 29,000,000,000,000,000,000
19about 1,500,000,000,000,000,000
20about 300,000,000
以上为最新数据

[ 本帖最后由 黑白子 于 2010-8-10 15:50 编辑 ]

使用道具 举报

银魔

宇宙起源

Rank: 7Rank: 7Rank: 7

积分
3197
帖子
1034
精华
12
UID
564
性别

魔方理论探索者 魔方破解达人 论坛建设奖 六年元老

发表于 2010-8-13 12:07:27 |显示全部楼层
顶个老帖,老大在04年发的这个“角块不动,棱块原地翻转”的状态果然就是最远状态之一,20步!

到达最远的20步:
U R U2 R F2 L U2 R F' B' R2 D ( R' L U2 F2 D2 ) F R2 D
U R U2 R F2 L U2 R F' B' R2 D ( B2 U2 F2 R' L ) F R2 D
……
以及它们的相似变换等,比如:
(U') U R U2 R F2 L U2 R F' B' R2 D ( B2 U2 F2 R' L ) F R2 D (U)
(R' U') U R U2 R F2 L U2 R F' B' R2 D ( B2 U2 F2 R' L ) F R2 D (U R)
……

PS:用CubeExplorer计算某一个特定状态的最少步数的时间还是可以接受的。
The Answer to the Ultimate Question of Life, the Universe, and Everything 

使用道具 举报

Rank: 4

积分
2557
帖子
2231
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2013-10-1 13:48:11 |显示全部楼层
这个链接有问题,点下一页就无法显示网页了。

使用道具 举报

Rank: 4

积分
2557
帖子
2231
精华
1
UID
4575
兴趣爱好
其它

十四年元老

发表于 2015-4-17 19:28:37 |显示全部楼层
ggglgq 发表于 2005-5-25 08:42
以下是引用乌木在2005-5-24 16:15:02的发言:
魔方态关系网(续)

重新阅读一遍,进一步理解了最远状态这个概念。

使用道具 举报

Rank: 2

积分
346
帖子
327
精华
0
UID
1341947
性别
保密
兴趣爱好
速度
收藏
发表于 2016-10-15 17:20:07 来自手机 |显示全部楼层
老大可否发一下打乱?

使用道具 举报

Rank: 1

积分
18
帖子
18
精华
0
UID
1342151
性别
保密
居住地
济南市
兴趣爱好
速度
发表于 2016-10-15 19:32:52 |显示全部楼层
强大,顶一下。

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-28 23:20

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部