Project OGR

From distributed.net

OGR

クライアントとプロキシは OGRプロジェクトへの対応 をほとんどのプラットホームで既に終えています。最新のクライアント を今すぐダウンロードしてインストールしてください。また、FAQ-o-Matic にOGR関係のFAQもご用意いたしました。数名の参加者から巨大なOGR-25スタブの存在が報告されていますが、これはかなり稀な例です。 この速度に関する詳細はOGR統計ページ にてご覧いただけます。

もしあなたがdistributed.netクライアントの操作などでテクニカルサポートが必要なら、help@distributed.net宛にメールを送信してください（英語）。その質問への回答が既になされている場合もありますので、 FAQ-o-Matic をチェックすることもお忘れなく。

ところで、ゴロム定規とは何か？

ゴロム定規（Golomb Ruler）とは、数学用語でいうと「2組の数字の差が同一であることはない」正の整数の集合を表します。この集合を定規に見立て考えれば、「2組のマーク間の距離が同一であることはない」という感じになります。「最短ゴロム定規（Optimal Golomb Ruler = OGR）とは、あるマーク数のもので一番短いゴロム定規を指します。しかしながら、OGRはマークの数が増加するにつれ、その発見（と証明）は指数オーダーで難しさが増していきます。逆に言えば、我々がこのWebを用いた試みを24マーク、そしてそれ以上のOGR探索へと進路を変更したことも、この困難さが故であるのです。

ゴロム定規は、組み合わせ分析や数論、符号理論、通信の分野へ特に関心を持つ数学者 Solomon W. Golomb博士の名前にちなんでつけられました。またゴロム博士は数学ゲームやパズルでも有名で、 Scientific American誌のコラム "Mathematical Games"にも寄稿しています。 OGRはX線結晶学や電波天文学におけるセンサー配置など、沢山の分野に応用されています。ゴロム定規は他にも順列組み合わせ論や符号理論、通信の分野でも有意な役割を果たし、これらの領域に適用するため、最初の分析の一翼を担ったのがゴロム博士です。

「ゴロム定規」とは、全てのマークの対が唯一の距離を測定するよう、ライン上にマークを置く方法のことを言います。以下に示すものは、5マークのゴロム定規です。 

| |     |         |   |
0 1     4         9   11

マーク下の数字は、左端からの距離を表します。この定規の長さは「11」で、5マークの定規で最も短い配置である2つのうちのひとつです。もうひとつは [0, 3, 4, 9, 11] という配置です。（これらの配置を反対にした（対称型） [0, 2, 7, 10, 11] と [0, 2, 7, 8, 11] も最短ゴロム定規ですが、通常対称型であるペアはどちらか一つが採用されます。）

マークの配置が本当にゴロム定規であるかどうかは、マーク対を全て書き出してみると判ります。

マーク１ マーク２ マーク間距離
0 1 1
0 4 4
0 9 9
0 11 11
1 4 3
1 9 8
1 11 10
4 9 5
4 11 7
9 11 2

3列目の数字が重複していないことに注目してください。また、距離「6」が抜けていますが、ゴロム定規は全ての距離を測るためのものではなく、唯一の距離を示すことに着目しているため、問題はありません。

「最短の」ゴロム定規を探すということは、測ることのできる距離が重複しない範囲で、出来る限り最短のものを得るということです。上記2つの5マーク定規は最短のものです。

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

例えば、現在判明している21マークの最短ゴロム定規は以下の通りです。 

2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4

James B. Shearer のリストでは、最短「であろうと思われる」 ゴロム定規が150マークまで.挙げられています。もし上の21マークゴロム定規をJamesのページで確認する際には、これが対称型である事に注意してください。

さらに困ったことに、OGRはマークの数が増加するにつれ、その発見は指数オーダーで難しさが増していきます。（このような問題を、数学者は「NP完全」問題と呼んでいます … 「巡回セールスマン問題」などが有名ですね）

OGRに関するリンク集

その他、OGRに関する参考文献

  • J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation," IEEE Trans. Inform. Theory, vol. IT-13, no. 1, pp. 106-113, 1967.
  • M. D. Atkinson, N. Santoro, and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions On Communications, vol. Com-34, no. 6, pp. 614-617, June 1986.
  • A. W. Lam and D. V. Sarwate, "On optimum time hopping patterns", IEEE Transactions on communications, vol. 36, no. 3, pp. 380-382, March 1988.
  • A.Dollas, W.T.Rankin and D.McCracken published "A New Algorithm for Golomb Ruler Derivation and proof of the 19 Mark Ruler" in IEEE Transactions On Information Theory (January, 1998, Volume 44, Number 01).
Personal tools