パスワードを忘れた? アカウント作成
38797 submission
数学

distributed.net、25マークの最短ゴロム定規を導き出す 12

タレコミ by capra
capra 曰く、
distributed.netOGR-25プロジェクトで、25マークの最短ゴロム定規が証明された。25マークの最短ゴロム定規の長さは「480」で、マークの配置は以下のとおり。
12-29-39-72-91-146-157-160-161-166-191-207-214-258-290-316-354-372-394-396-431-459-467-480
開始から8年が過ぎたOGR-25プロジェクトには今まで124,387人が貢献してきており、最短解は2007年10月10日に1名と2008年3月24日に1名の合計2名によって発見された。(本家/.記事より
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2008年10月28日 17時18分 (#1445935)
    ゴロム定規ってなんじゃらほいと思ったら,今やっているある種のアレイ設計とも関連のある話なので驚きました.

    単純なアレイは等間隔に素子を配置するのですがそのようなやり方は冗長であって,より少ない素子数でも不等
    間隔配置によって良好な指向特性を得られます. 昔ちらちらと調べたことがある資料ではこんな言葉を見た覚えが
    無いのですが,実はゴロム定規に基づく配列は冗長性の無いアレイの最適配列の解になってるんですよ! 
    (素子の間隔の差が等差数列となるのが最良)
    タレこんでくれた人ありがとう,勉強になりました.
  • 1から500までのうちから好きな数字を24個選んで、、、とは関係のね。てっきりロトくじの抽選結果に見えたので。

    もし数字全部当てたら末代までビルゲイツだなぁきっと。
    • by Anonymous Coward
      長いロトを作っても,売り上げが増えた分しか賞金は増えません.
      賞金が「末代までビルゲイツ」になるまで,当たらないクジを購入し続ける人が続くことは無いでしょう.
  • by Anonymous Coward on 2008年10月28日 23時04分 (#1446112)
    【分散処理】またーりdistributed.net 6【懸賞有】 [2ch.net]
    次のOGR-NGも始まっています。
  • by Anonymous Coward on 2008年10月28日 14時09分 (#1445791)
    >最短ゴロム定規を求める問題は効率的な解放が存在せず、
    ね。
  • by Anonymous Coward on 2008年10月28日 14時24分 (#1445800)
    12 の前に 0 があるのではないでしょうか?
    要素も24個しかないようですし・・・。
    • Re:0がぬけてる? (スコア:2, 参考になる)

      by okky (2487) on 2008年10月28日 14時44分 (#1445814) ホームページ 日記
      http://www.distributed.net/ogr/index.php.jp [distributed.net]
      を追いかけてみました。それによると

       
      ゴロム定規は通常、上記のようにマークの絶対位置で記述するのではなく、 マーク間の距離によって表され、例えば上のものは「1-3-5-2」です。 (まれに「0-1-3-5-2」と表されることもありますが、通常0は省略されます。)

      (bold化は私)

      つまり「0は当たり前なので記述しない」ようですね。
      --
      fjの教祖様
      親コメント
      • by Anonymous Coward
        というか、 okky さんも引用されている解説では「ゴロム定規は通常、 (中略) マーク間の距離によって表され」る、とありますが、タレコミ文中のはマークの絶対位置なので通常の表記法ではないですね。
  • by Anonymous Coward on 2008年10月28日 20時31分 (#1446041)
    NP完全 [wikipedia.org]ではなく、NP困難 [wikipedia.org]では?
    NP完全であるためには、解が真に最短であることの検証が多項式時間でできる必要があると思いますが
typodupeerror

UNIXはただ死んだだけでなく、本当にひどい臭いを放ち始めている -- あるソフトウェアエンジニア

読み込み中...