哥隆尺问题

四个分割长度为6的哥隆尺.这个哥隆尺既是完美的也是最优的。

哥隆尺问题（Golomb ruler），是指在一个固定整数长度的尺上不等长地划分最少的刻度，并能用此尺度量由1到该整数的每一个单位的问题。

哥隆尺是由Sidon and Babcock独立发现，并且以数学家Solomon W. Golomb 的名字命名。没有必要的证据证明哥隆尺能够衡量所有距离的长度，如果这样的哥隆尺真的存在的话，那么它就叫做完美哥隆尺。现已证明，没有五个或更多标记的最优哥隆尺存在。最理想的哥隆尺是指不存在更小的相同的刻度的哥隆尺。生成哥隆尺是简单的，但是找到一个指定刻度的最优哥隆尺是的一个有挑战性的计算项目。

Distributed.net已经完成了对哥隆尺-24，哥隆尺-25和哥隆尺26的大规模分布式并行查找。Distributed.net还有计划寻找哥隆尺-27和哥隆尺-28。然而，只要之前的计划用于发现一个更好的算法，他们就不会改变。Distributed.net正在积极的搜寻最优哥隆尺-27，预计需要7年时间来找到它。

现在，寻找最优哥隆尺的任意n阶复杂性是未知的。尽管一些人推测说哥隆尺是NP问题，不过涉及到哥隆尺的NP问题领域还没有被发现，也就是说，没有对于寻找哥隆尺的完全NP问题。

已经发现的最优哥隆尺

order	length	marks
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 0 3 4 9 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

参考资料

• Gardner, Martin. Mathematical games. Scientific American. 1972.March: 108–112. 
• http://en.wikipedia.org/wiki/Golomb_ruler
• http://mathworld.wolfram.com/GolombRuler.html
• http://www.research.ibm.com/people/s/shearer/grtab.html
• http://www.distributed.net/ogr/