数学研发论坛

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

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

  [复制链接]
发表于 2009-11-26 11:09:57 | 显示全部楼层
昨天开始重新整理了一个程序。这个只需要一个可执行程序(也只有一个线程)。
感觉应该比前一个版本快一些。我在Linux下面测试了一下fid7,好像比原先版本应该能够快一倍左右的速度。而且程序还会同时试着搜索一些20棵树23行的结果。
另外一个好处是程序可以统一处理所有16棵树的输入,然后扩展产生20棵树23行的结果,而不像上一个版本只能处理16棵树11行的输入结果
不过这个程序还没有经过足够的测试,所以下面仅仅将原代码附在这里,而没有附带可执行程序。
而且程序的输出结果在标准输出,而不是target20文件
find2.zip (10.44 KB, 下载次数: 3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-26 11:27:40 | 显示全部楼层
计算人员:数学星空
开始时间:
计算文件:fid2
当前文件大小:0
进度:20000
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-26 12:31:22 | 显示全部楼层
计算人员:Frankenstein
开始时间:09.11.22
计算文件:fid4
当前文件大小:0
进度:
计算机1:0~11031
计算机2:15000~16281
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-26 13:19:07 | 显示全部楼层
昨天开始重新整理了一个程序。这个只需要一个可执行程序(也只有一个线程)。
感觉应该比前一个版本快一些。我在Linux下面测试了一下fid7,好像比原先版本应该能够快一倍左右的速度。而且程序还会同时试着搜索一些20 ...
mathe 发表于 2009-11-26 11:09

想法很好,应仔细分析、总结程序解决问题的每一步骤,尽早发现所有bug。
由于没有找到24行解法可能性非常大,“现代数学三大难题”之一的“20棵树植树问题”被成功破解的难点可能就剩下论证程序的正确性
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-26 13:53:31 | 显示全部楼层
现在测试的结果是这个程序速度比我们现在使用的还慢(也许是因为为了找更多的23行解而导致搜索空间增加),所以就没有必要继续测试了。
而现在版本的程序的可靠性已经比较高了,至少现在我们已经知道的一些特殊解(比如已经知道的17棵树16行的结果,18棵树18行的结果,20棵树23行的结果)都能够成功找到。
至于完全解决20棵树问题,还需要一个使用有理数而不是有限域上数的版本才能够完全确信。现在的方法只是可以带给我们极大的信心最优解为我们所找到的。
根据我过去的经验,如果直接使用gmp中的有理数库替换程序s8m.cpp中的有限域中的数,程序速度估计要慢10倍左右,这个对于我们现在的计算量是不可以忍受的,所以我没有去尝试。
不过考虑到实际上参与运算的有理数通常分子分母都不会太大,而且程序如果设计的好,可以只使用整数而不是分数。所以如果设计良好,可以设计一个整数版本的s8m.cpp(只使用普通32比特的整数),但是要添加一个计算溢出判断(如果计算溢出,抛出异常,中断当前的过滤,认为这个解可能是潜在的合法解即可)。估计这样处理以后的程序比现在版本不会慢多少,这个应该是比较可行的方案。
不过还有两个问题:
i)让所有解方程过程只使用整数而不是有理数(或有限域中的数),我们需要避免所有除法运算,为此代码要复杂很多,我们需要花费不少时间修改这一部分代码以及测试
ii)对所有运算需要添加溢出判断和异常处理,这一步要相对容易很多。但是如何高效实现依旧是一个问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-26 14:26:27 | 显示全部楼层
本帖最后由 liangbch 于 2009-11-26 14:30 编辑

回520#
fid23 已经全部检查完毕,没有找到解。文件target20为空。

现在开始检查fid24,请mathe 更新任务分配表格
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-26 14:26:38 | 显示全部楼层
操作出了一些问题,耽误了一些进度,目前:
计算人员:winxos
计算文件:fid3
当前文件大小:0
进度:9522
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-27 08:40:37 | 显示全部楼层
昨天不知谁把电源关掉了,害得一晚上没算,目前进度是:
fid26:11160
fid27:12357
fid28:9502
fid29:17572
fid30:14916
target20文件:都是0KB
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-27 09:07:06 | 显示全部楼层
请教mathe:
至少到18棵树(每行4棵),都能得出最多行的明确结论,包括整数解、实数解、复数解。采用的方法和现在计算方法有什么区别?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-27 09:11:24 | 显示全部楼层
计算人员:Frankenstein
开始时间:09.11.22
计算文件:fid4
当前文件大小:0
进度:
计算机1:0~12125
计算机2:15000~18754
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-10-24 08:51 , Processed in 0.085244 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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