| Deutsch | English | Français | Italiano | Nederlands | 日本語 | Svenska |
Project 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に関するリンク集
- 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
- David Fowler's page on Genetic Sparse Rulers [similar to Golomb Rulers]
- D. Kent Freeman paper abstract on the Similarity of Maximizing Irregularity and Solving Golomb Rulers
- A CGI server that tests for golombness if you enter a 20 mark ruler. Based out of Switzerland's ROSE university, titled: Concours Bases de l'algorithmique
その他、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).