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

capra 曰く、

distributed.netのOGR-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名によって発見された。（本家/.記事より）

「最短ゴロム定規」とは、それぞれの差がすべて異なる非負の整数の集合のことで、その集合に含まれる整数の数をマーク数と呼ぶ。たとえば「{0,1,4,6}」は「4マークの最短ゴロム定規」である。ゴロム定規については、「△橘どすこい支所」の「Optimal Golomb Rulerとは？」という記事が分かりやすい。

ゴロム定規は電波望遠鏡や暗号化などで使われているが、最短ゴロム定規を求める問題は効率的な解法が存在せず、NP完全問題である（マーク数が増えると指数的に計算量が増える）ため、マーク数が大きい最短ゴロム定規を求めるのは困難であった。

これは役に立つ.......

[Anonymous Coward]

ゴロム定規ってなんじゃらほいと思ったら，今やっているある種のアレイ設計とも関連のある話なので驚きました．

単純なアレイは等間隔に素子を配置するのですがそのようなやり方は冗長であって，より少ない素子数でも不等
間隔配置によって良好な指向特性を得られます．　昔ちらちらと調べたことがある資料ではこんな言葉を見た覚えが
無いのですが，実はゴロム定規に基づく配列は冗長性の無いアレイの最適配列の解になってるんですよ！　
（素子の間隔の差が等差数列となるのが最良）
タレこんでくれた人ありがとう，勉強になりました．

Re:これは役に立つ.......

[Anonymous Coward]

実はイージqあwせdrftgyふじこlp

ロト24(おふとぴ)

[salasen (31808)]

1から500までのうちから好きな数字を24個選んで、、、とは関係のね。てっきりロトくじの抽選結果に見えたので。

もし数字全部当てたら末代までビルゲイツだなぁきっと。

Re:

[Anonymous Coward]

長いロトを作っても，売り上げが増えた分しか賞金は増えません．
賞金が「末代までビルゲイツ」になるまで，当たらないクジを購入し続ける人が続くことは無いでしょう．

参加してください

[Anonymous Coward]

【分散処理】またーりdistributed.net 6【懸賞有】 [2ch.net]
次のOGR-NGも始まっています。

typo

[Anonymous Coward]

＞最短ゴロム定規を求める問題は効率的な解放が存在せず、
解法ね。

0がぬけてる？

[Anonymous Coward]

12 の前に 0 があるのではないでしょうか？
要素も24個しかないようですし・・・。

Re:0がぬけてる？

[okky (2487)]

http://www.distributed.net/ogr/index.php.jp [distributed.net]
を追いかけてみました。それによると

　

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

(bold化は私)

つまり「0は当たり前なので記述しない」ようですね。

--
fjの教祖様

Re:

[Anonymous Coward]

というか、 okky さんも引用されている解説では「ゴロム定規は通常、 (中略) マーク間の距離によって表され」る、とありますが、タレコミ文中のはマークの絶対位置なので通常の表記法ではないですね。

NP完全？

[Anonymous Coward]

NP完全 [wikipedia.org]ではなく、NP困難 [wikipedia.org]では？
NP完全であるためには、解が真に最短であることの検証が多項式時間でできる必要があると思いますが

Re:NP完全？

[deraok (37011)]

どうもNP困難性も未証明 [wikipedia.org]のようですが・・・
というか、最短ゴロム定規を「求める」のは明らかにNPに属さない（⇒NP完全ではない）ですね。

Re:

[Anonymous Coward]

そうですね。

NP困難なら総当りでやってるのかな。それならあんまり面白い話じゃないな。