上一页

ⓘ 哥隆尺问题




哥隆尺问题
                                     

ⓘ 哥隆尺问题

哥隆尺问题 (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问题。