数学研发论坛

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

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

  [复制链接]
发表于 2009-11-11 14:57:44 | 显示全部楼层
请教mathe,我的想法对不对:
按您的程序全部算完并处理完结果后,有两种可能
1.找到20棵树的24行种树法(很容易验证是否正确)。
2.没有找到20棵树的24行种树法,是否能推出不存在20棵树的24行种树法(包括实数点种法)?

另:我又找到一台机器(虽然运算较快,但不能24小时计算),开始计算fid29。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-11 15:35:06 | 显示全部楼层
呵,若大伙都像您这样积极,踊跃参与合作,那将提前完成...
但是,好像并没有想象中的那么好哟..
计算的确很费时,我想在一个月内出结果就已经很不错了....
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-11 16:18:53 | 显示全部楼层
请教mathe,我的想法对不对:
按您的程序全部算完并处理完结果后,有两种可能
1.找到20棵树的24行种树法(很容易验证是否正确)。
2.没有找到20棵树的24行种树法,是否能推出不存在20棵树的24行种树法(包括实数点 ...
sheng_jianguo 发表于 2009-11-11 14:57

如果没有找到,还不能否定,有两个原因:
i)这里搜索的还不是全部集合,只有部分集合。另外一部分我过去试着同无心人计算过,没有找到解,但是后来发现那部分代码还是有bug.
ii)计算中为了提高速度,使用了有限域;虽然由于这个有限域阶数充分大,大部分情况同复数域下的解相同,但是我们无法保证解完全相同(但是有很大的理由相信会有相同的最优解)。比如我现在同样的代码计算出的18棵树以下的最优解都同过去的一样(而且还可以轻松的找出最优的复数解和整数解)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-12 10:25:20 | 显示全部楼层
请教mathe:
为什么中断程序后计算时间(第二个数)明显减少?有问题吗?
注:为了比较,中断程序后我将tag文件中的数字1257改为1255。
AAA.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-12 11:02:22 | 显示全部楼层
处理每行数据的时间是前后两个时间的差值。
相差很明显吗?如果有细微的差别,应该比较正常。通常不应该有很大的变化
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-12 11:57:29 | 显示全部楼层
呵,计算进展缓慢哟,通过三天的时间(每天7小时),才计算到3000行哟。。。。
不知道一个月时间能否算完。。

顺便问一句:算完后,程序给出什么提示吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-15 20:22:35 | 显示全部楼层
请教mathe,我的想法对不对:
按您的程序全部算完并处理完结果后,有两种可能
1.找到20棵树的24行种树法(很容易验证是否正确)。
2.没有找到20棵树的24行种树法,是否能推出不存在20棵树的24行种树法(包括实数点 ...
sheng_jianguo 发表于 2009-11-11 14:57

还发现了一个问题。程序中使用了一个过滤:
        if(n==18&&!checkDegreeN18())
                return;
        if(n==19&&!checkDegreeN19())
                return;
        if(n==20&&!checkDegreeN20())
                return;
在这个条件下,不考虑使用了有限域,那么
1.如果找到了24行结果
   i)如果能够使用这些24行结果继续构造25行结果,最优结果为25行
   ii)如果不能使用它们构造25行结果,最优结果为24行
2.如果没有找到24行结果
  那么不存在25行结果,但是不能排除24行结果存在的可能。
如果删除代码中上面6行,那么如果没有找到24行结果就说明不存在24行结果了。不过我还没有测试删除上面6行代码对速度的影响。等我第一部分运行完测试一下(很快就要结束了)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-15 20:23:53 | 显示全部楼层
呵,计算进展缓慢哟,通过三天的时间(每天7小时),才计算到3000行哟。。。。
不知道一个月时间能否算完。。

顺便问一句:算完后,程序给出什么提示吗?
数学星空 发表于 2009-11-12 11:57

没给提示,不过程序结束,命令行的提示符会出来
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-16 09:12:14 | 显示全部楼层
现在做了一下测试,发现删除哪些过滤条件后,程序丝毫没有变慢,反而可能变快一些(不过程序运行时间还是挺不稳定的,所以到底是否便快不好判断)。
所以删除了过滤条件重新编译了一下。此外,发现直接用s8m(旧的过滤算法,更慢,但是效率更加高)来过滤也不会导致速度变慢,所以也做了相应的修改。只是修改以后,输出文件target20通常都会是空的。如果产生了一个结果,那么是合法解的可能性会非常大。
另外,将程序分别用intel c++编译器和vc编译。
第一个版本是intel c++编译器编译的结果
binary.icc.zip (130.98 KB, 下载次数: 2)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-16 09:15:35 | 显示全部楼层
我绝对对于已经运行过的数据,就暂时没有必要重复运行了,不过对于后面的数据,可以换新的程序,好像速度可以提高一些(而且搜索范围更大)。不过解压上面程序覆盖原先可执行程序时,最好先备份一下tag和target20文件,我好像不小心覆盖了,所以现在tid1又重新运行了(快结束了,没找到一个解)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-6-17 12:50 , Processed in 0.142326 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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