ゴロム定規

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動
次数4、長さ6のゴロム定規。最短で完全である。

ゴロム定規(ゴロムじょうぎ、: Golomb ruler)とは、想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺とも。マーク数を「次数 (order)」、2つのマーク間の距離のうち最大の距離を「長さ (length)」という。ゴロム定規の平行移動と鏡映は自明と考えられる。そのため慣例として、最小のマークを0とし、その次のマークは2つの可能な値のうち小さいほうを取る。

ソロモン・ゴロムが名前の由来だが、Sidon[1]とBabcock[2]も独自に発見している。

ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全 (perfect)」ゴロム定規 (PGR) という。5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている[3]。また、同一次数(マーク数)で最短のゴロム定規を「最短 (optimal)」ゴロム定規 (OGR) という。ゴロム定規を作るのは簡単だが、特定次数のゴロム定規を見つけるのは大変である。

特定次数における最短ゴロム定規の発見を分散コンピューティングを利用したプロジェクトとしてdistributed.netで進められている。distributed.netでは、次数24[4]、次数25[5]、次数26[6][7]、次数27[8]の最短ゴロム定規を求め、最短の候補を検証中である[9][10]。distributed.netは次数28の最短ゴロム定規も探索しようと計画している。ただし、新たにアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している[11]。2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていた[12]が、2014年2月に確定したと発表した[13]

最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。

今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難問題だと考えられている[3]

既知の最短ゴロム定規[編集]

下表は、全ての既知の最短ゴロム定規である。マークの配置が表にあるものと逆のもの(対称型)は省く。

次数 長さ マークの位置
1 0 0
2 1 0 1
3 3 0 1 3
4 6 0 1 4 6
5 11 0 1 4 9 11
0 2 7 8 11
6 17 0 1 4 10 12 17
0 1 4 10 15 17
0 1 8 11 13 17
0 1 8 12 14 17
7 25 0 1 4 10 18 23 25
0 1 7 11 20 23 25
0 1 11 16 19 23 25
0 2 3 10 16 21 25
0 2 7 13 21 22 25
8 34 0 1 4 9 15 22 32 34
9 44 0 1 5 12 25 27 35 41 44
10 55 0 1 6 10 23 26 34 41 53 55
11 72 0 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72
12 85 0 2 6 24 29 40 43 55 68 75 76 85
13 106 0 2 5 25 37 43 59 70 85 89 98 99 106
14 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
15 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151
16 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
17 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
18 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
19 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246
20 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283
21 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333
22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356
23 372 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372
24 425 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425
25 480 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480
26 492 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492
27 553 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553

脚注[編集]

  1. ^ S. Sidon, "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen", Mathematische Annalen 106 (1932), pp. 536–539
  2. ^ Wallace C. Babcock. "Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection", Bell System Technical Journal 31 (1953), pp. 63–73.
  3. ^ a b Modular and Regular Golomb Rulers”. 2009年6月23日閲覧。
  4. ^ stats.distributed.net - OGR-24 Overall Project Stats”. 2008年3月27日閲覧。
  5. ^ stats.distributed.net - OGR-25 Overall Project Stats”. 2008年9月22日閲覧。
  6. ^ bovin's .plan archive
  7. ^ Distributed.net Projects
  8. ^ stats.distributed.net - OGR-27 Overall Project Stats”. 2014年2月28日閲覧。
  9. ^ distributed.net - .plan archives”. 2008年3月27日閲覧。
  10. ^ distributed.net - .plan archives 2”. 2008年10月26日閲覧。
  11. ^ distributed.net - .plan archives 3”. 2009年6月23日閲覧。
  12. ^ bovine's plan, 24-Feb-2009 17:26
  13. ^ distributed.net staff blogs - The OGR-27 project has been completed.”. 2014年2月28日閲覧。

参考文献[編集]

外部リンク[編集]