|
|
英文介绍见官方网站：
http://www.distributed.net/
http://www.distributed.net/ogr/
========
What is a Golomb Ruler anyway?
In mathematics, the term "Golomb Ruler" refers to a set of non-negative integers such that no two distinct pairs of numbers from the set have the same difference. Conceptually, this is similar to a ruler constructed in such a way that no two pairs of marks measure the same distance. An Optimal Golomb Ruler (OGR) is the shortest Golomb Ruler possible for a given number of marks. However, finding (and proving) OGR's becomes exponentially more difficult as the number of marks increases, and it is for this reason that we have turned to the web for help in finding the OGR's with 24 and more marks.
Golomb rulers are named after Dr. Solomon W. Golomb, a professor of Mathematics with a special interest in combinatorial analysis, number theory, coding theory and communications. Dr. Golomb also has an interest in mathematical games and puzzles, having been a contributer to many columns in the Scientific American "Mathematical Games". OGR's have many applications including sensor placements for X-ray crystallography and radio astronomy. Golomb rulers can also play a significant role in combinatorics, coding theory and communications, and Dr. Golomb was one of the first to analyze them for use in these areas.
A Golomb ruler is a way to place marks along a line such that each pair of marks measures a unique linear distance. Here is a Golomb ruler with five marks:
| | | | |
0 1 4 9 11
The number below the mark is the distance from the left edge. The length of this ruler is 11, and it happens to be one of the two shortest such rulers with five marks. The other ruler has marks at positions 0, 3, 4, 9, and 11. (The mirror images of these two rulers, 0, 2, 7, 10, 11 and 0, 2, 7, 8, 11, are also optimal Golomb rulers. Usually just one of each mirror-image pair is mentioned.)
You can check that the above ruler is indeed Golomb by writing out a table of all the pairs of marks and their respective distances:
Mark1 Mark2 Distance
0 1 1
0 4 4
0 9 9
0 11 11
1 4 3
1 9 8
1 11 10
4 9 5
4 11 7
9 11 2
Note that there are no duplicated distances in the third column. There is also no distance 6, but that is okay because Golomb rulers don't have to measure each distance, only distinct distances.
The goal of "optimizing" Golomb rulers is to get them as short as possible, while not duplicating any measured distances. The two 5-mark rulers above are optimal.
Golomb rulers are usually characterized by their differences, rather than absolute distances as in the above diagram. So the above ruler would be 1-3-5-2 (sometimes this is written as 0-1-3-5-2 but the leading zero is often dropped).
For example, the current best known 21-mark ruler is the following:
2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4
James B. Shearer has compiled a list of all the best known Golomb rulers up to 150 marks. If you're comparing rulers, note that the 21-mark ruler listed on James' page is the mirror image of the one above.
Unfortunately, the search for OGRs becomes exponentially more difficult as the number of marks increases (similar to what mathematicians call "Np complete" problems ... like the infamous Traveling Salesman optimization).
========
中文翻译如下：
翻译人：碧城仙 中国分布式计算总站版权所有
什么是 Golomb 尺?
在数学领域里面, 术语“Golomb 尺”是从非负整数集中任取一组数字，将这些数字按照从小到大的顺序排成一条直线，然后将每一个数字都与最左边的数字相减得到“距离值”（类似于绝对值的定义，绝对值定义中最左边的数字为 0），每个在尺上的数字与最左边的数字距离都不可以相同，按照这样的标准制作的尺子就是“Golomb 尺”（实际中并不做成真正的尺子，其意义并不在此）。寻找“Golomb 尺”的数字排列非常困难，其困难程度随标记数字数目的增加而指数性增大。
什么是“最优 Golomb 尺问题”（OGR）？
所谓 Golomb 尺是指在一个固定整数长度的尺上不等长地划分最少的刻度，并能用此尺度量由1到该整数的每一个单位的问题。例如 OGR－6 是在 6cm 的尺上按 0、1、4、6 划分刻度，即可连续量度 1、2、3、4、5、6cm 的每一距离。
Golomb 尺是以 Solomon W. Golomb 博士的名字命名的，Solomon W. Golomb 是一位对排列组合、数论、编码理论和通讯特别感兴趣的数学教授。Golomb 博士也对数学上的比赛和迷题很感兴趣，在美国繁荣科学月刊里就有许多“数学比赛”。 OGR 在 X-射线传导结晶学和射电天文学上应用广泛。另外，Golomb 尺在组合数学、编程理论和通信领域亦扮演着非常重要的角色，而 Solomon W. Golomb 博士则是率先将 Golomb 尺理论应用于这些领域中的先驱之一。
Golomb 尺问题要寻找出一种能够在一段特定长度的线上标记刻度的最优方案。下面就是一个最简优化尺的例子，它有五个刻度：
| | | | |
0 1 4 9 11
上面的例子中，在标记线下面的数字是该条标记线到最左边一条线的绝对距离。这把 Golomb 尺长度为 11，上面的例子碰巧是只用 5 个刻度的最简优化尺之一。11 单位长度标记刻度的方案还有以下两种：0、3、4、9、11 和 0、2、7、8、11。在寻找最简优化尺的过程中，通常希望能够找到所有可能的组合。
您可以试着在您的桌子上比画比画来验证一下例子中的刻度是否满足“最优 Golomb 尺问题”的要求：
Mark1（左边的刻度线）， Mark2（右边的刻度线）， Distance（可供测量的长度）
0 1 1
0 4 4
0 9 9
0 11 11
1 4 3
1 9 8
1 11 10
4 9 5
4 11 7
9 11 2
可以注意到第三列中没有重复的距离值，也没有距离值 6，但同样是满足要求的，因为 Golomb 尺不必得到所有长度的距离值，仅仅要求精确的距离值。
我们所希望得到“最简优化的 Golomb 尺”的目标是刻度数目尽可能的少，而不重复任何可用于测量的距离。上面所提到的两个 5 条刻度的尺子无疑是最简优化的！
Golomb 尺为了方便描叙，通常采取与例子不同的表示方法，比如例子可以表示为 1-3-5-2（1、3、5、2分别是每相邻的两条刻度线的“间距”），有时也表示成 0-1-3-5-2 的形式，最前面的 0 可以省略不写。
例如，当前已知的最完美的 21 条刻度线的尺子的表示形式如下：
2-22-32-21-5-1-12-34-15-35-7-9-60-10-20-8-3-14-19-4
James B. Shearer 已经把目前业已找到的 Golomb 尺的按照刻度数目从 1 到 150 列出了一张清单。您可以到 http://www.research.ibm.com/people/s/shearer/grtab.html 页面查看。如果您比较细心，您一定会发现我们前面所举的 21 条刻度线的例子就在 James B. Shearer 的列表中。
但是很不幸的是，随着刻度数目的增加，寻找 OGRs 变得越来越艰难！（其困难程度可与被数学家公认的两个臭名昭著的问题——“P-NP”问题、“旅行商”问题——相抗衡！）
附注：(由 碧城仙 添加)
1. “P 与 NP”问题:
P－问题即是可被“运行多项式时间的”一个算法解决的问题 (多项式时间: 运行时间最多是输入量的多项式函数)； NP－问题即是有一个“可用多项式时间检验的”解答的问题。是否 P = NP？
该问题排位“新千年急待解决的 7 大数学问题”之首！
2.“旅行商”问题( Traveling Saleman Problem，简称 TSP )：
已知 n 个城市之间的相互距离，现有一个推销员必须遍访这 n 个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
（未完待续，如有错误，敬请指正，谢谢！中国分布式计算总站版权所有） |
评分
-
查看全部评分
|
发表于 2005-1-24 15:08:11
发表于 2005-9-5 01:17:29
发表于 2006-2-11 21:11:38