热门问题
时间线
聊天
视角

哥隆尺问题

来自维基百科,自由的百科全书

哥隆尺问题
Remove ads

哥隆尺问题(Golomb ruler),是如何在一把尺上划分刻度,使所有刻度彼此之间的距离都不相同。刻度的数目称为阶,而两个刻度间最长的距离为长度。对哥隆尺做平移或镜像并不影响结果,因此习惯上将最小刻度设为 0 。

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

哥隆尺是由Sidon[1]和Babcock[2]各自独立发现,并且以数学家所罗门·格伦布的名字命名。

哥隆尺不需要能够测量到其自身长度为止的所有距离,如果能够的话,称为完美哥隆尺。已经证明不存在五阶以上的完美哥隆尺[3]。最优哥隆尺则是同一阶中长度最短的哥隆尺。生成哥隆尺是简单的,但是找到一个指定阶的最优哥隆尺是的一个有挑战性的计算项目。

Distributed.net页面存档备份,存于互联网档案馆)已经利用大规模分散式平行计算完成了对24阶到28阶最优哥隆尺的寻找。Distributed.net于2014年2月开始寻找28阶最优哥隆尺,并于2022年11月23日完成。[4]

目前,寻找n阶最优哥隆尺的复杂度是未知的,有人猜测这是NP困难问题[3]

Remove ads

已经发现的最优哥隆尺

下表列出了目前已知的最优哥隆尺。

更多信息 阶, 长度 ...
Remove ads

参考资料

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads