distributed.net - OGR - 最简优化尺 - 项目介绍

Youth

有点没看太明白，到底OGR是确定刻度线数量找最短的尺，还是确定尺的长度寻找最少的刻度线数量？我感觉应该是前者，但看大仙的说明又似乎说的是后者

fwjmath

应该是确定刻度线的数量，然后寻求尺最大的长度n，同时满足这把尺利用刻度线能够量出从1到n的所有长度~~~

Youth

最大的长度？

the shortest Golomb Ruler possible for a given number of marks？

fwjmath

重新看了定义~~~发现以前理解错了~~~Golomb Ruler定义就是没有两个刻度之间的差是相等的~~~然后确定刻度的数量求尺的最短长度~~~因为短到了一个程度以后显然会有重复的刻度差~~~

cnchina

http://www.rechenkraft.net/yoyo/
YOYO@HOME似乎是这个项目在BOINC下的一个转接？
yoyo@home is a wrapper of the distributed.net client and runs OGR work units. On distributed.net stats server this project is registered with a own account. All distributed.net stats will be credited on this.
You can participate by downloading and running a free program on your computer.


另外，刚才看到个新闻，这个OGR-25 项目已经完成超过70%，预计在2008年年中的时候完成这一个阶段。
27.09.2007 OGR project status
OGR has now completed more than 70% of its search space. Some predictions predict the end for the mid of 2008.

碧城仙

那前面翻译的内容是不是要改啊？我也糊涂了。我的理解是先给定了某长度为 n 的尺子，原本只有 0 和 n 两条刻度线，现在要做的是加上几条刻度线，项目研究的是如何加刻度线，能使刻度线条数最少，且能测量 0~n 之间的任何整数长度。

fwjmath

似乎的确要修改~~~在wiki上面查到的定义是：

In mathematics, a Golomb ruler, named for Solomon W. Golomb and discovered independently by Sidon[1] and Babcock,[2] is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart.

这里没有说要满足所有距离都能量出来，只需要任意两对不同标记（可以有一个标记在两对中均出现，但是不能两对都是一样的）之间的距离不同就可以了~~~

碧城仙

好像确实不需要满足能测量所有距离。只要能测量的距离不重复就是满足要求的了。

1 楼的翻译里只需要修改部分“每一个整数距离”就行了。1 楼翻译里也有提到“因为 Golomb 尺不必得到所有长度的距离值，仅仅要求精确的距离值。我们所希望得到‘最简优化的 Golomb 尺’的目标是刻度数目尽可能的少，而不重复任何可用于测量的距离。 ”

fwjmath

的确~~~不影响大部分的结果~~~

Wetman

NP问题在编程里好像是无法用标准算法解决的问题啊……

Wetman

另外这个项目到底在解决什么问题？这个尺是可以无限增长的，如果它是在不停地枚举总长度n的话岂不是永远没完没了了？或者它是在找最优化刻度的规律？

fwjmath

关于NP问题，按照现在研究的说法是还没有找到时间复杂度为多项式的算法，也还不能证明没有这样的算法。很多NP问题在规模较小的时候可以在一个合理的时间内解决，但这个时间复杂度大于多项式而已~~~
关于OGR，这个尺的长度的确可以无限增长，的确是没完没了的。但是算出来的这些可能对以后彻底解决这个问题有帮助，所以还是有意义的。