Project OGR
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に関するリンク集
- Wikipedia's article
- MathWorld's description of Golomb Rulers
- Greg Hewgill's technical OGR information page and his plan file
- The previous OGR Effort (OGR-20, -21, -22, and -23)
- James B. Shearer's list of best known Golomb rulers (up to 150 marks) and his main Golomb page.
- Lloyd Miller's listing of more best known Golomb rulers and other information.
- William T. Rankin's web page describing his master's project involving the distributed search of OGR-17, -18, and -19
- Stephen Wayne Soliday's paper on a Genetic Algorithm for Near Optimal Golomb Rulers
- D. Kent Freeman paper abstract on the Similarity of Maximizing Irregularity and Solving Golomb Rulers
その他、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).