正在考虑将优美树验证做成分布式，请大家给点意见

fwjmath

以下是优美树的简单介绍：

关于优美图、优美树和优美标号的介绍，请参看这两个链接：

http://topic.csdn.net/u/20080322 ... 3-87367c452985.html

http://en.wikipedia.org/wiki/Graceful_labeling

简单地说，假设有一颗树T拥有n个顶点，如果存在对顶点的一个由0至n-1的不重不漏的标号方法，使每条边由此诱导出来的标号（即为边的两个顶点标号的差的绝对值）为从1到n-1的不重不漏的n-1个数的话，那么我们称这个标号方案是一个优美标号，而这棵树也被称为优美的。注意，在这里关于优美性的论述只对于树有效。

图论中著名的Ringel-Kotzig猜想断言：所有的树都是优美的。这是一个尚未证明而意义重大的猜想。曾经有很多人尝试证明这个猜想，但都没有成功。而也有人对这个猜想进行数值上的验证。在此之前的记录是任意含有29个顶点的树都是优美的，这个结论是由Michael Horton在10台计算机上用了总计58天的CPU时间作出的。

在 http://www.equn.com/forum/thread-2506-5-1.html 这里页面中部，JUST提出了优美树的标号验证可以作为一个分布式计算项目。经过了超过半年的研究，我已经将验证结果推进到n=31了，而现在的算法改进的余地我不敢说没有，但是至少我是想不出来了。而n=31的运算在我的双核机器上也需要一个月（已经将结果“分布式”到了两个核上了）。如果有订阅我的空间的朋友应该也会知道这回事。这也是我今年TIPE（法国的一种考试，考生需要订出自己的研究题目并向考官讲述研究结果）的题目。
我当然很希望把这个东西做成分布式计算项目，经过很长时间的考虑，根据实际情况来说的话我有如下的想法：

1. 首先，我现在还是学生，所以也没有精力慢慢学习BOINC的整个系统，况且也没有能掌握的服务器，学了也没用。当然自己写就更加不可想象了。所以，项目大概会采取如同3x+1项目的形式，也就是说以电子邮件的形式来分配WU。当然，到以后条件成熟之后或许可以转型到BOINC上。由于这个限制，所以项目的WU可能会比较长，至少5天左右，而且没有容易使用的界面。
2. 其次，由于现在这个题目是我TIPE的题目，由于避嫌和保护之故，暂时源代码和算法可能都不能完全公开，应该要起码等到我考完这个试之后才能公开。这也是迫不得已之举，因为我想搞这个项目的其中一个目的也是为了优化算法。

这就是基本的考虑。我打算找一个稳定点的空间来做这个事情。我申请过一个GooglePages，但是现在不知道国内能不能访问。不过在撰写好众多页面之前这个问题还不需要考虑太多。我可能最近会着手将我写的在本机上运行的程序改造成适合分布式计算的，还要再写一点使用教程FAQ之类的，不过好在这个可以抄~~~
不过大家也不要对我抱太大期望。之前有个想法已经流产过一次了，这个也不担保不会流产，但是我会尽最大努力的。之所以还在这里说这个，主要是因为想征求大家的意见，特别是在如下方面：

1. 对于一个通过电子邮件来分配WU的项目，WU的长度和期限大概是怎么样才比较合适？3x+1项目的长度和期限分别为12天和3个月。
2. 大家希望计算程序的命令行显示一些什么信息？初步考虑是计算进度和时间。
3. 结果文件的大小怎么样会比较合适？3x+1项目的结果文件大概是几百KB。这个问题的答案对程序参数的调整很重要。
4. 由于问题的特性，进度可能会出现前快后慢的情况，而且非常难纠正这种偏差，这样子能接受吗？

谢谢大家合作~~~

fwjmath

附两张优美树的近照

扎西

虽然不懂，还是要支持你：）

昂宿星团人

同。。。

Julian_Yuen

3楼4楼

+65536

BiscuiT

不懂+1
支持+9

