数学研发论坛

 找回密码
 欢迎注册
楼主: 0→∞

[求助] 果树问题讨论:这两个问题等价么?

  [复制链接]
发表于 2008-11-25 16:31:51 | 显示全部楼层
18颗树结果出来了,最多18行。而242#已经给出了一个18行的例子

评分

参与人数 3威望 +2 金币 +2 鲜花 +2 收起 理由
gxqcn + 2 终于开花结果了。:)
liangbch + 2
无心人 + 2 鼓励下

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 21:16:06 | 显示全部楼层
我还想到一个方法也许可以用来计算T18.也就是搜索过程中可以将解方程的那个程序同搜索算法结合起来,保存解方程程序的中间状态,然后搜索过程每添加一条边,相当于在方程组中添加一条二次等式,然后继续判断是否会得出矛盾;如果得出矛盾,直接将这个数据裁减掉。这样计算T18空间复杂度肯定没有问题。不过时间复杂度会挺大的。
现在计算出来的T17总共大概15G的数据,其中13条边的7G多,基本上没有可以淘汰的数据;14条边的7G多,但是应该大部分可以淘汰,估计最后可以只留下一个几十个M的文件。而15条以上边的已经全部计算出来,也就几百个数据。
但是从T17到T18,其中13条边的情况的7G数据约1000万个数据,如果每秒处理完一个数据的搜索(同时裁减),大概总共需要116天。如果4个CPU,那么除以4倍,一个月时间。但是如果速度还要慢一倍,那么就麻烦了。
当然还有一个解决方案是做成一个分布式的版本,让无心人的50台机器同时运行,也许能够在几天内就解决。
不过上面几个过程的编程都非常复杂,比如组合解方程程序和搜索程序就已经挺复杂了。而将程序做成一个分布式版本更加复杂。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-25 21:26:27 | 显示全部楼层


分布版,读写文件不能太狠
不能影响学生上课啊
如果占资源少于20%
可以考虑上150台机器

点评

哈哈  发表于 2013-12-10 22:11
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-26 08:02:54 | 显示全部楼层
我想到一个可能可以使用的解方程的新算法,等有时间试一试这个新算法看看。写分布版本的程序很花费时间的,还要考虑网络通讯(当然读写文件会很低,大部分操作会放在CPU上),还是最后考虑吧。说实在,如果能够在单机上花一两个月就可以解决的问题,我还是不愿意花时间去写分布式的版本的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-26 08:07:07 | 显示全部楼层


你能调动多少台机器?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-26 08:09:29 | 显示全部楼层
我有一台Linux(2个双核),和两台Windows.
不过一台Windows比较慢,通常我不怎么用,另外一台通常在上面工作也不怎么用,所以就一台。
而且我前面计算过程都没有使用多线程。当时有时候会用多个进程运行程序的不同部分。通常最多两个进程,因为还需要留下CPU时间调试程序和做一些测试
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-26 08:14:37 | 显示全部楼层
等于说并行程度不高啊
另外,网络程序可以考虑命名管道通讯协议
简单
呵呵
当然,实时性差了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-26 08:27:11 | 显示全部楼层
并行度非常高,其实通讯部分占的比例也很低,这些都不是大问题,主要是搭程序的框架。
显示服务器对一些数据进行划分,然后平均非配给各个机器进行计算(这是主要部分)。
计算完以后,所有数据再在服务器上进行合并(淘汰重复数据,平均每个数据重复出现5次左右),然后服务器对合并以后的数据再次划分,平均分配给各个机器就可以了。
不过最近我不想再写代码了,歇息歇息。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-26 08:38:39 | 显示全部楼层
学习haskell吧
休息下因为C++劳累的大脑
体验下轻松编程的乐趣

点评

:)  发表于 2013-12-10 22:13
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-26 08:52:35 | 显示全部楼层
你有比较好的文档吗?可以在接下去一段时间先看一看文档
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-1-20 15:19 , Processed in 0.100569 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表