distributed.net、25マークの最短ゴロム定規を導き出す 12
タレコミ by capra
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名によって発見された。(本家/.記事より)
これは役に立つ....... (スコア:2, 興味深い)
単純なアレイは等間隔に素子を配置するのですがそのようなやり方は冗長であって,より少ない素子数でも不等
間隔配置によって良好な指向特性を得られます. 昔ちらちらと調べたことがある資料ではこんな言葉を見た覚えが
無いのですが,実はゴロム定規に基づく配列は冗長性の無いアレイの最適配列の解になってるんですよ!
(素子の間隔の差が等差数列となるのが最良)
タレこんでくれた人ありがとう,勉強になりました.
Re:これは役に立つ....... (スコア:2, 興味深い)
ロト24(おふとぴ) (スコア:1)
もし数字全部当てたら末代までビルゲイツだなぁきっと。
Re: (スコア:0)
賞金が「末代までビルゲイツ」になるまで,当たらないクジを購入し続ける人が続くことは無いでしょう.
参加してください (スコア:1, 参考になる)
次のOGR-NGも始まっています。
typo (スコア:0)
解法ね。
0がぬけてる? (スコア:0)
要素も24個しかないようですし・・・。
Re:0がぬけてる? (スコア:2, 参考になる)
を追いかけてみました。それによると
(bold化は私)
つまり「0は当たり前なので記述しない」ようですね。
fjの教祖様
Re: (スコア:0)
NP完全? (スコア:0)
NP完全であるためには、解が真に最短であることの検証が多項式時間でできる必要があると思いますが
Re:NP完全? (スコア:1)
というか、最短ゴロム定規を「求める」のは明らかにNPに属さない(⇒NP完全ではない)ですね。
Re: (スコア:0)
NP困難なら総当りでやってるのかな。それならあんまり面白い話じゃないな。