fwjmath

大家支持之余可不可以回答一下问题啊~~~
这篇东西的核心是那四个问题~~~

扎西

1. 对于一个通过电子邮件来分配WU的项目，WU的长度和期限大概是怎么样才比较合适？3x+1项目的长度和期限分别为12天和3个月。
-连CPDN都敢碰，其他的都不怕了。
2. 大家希望计算程序的命令行显示一些什么信息？初步考虑是计算进度和时间。
-信息不用太复杂，效率是最重要的，可以参考sob的显示
3. 结果文件的大小怎么样会比较合适？3x+1项目的结果文件大概是几百KB。这个问题的答案对程序参数的调整很重要。
-这个不了解，不能给出建议，只要不影响上传就行。
4. 由于问题的特性，进度可能会出现前快后慢的情况，而且非常难纠正这种偏差，这样子能接受吗？
-能接受

[ 本帖最后由 扎西日泰 于 2008-11-21 14:53 编辑 ]

扎西

幸好订阅了equn论坛的rss，不然还不知道又出了一个新咱们自己人搞的新项目

Youth

支持

之前没算过3x+1，不太习惯电子邮件分配wu的方式（至少听上去不太习惯。。。 ），希望以后有可能的话还是能跑在boinc之类的平台上：）

Youth

1. 3x+1的长度和期限听上去还可以，可以参考，不过只要程序稳定不容易出问题，长度的因素可能不是太重要
2. 进度和时间差不多了
3. 只要不是大得夸张，大家的网络应该大都没问题吧
4. 最好偏差不要太大：）

Julian_Yuen

1. 对于一个通过电子邮件来分配WU的项目，WU的长度和期限大概是怎么样才比较合适？3x+1项目的长度和期限分别为12天和3个月。
同Youth。但个人建议如果条件许可的话，时间不要太长，以免让配置较低的机器参与起来很吃力。

2. 大家希望计算程序的命令行显示一些什么信息？初步考虑是计算进度和时间。
考虑带图形了麽？或者计算WU完成之后，秀一下计算结果也可以。

3. 结果文件的大小怎么样会比较合适？3x+1项目的结果文件大概是几百KB。这个问题的答案对程序参数的调整很重要。
结果的大小暂且不谈，但我想说说email传送数据的问题。网络慢的时候，有可能会出现附件不完全的情况。
如果计算没有错误，仅仅是上传的问题，那会很可惜。打压缩包的话，既节约邮件大小，也能通过压缩文件的校验来检测是否完整。

4. 由于问题的特性，进度可能会出现前快后慢的情况，而且非常难纠正这种偏差，这样子能接受吗？
是指计算进度不是线性的麽？我指随着n增加，可能会带来越来越大的计算量，是么？
还是说项目的完成进度？
不过我倒是可以接受的，不管怎样。

5.建议：如果时间充裕的话，能够把WU的具体分配情况记录下来，最好。
比如，某WU合适分配给某几人，然后何时谁回传了完成结果。当然，没时间也就算了

昂宿星团人

1. 对于一个通过电子邮件来分配WU的项目，WU的长度和期限大概是怎么样才比较合适？3x+1项目的长度和期限分别为12天和3个月。
没想法。。。

2. 大家希望计算程序的命令行显示一些什么信息？初步考虑是计算进度和时间。
再加上图形吧？

3. 结果文件的大小怎么样会比较合适？3x+1项目的结果文件大概是几百KB。这个问题的答案对程序参数的调整很重要。
个人认为小一点比较好。。。

4. 由于问题的特性，进度可能会出现前快后慢的情况，而且非常难纠正这种偏差，这样子能接受吗？
完全不在意~

扎西

对于用邮件来分配wu我觉得问题不大，只要不是一次只能接受、计算和上传一个WU就行。

fwjmath

计算进度的偏差指的是在一个WU的开头和结尾，一个百分点需要的时间是不同的~~~可能相差十几倍~~~
WU的具体分配是肯定会记下来的~~~