RC5・DESに続くdistributed.netの挑戦は、チェスでも素数でもなく「最短ゴロム定規（OGR)」でした。まぁ例によって我々はクライアントプログラムを走らせるだけですが、OGRとは何か、どのようなアルゴリズムで探索しているのか…と言ったことを理解していれば、楽しさも増し、勧誘もし易くなるに違いありません。そこで、まだ中途半端な内容ではありますが、今まで集めたOGRに関する情報をまとめてみます。
ゴロム定規って何？
じゃぁ、最短ゴロム定規って？
それってそんなに難しいの？
でも、RC5-64よりも楽勝では？
Special Thanks(^-^)
ゴロム定規(Golomb Ruler)とは、「定規」というところから判る通り、数学の世界からやってきました。生みの親は数学者Solomon W. Golombという方です。「Sparse Ruler」と呼ばれることもあります。
ゴロム定規と普通の定規はどう違うのかと言いますと、例えばここに、0から6まで7つ目盛の付いた、長さ6cm定規があります。（単位はcmでもなんでも構わないのですが）
| 0 | 1 | 2 | 3 | 4 | 5 6 |
| １ | １ | １ | １ | １ | １ |
下の灰地の数字は目盛間の距離で、当然全て１です。ですから、これで測れる長さは、１、２、３、４、５、６。つまり目盛の数-1の6種類です。
普通の定規では、目盛数以上の種類の長さを測ることは出来ません。でも、下のように目盛をふれば、目盛数以上の種類の長さを測ることが出来ます。
0 1 4 6 １ ３ ２ 同じく長さは6cmですが、目盛は[0,1,4,6]の4つしかありません。でも、0-1間で１、4-6間で２、1-4間で３、0-4で４、1-6間で５、全体で６…と、上と同じく6種類の長さを測ることが出来るのです。これがゴロム定規です。
（特にこの定規は目盛4個で出来る最短の定規なので「最短ゴロム定規」と、さらに１から６まで全ての長さを測ることが出来るので「完全ゴロム定規」とも呼びます。これらは後述します。）
「だからなんなんだ！」…との声が聞こえてきそうですが(^^;)、このゴロム定規は符号理論、X線結晶学、回路設計、電波天文学などの分野に応用されており、これらでは普通の定規よりもゴロム定規の方が重宝されているのです。
例えば電波望遠鏡のアンテナ配置を考えてみましょう。これは、規則的に並べられたアンテナへ届く電波の微妙な差によって天体までの距離などを割り出すのに使われています。このアンテナを、「普通の定規」よろしく6km範囲の1km置きに1台づつ、計7台設置して得られる結果と、「ゴロム定規」に従って6km範囲に4台設置して得られる結果は同じものになります（測ることの出来る距離の種類は同じ訳ですから)。そうなると、ゴロム定規に従ってアンテナを建造したほうが差し引き３台分の建設費が浮くことになります。これは大きいですよね(^-^)
さて、どういうものが「ゴロム定規｣なのかを以下に定義します。
重複せず負の数を含まない整数のみからなる数列GRが以下の条件を満たすとき、数列GRは「ゴロム定規」であるといいます。
| 数列GR上任意の要素x、y、x'、y'において、必ずx-y≠x'-y'となる
（ただし x>y、x'>y'、x≠x'またはy≠y') |
…つまり…え〜と、例えば次のような集合はゴロム定規ではありません。
| [0,1,2,3] …4つの数からできるx-yの組み合わせは[1-0,2-1,3-2,2-0,3-1,3-0]。 これに対応する結果セットは[1,1,1,2,2,3]。 重複しているのでゴロム定規ではない。 |
同じ要素数４の数列でゴロム定規(GR-4)を作るとすれば、例えば次のようになります。
（以下、要素数nを「nマーク」、nマークのゴロム定規を「GR-n」、同じく最短ゴロム定規を「OGR-n」と呼びます。）
| [0,1,3,7] …4つの数からできるx-yの組み合わせは[1-0,3-1,7-3,3-0,7-1,7-0]。 これに対応する結果セットは[1,2,4,3,6,7]。 重複していないのでゴロム定規である。 |
数列、と言うと拒否反応で頭がおかしくなりそうですが(＾＾;)、これは次のような目盛の振られた定規と捕らえてみます。
| 0 | 1 | 3 | 7 | |||
| １ | ２ | ４ | ||||
上段白地のスケールは上で示した[0,1,3,7]のマークです。下段灰地のスケールはゴロム定規の目盛で、数字はマーク間の長さです。つまりこの定規で測れる長さは上で示したとおり、「１」、「２」、「４」、及び１と２を使った「３」、２と４を使った「６」、そして全体の長さである「７」です。５は測れませんがそれは仕様です(苦笑) 肝心なのは、マークの存在が無駄なものとならない、という事です。
他にもGR-4は[0,1,3,11]、[0,1,7,11]などなど無数に存在します。要は差が重複しなければ良いのですから、簡単に量産したければ要素の最大値（一番右の数）をどんどん大きくしていく、つまり定規をどんどん長くして行けば良いわけなんです。
最短ゴロム定規（Optimal Golomb Ruler)とは、例えば上記の[0,1,3,11]のGR-4よりも[0,1,3,7」のGR-4の方が短い定規となるように、無数に存在するGR-nの中で最短のものがOGR-nです。上に示した（[0,1,3,7]の）定規は、GR-4ですがOGR-4ではありません。つまり、OGR-4とは定規全体の長さが７以下な訳です。ではもう一度この定規をチェックしてみましょう。
| 0 | 1 | 3 | 7 | |||
| １ | ２ | ４ | ||||
どうして最後の目盛の長さを「３」ではなく「４」としたのでしょう？ それはもしも[0,1,3,6]というマークでは、3-0と6-3が共に３となり、重複するのでゴロム定規ではなくなってしまうからです。でも、ちょっと工夫して、下のように「最適化（Optimal)」すればゴロム定規の条件を満たしませんか？ これこそが４マークの最短ゴロム定規、OGR-4です！
0 1 4 6 １ ３ ２
このようにOGR-4は[0,1,4,6](長さ6)が最短で、これ以上短くする方法はなく、唯一のものです。
「え、唯一？ [0,1,4,6]の他に、[0,2,5,6]も最短ゴロム定規では？」 はいその通りです。
0 2 5 6 ２ ３ １
今までの目盛の振り方は、最初を0(ゼロ)、最後をLとした昇順、つまり 0<a<L という規則で振っていましたが、逆に最初をL、最後を0(ゼロ)とした降順、 L>a>0 という規則で目盛を振ると、以下のようになりますよね？
6 4 1 0 ２ ３ １ このように、一見[0,1,4,6]と[0,2,5,6]は別の定規に見えますが、実は単なる裏返しの関係（対称型）なので、同一の定規とみなされます。
ただし、同じ長さで完全に「別の」定規である例も存在します。今までにOGR-21までが確認されていますが、OGR-5/6/7/11には、同じ長さで複数のOGRが発見されています。James B.Shearer@IBM Researchのページでご確認ください。
４マーク程度であれば、ちょいと頭をひねれば最適解がみつかります。でも、10マーク、20マークと増えていったらどうでしょう？ 4マークでの組み合わせは6通りでしたが、当然組み合わせと言うものは増えていきますから、すぐに頭はパンクしてしまいます。ちなみにOGR-5は[0,1,4,9,11]ですが、その生成に規則性は見出せないと思います。
実際、この「最短ゴロム定規」問題は、効率的に解決できるアルゴリズムの存在しない（多項式オーダーでは「解けない」）問題、「NP完全」問題であると言われています。ただし、NP完全で計算規模が爆発的に大きくなったので解が判りません、では困るので、多くのNP完全問題には「最適じゃないんだけれど実用的なぐらい最適に近い解」を求めるアルゴリズム、というものが存在します。OGRでは、「Cyclic Differece Set」(CDS)です。ただし最適ではない以上OGRではないので、基本的にCDSによって得られるのは単なるGRです。現在CDSによって既にGR-150までが計算され、その長さは20521であることが判っています。
CDSに関する情報は現在翻訳中ですので少々お待ちください(^^;) もっとも、今まで実際に計算されたOGR-2からOGR-21までで、CDSアプローチによって得られたGRがOGRではなかったのは7つのみで、最高の開きがあったOGR-15でも、精度の差は長さ12ぶんと、なかなかよく出来たアルゴリズムのようです。
CDSでは正確には得られない。でも調べたい… そう考え、分散コンピューティングを利用してOGR-20及びOGR-21の計算を呼びかけたのがMark Garryのページです。残念ながらOGR-20/21ともにCDSアプローチによって得られたGRよりもOGRは短く出来るという結果は得られなかったようです。「OGR-22もやる！」とあるのですが、充電中のようで、恐らくdistributed.netはこれを引き継ぐか対決する形でOGR-22の計算を行うものと思われます。
RC5-64では、「全部で2^64=18,446,744,073,709,551,616個の鍵があり、正解はこのどれかにある｣と言う単純明快なものでしたが、OGRの方はそうはいかないんです。
まず、「RC5-64で鍵に相当するものは何通りあるか？」ですが、判りません!!!! …というのも、ある数列を仮定して、それがGRかどうかをチェックするのではなく、GRをどんどん作っていって、それが長さ制限（358以下)に収まるかどうか、をチェックするからです。ですから、何通りあるかが判ったとき、それはOGRが発見されたときなんですよ(笑) ですから、判りません!!!!
無数に存在するGR-22… これを、OGRに関わる色々な法則を使って絞り込んで行くわけです。例えば長さは358を超えない、11番目のマークは178以下になる、ゴロム定規は切っても切ってもゴロム定規になる、対称型は同じ定規である、2番目のマークは2からはじめる… これらを組合わせれば探索範囲がどんどん縮まります。その手法に関しては今後紹介します。
おおたさん＠電信八号ユーザーズ
青木さん＠SEGAユーザーズグループ
くまがいさん＠TeamOS/2Japan
田中さん
うえやまさん＠Japan Linux User Group
数名の「匿名希望」さん(^^;)
参考文献
・Dollas,Rankin,McCracken「A New Algorithm for Golomb Ruler Derivation and Proof
of the 19 Mark Ruler」
IEEE Transactions On Information Theory, Vol.44, No.1, pp.379-382, 1998
・Dewdney「Computer Recreations（地球を計測する電波天文学者を手伝う目に見えない定規の探索）」
Scientific American, pp.14-21, Mar.1986（別冊日経サイエンス102, pp.82-87, 1992）
・Garry「In Serach Of The Optimal 20
& 21 Marks Golomb Rulers」
・Shearer「Golomb rulers
and related problems」
・Coolsaet「Golomb Rulers and Cyclic Defference
Sets」
…以上です…
9月17日版に、とりあえず誤りの修正と若干の追加を行ないました。CDSや探索アルゴリズムなど、ただいま勉強中ですので、もうちょっとで「らしく」なるんじゃないかと思います。数日後にまたいらしてください(^-^)
jtfuruhata H10.9.16
modified H10.10.8