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

Julian_Yuen · 发表于 2008-11-23 01:25:39

嗯，的确是可以继续算的

现在计算还是挺正常的。
----
你这种情况倒是真的很惨，呵呵，pre-alpha版本....囧rz

fwjmath · 发表于 2008-11-23 02:45:32

没办法啊~~~我之前自己运行的版本输出的数据比现在给大家的这个版本要少得多~~~如果真的认真做起检查点的话性能就不能保证了~~~所以只能随便做一个凑合着~~~于是惨剧就发生了~~~

烦人 · 发表于 2008-11-24 21:08:20

我现在对这个项目的理解还是比较模糊（从初中开始数学就没学好过

），想知道对于定点数量固定的一个树，可以排列出多少不同的树？有计算公式吗？比如我们现在计算的，31个顶点一共有多少种组合呢？对于每一种可能的组合都需要进行验证吗？

[ 本帖最后由烦人于 2008-11-24 21:09 编辑 ]

fwjmath · 发表于 2008-11-24 23:32:42

现在对于顶点数目固定的树的数量还没有一个确切的计算公式，只有一个大约的估计。现在只有通过枚举也可以计算出精确的数目。
现在计算的是有32个顶点的树，一共有109972410221棵，大概就是一千亿棵。几乎对于每一棵都要进行验证。
有一些树是已知为优美的，但是所占比例很少。
有人猜想为一棵树寻找一个优美标号是一个NP问题，也就是说不能找到非常有效的算法。

BiscuiT · 发表于 2008-11-24 23:46:14

32
50
2
10997242

我收到的 data.txt 里面的这些是表示什么？
每个人收到的包要验算多少棵树了？

fwjmath · 发表于 2008-11-25 00:14:13

第一行是顶点数
第二行是一共分多少个包
第三行是这个包的编号
第四行是顶点数一定的树的总数目的万分之一

收到的包要验算的树的数目就是第四行乘以一万再除以第二行~~~
现在的包每人要验算2.2*10^9也就是大概二十亿棵~~~

BiscuiT · 发表于 2008-11-25 00:47:09

那33个顶点的树会有多少了？感觉好像会增长的很快。。

fwjmath · 发表于 2008-11-25 04:00:34

我根据现在的资料估算了一下~~~33个顶点的树差不多有三千亿棵~~~
这个是指数增长的~~~增长得还是非常快的~~~

Julian_Yuen · 发表于 2008-11-25 07:55:02

指数...

烦人 · 发表于 2008-11-25 10:07:22

恩。。啊。。我们现在验证的是32个顶点的树。。。

BiscuiT · 发表于 2008-11-25 11:27:38

这不是一下子就碰壁了吗。。

Julian_Yuen · 发表于 2008-11-25 12:05:29

1

不把任务分小的话，是无法体现分布式的用处的....

fwjmath · 发表于 2008-11-25 19:48:19

不急不急~~~我们还有摩尔定律~~~用指数对抗指数~~~

BiscuiT · 发表于 2008-11-25 21:01:38

现在一个包可以验算20亿颗树。。
不知道要多久能跟gimps那样。。
一个人只爬一棵树。。还要爬个一年半载。。

Julian_Yuen · 发表于 2008-11-25 21:07:59

70巴仙了

		自动登录	找回密码
密码			新注册用户

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

回复 #30 fwjmath 的帖子

回复 #31 Julian_Yuen 的帖子

回复 #33 烦人的帖子

回复 #35 BiscuiT 的帖子

回复 #36 fwjmath 的帖子

回复 #37 BiscuiT 的帖子

回复 #34 fwjmath 的帖子

回复 #38 fwjmath 的帖子

回复 #41 BiscuiT 的帖子

回复 #41 BiscuiT 的帖子

回复 #43 fwjmath 的帖子

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

回复 #30 fwjmath 的帖子

回复 #31 Julian_Yuen 的帖子

回复 #33 烦人 的帖子

回复 #35 BiscuiT 的帖子

回复 #36 fwjmath 的帖子

回复 #37 BiscuiT 的帖子

回复 #34 fwjmath 的帖子

回复 #38 fwjmath 的帖子

回复 #41 BiscuiT 的帖子

回复 #41 BiscuiT 的帖子

回复 #43 fwjmath 的帖子

回复 #33 烦人的帖子