热门问题
时间线
聊天
视角

哥隆尺問題

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

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