哥隆尺问题

✍ dations ◷ 2025-04-04 04:57:06 #数论

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

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

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

Distributed.net已经利用大规模分散式平行计算完成了对24阶到27阶最优哥隆尺的寻找。Distributed.net已于2014年2月开始寻找28阶最优哥隆尺。

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

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

相关

  • 视网膜色素变性 19视网膜色素变性,或称视网膜色素病变(Retinitis Pigmentosa,简称RP),是一种遗传性眼科疾病。初期普遍的病征是夜盲、视野变窄,可以看到正前方景物,但略偏左右的视野就无法看见,RP病人
  • 铋溴酚铋溴酚(国际非专利药品名称为Bibrocathol,商品名称为Noviform及 Posiformin)是一种含铋的有机化合物,对粘膜和创伤具有杀菌、收敛和抑制分泌的作用。其作用机制可以用其分子结构
  • 分点分点(英语:equinox,或称二分点)是想像中天球赤道在天球上的位置,是每年太阳穿过天球赤道和黄道在天球上交点的天文事件,这造成地球上各地的白天和夜晚几乎等长。只有在分点的瞬间,
  • 朱一是朱一是,字近修,号欠庵。明末清初浙江海宁人。生卒年不详。本为诸生,擅长写科举时文,是考生指南。与范路等为“梅里八友”。崇祯十五年举人。甲申后自署“欠庵”,自谓“惟欠一死”
  • 陈周全陈周全(?-1795年),又名陈周,原籍清朝福建泉州府同安,于18世纪末于台湾发动民变。陈周全为1790年代在台湾天地会的首领。1792年,前往福建同安起事,事败之后,连同残余兵力返回台湾。同年
  • 突尼斯行省16世奥斯曼帝国征服突尼斯,成为奥斯曼帝国的突尼斯(省)。1516年奥斯曼帝国征服突尼斯,但不久却被西班牙帝国夺走,直到最后奥斯曼帝国才在1574年从西班牙重新占领突尼斯并展开统治
  • 许文岐许文岐(?-1643年),字我西,浙江仁和县人。晚明政治人物。许文岐出身簪缨世家。于崇祯七年(1634年)中式进士,授南京兵部主事,升南京兵部职方司郎中。当时民变蜂起,江北混乱,许文岐辅佐尚书
  • The EastLight.The EastLight.(朝鲜语:더 이스트라이트),韩国Media Line于2016年所推出的男子乐团,成员包括李硕澈、李恩成、李胜铉、金埈煜、丁俟江及李宇镇。歌迷官方名称为“Sun”。乐队成员
  • 白美清白美清(1931年-),男,四川华阳人,中华人民共和国政治人物,曾任国务院副秘书长,中华人民共和国商业部、国内贸易部副部长,第八届全国人大代表。
  • 风吹了《风吹了》(日语:風立ちぬ、かぜたちぬ,另译名《起风了》、《风雪黄昏》、《风起》及《起风》)是日本小说家堀辰雄于1936年发表的中篇小说,小说内容建立在作者自身的经历之上,一共