[转]三阶魔方神程序

原文链接

http://tomas.rokicki.com/cubecontest/winners.html

第一名是来自密歇根的 Tomas Sirgedas,他的实现相当令人震惊,语言为C++,代码长度只有874个字符。在我的数据集上,平均步数为16.03,平均速度为64毫秒。他最终的得分是难以置信的7901,他的程序若非亲眼看见,打死也不相信会有这么巧妙的思路。

裁判奖归给了德国人Stefan Pochmann,他用C++实现了Thistlethwaite's algorithm。他的得分为15278,屈居第二名,代码长度为1311个字符,平均用时197毫秒,平均步数为16.72步。尽管这份代码并不完美,他还是赢得了裁判奖。在所有提交者中Perl提供了只有528个字符的最短的程序,平均占用15毫秒得出结果,并且平均327,63步复原一个魔方。

三等奖给了Jaap Scherphuis,来自Delft, the Netherlands,他再次用C++实现了Thistlethwaite’s algorithm算法。他的程序总计2059个字符,平均154毫秒得出结果,并且平均执行16.04步复原魔, 总得分21,599。此外,第一名和第二名都是归功于Jaap和他的网站算法的帮助。(原句:Furthermore, both the first and second place winners credit Jaap and his site for help with the algorithms! )

第四名是来自Gennevilliers, France的Antony Boucher ,他使用了四步连续的IDA*搜索算法来复原所有的十字到特定状态,如果失败了,就 复原顶部十字,然后复原剩下的棱块儿,接着用预先设定好的算法复原角块儿。他用C语言编写的程序使用了1628个字符,获得了惊人的平均22毫秒得出结果的成绩,对于我设定的数据,平均29.49步复原模仿,并且最终得分25,061分。

我设置的实验数据包括了所有的单步转动魔方状态,18种两步转动混乱魔方,18种3步,和46种随机混乱状态。

按最终成绩排列的最高分记录如下:

Place 名称 大小 速度 步骤数 得分
1 Tomas Sirgedas, Ann Arbor, MI, USA 874 64 16.03 7901
2 Stefan Pochmann, Darmstadt, Germany 1311 197 16.72 15278
3 Jaap Scherphuis, Delft, the Netherlands 2059 154 16.04 21599
4 Antony Boucher, Gennevilliers, France 1628 22 29.49 25061
5 David Barr, Laurel, MD, USA 1499 155 35.03 34394
6 Charles Tsai, Canton, MA, USA 2213 10 78.76 87322
7 Mikael Klasson, Linköping, Sweden 2190 10 88.34 96925
8 Grant Tregay, West Chicago, IL, USA 4009 10 59.17 118843
9 Adrian Sandor, Hong Kong, China 1992 670 54.65 127423
10 Yuri Pertsovski, Hazorea, Israel 3013 2 98.82 149467
11 Joe Lindström, Linköping, Sweden 2054 1600 39.96 172363
12 Justin Legakis 3517 212 93.4 233883

  • Stefan Pochmann, Darmstadt, Germany 528 15 327.63 89089
原文地址:https://www.cnblogs.com/weiyinfu/p/9459811.html