パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

余剰CPU時間を使ってルービックキューブは23手以内で揃うと証明」記事へのコメント

  • by Anonymous Coward
    ランダムな25手とランダムな状態はどう違うのでしょう?
    ランダムな25手だと、あんまり崩れていないケースも
    発生するということでしょうか?
    • Re: (スコア:3, 参考になる)

      ランダムに25手回した後、方向が反転している辺の数を数えて、理論的な分布と比較すという実験が去年行われました( Lucas Garronによる解析 [yahoo.com]、Herbert Kociembaによる解析 [yahoo.com])。40手でも十分なランダム性が得られません。

      改訂されたルールでは、これら4つの座標値をランダムに選んでキューブ状態を作ります。実物のキューブでこれをやるは、いったん部品にバラして組み立てるのがわかりやすいでしょう。そんな方法では大会競技進行に間に合わない
      • Re: (スコア:3, 参考になる)

        すいません、推敲してる間に変になっちゃいました。

        「ランダムな状態」とは、ルービックキューブの取り得る状態(4.3×10^19通り)のうちのひとつを等確率で選ぶということです。

        「ランダムにn手回す」のでは、すべての状態が等確率に出現することはなりません。nが十分大きければ「実用上」問題ないレベルにできますが、その「実用上」を「危険率1%」に設定するとn=40でも不足ということです。

        以下の4つの状態を座標と考え、それぞれランダムに選ぶと、ランダムな状態を等確率で生成することができます。
        - 角キューブの方向(3^8/3)
        - 辺キューブの方向(2^12/2)
        - 角キューブの順列(8!)
        - 辺キューブの順列(12!)
        (順列の偶奇性が角と辺とで常に一致する分、どちらかを半分に制限します)。
        • by Anonymous Coward
          ちなみにその4.3×10^19通りの状態中には「あと2手で揃ってしまう」とか「既に揃ってしまっている」といった状態のキューブも含まれると思うのですが、そういったものを排除して難易度をそろえるためにどんな工夫や評価がされているのかも気になるところ。
          それとも、実用上はそんなもんは0.00001%未満の確率でしかランダムには出現しないのでしょうから、全く無視されているのでしょうか。
          • by Deasuke (34806) on 2008年05月09日 11時28分 (#1341388) 日記
            そういう場合は、きっとCubeExplorerを起動した人が「Shuffle」のボタンを押しそこなったと勘違いしてもう一度「Shuffle」のボタンを押すから大丈夫ですよ。
            --
            Best regards, でぃーすけ
            親コメント

吾輩はリファレンスである。名前はまだ無い -- perlの中の人

処理中...