アカウント名:
パスワード:
ルービックキューブの世界選手権に出ている人たちの実感は何手くらいなのでしょうね。
最後のひと工夫でさらに3手縮めているところがミソのようですがまだ理解できていません。
最後のひと工夫 (三手縮める) は Kociemba の Cube Explorer で brute force をかけました、ということでしょう。Section 7.3 のまんまです。
Kunkle達はこれをしなかったそうです。
リンク先 (cubezzz.homelinux.org) には
I already told this Daniel Kunkle and he agreed with this.
追実験はそう難しくないはずなので、近いうちにちゃんとした 26 手の証明は完成されると期待したいんですが、それよりも現時点で 26 手の証明がされたというのは誤報なので、これがどう修正されていくかが気になります。
Brute force では 25 手の証明までこのまま一気にされそうな勢いですが、やっぱりアルゴリズム面での工夫と breakthrough がないと面白くないですね。まだ新規参入者のつけいる余地はあるということですか。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
コンピュータは旧約聖書の神に似ている、規則は多く、慈悲は無い -- Joseph Campbell
シミュレーションでは証明にならない (スコア:0)
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
Re:シミュレーションでは証明にならない (スコア:0)
ないのかな？総当りでやってたならば示されてしまってるということに
もなりそうなんだけど．
枝刈りの仕方とかからまだ言えないのかしら．
Re:シミュレーションでは証明にならない (スコア:0)
他にもっと効率のよいアルゴリズムがあるのかもしれません。
つまり、総当りというのは初期状態のことであって、経路では ないのです。
ルービックキューブの世界選手権に出ている人たちの実感は何手くらいなのでしょうね。
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
こっちのページ [physorg.com]には論文へのリンクがあります。これから読んでみます。
ちなみに世界選手権でいちばんメジャーな解法である「LBL法」では平均56手くらいです。
自分で解きながら数えたこともありますがおおむね50～60手くらいです。
最小手数を競う競技もあります。
紙と鉛筆だけを使って1時間以内に見つかった解の手数を使います(公式ルール [jrca.cc]内のArticle E参照)。
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
そこまでの最大手数、そこからの最大手数の和を計算したそうです。
最後のひと工夫でさらに3手縮めているところがミソのようですがまだ理解できていません。
Wikipediaの記事 [wikipedia.org]では、ルービックキューブの最短手数探索法について、
Thistlethwaiteによる4段階法、Kociembaによる2段階法が解説されています。
CoopermanとKunkleの方法は、同じように表記すれば、
G0=<L,R,F,B,U,D>
G1=<L2,R2,F2,B2,U2,D2>
と部分問題を設定した場合に相当します。
CoopermanとKunkleはcosetの要素全
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
最後のひと工夫 (三手縮める) は Kociemba の Cube Explorer で brute force をかけました、ということでしょう。Section 7.3 のまんまです。
26手以下という証明はできていなかった (スコア:1)
この中で、レベル3までのcosetとレベル12と13のハーフターン部分群要素の積について、brute forceのかけ方が足りなかったことが、Herbert Kociembaの指摘 [homelinux.org](コメントを見るにはログインが必要)によってわかったそうです。彼らはレベル3のcoset 23個と624個の部分群要素の積、約1.4万個を作成してCube Explorerにかけました。論文の方法ではレベル13のcosetについては、3+13つまり16手以内であることしか証明できないので、実際に最適解を求めてみて14手以内だった、上限を2手縮めた、と主張してたわけです。
23も624も、ともに対称性を使って要素数を減らした結果の数え上げなので、積を計算するときには少なくとも片方は48通りに回転させなければなりません。Kunkle達はこれをしなかったそうです。
そんなわけで、「ルービックキューブは26手以内で揃う」という証明は未完成です。計算し忘れた分の中に14手以内で解けない状態がもし見つかったら、この論文では証明できなかったことになります。もちろん追加でCube Explorerを回してみたら、全部14手以内で解けるかもしれません。しかしそれよりは、論文のSection 6に示されている方法で調べた方が早く結果がわかるかもしれません。
Re:26手以下という証明はできていなかった (スコア:1)
リンク先 (cubezzz.homelinux.org) には
とあるので、そのうち Kunkle から何かコメントがあるかもしれませんね。追実験はそう難しくないはずなので、近いうちにちゃんとした 26 手の証明は完成されると期待したいんですが、それよりも現時点で 26 手の証明がされたというのは誤報なので、これがどう修正されていくかが気になります。
Brute force では 25 手の証明までこのまま一気にされそうな勢いですが、やっぱりアルゴリズム面での工夫と breakthrough がないと面白くないですね。まだ新規参入者のつけいる余地はあるということですか。