果树问题讨论:这两个问题等价么？

mathe

昨天开始重新整理了一个程序。这个只需要一个可执行程序（也只有一个线程）。
感觉应该比前一个版本快一些。我在Linux下面测试了一下fid7,好像比原先版本应该能够快一倍左右的速度。而且程序还会同时试着搜索一些20棵树23行的结果。
另外一个好处是程序可以统一处理所有16棵树的输入，然后扩展产生20棵树23行的结果，而不像上一个版本只能处理16棵树11行的输入结果
不过这个程序还没有经过足够的测试，所以下面仅仅将原代码附在这里，而没有附带可执行程序。
而且程序的输出结果在标准输出，而不是target20文件
find2.zip (10.44 KB, 下载次数: 3)

2009-11-26 11:09 上传

点击文件名下载附件

另外我现在在用这个程序处理fid7文件做进一步测试，大家可以先跳过这个文件

数学星空

计算人员：数学星空
开始时间：
计算文件:fid2
当前文件大小：0
进度：20000

Frankenstein

计算人员：Frankenstein
开始时间：09.11.22
计算文件:fid4
当前文件大小：0
进度：
计算机1：0~11031
计算机2：15000~16281

sheng_jianguo

昨天开始重新整理了一个程序。这个只需要一个可执行程序（也只有一个线程）。
感觉应该比前一个版本快一些。我在Linux下面测试了一下fid7,好像比原先版本应该能够快一倍左右的速度。而且程序还会同时试着搜索一些20 ...
mathe 发表于 2009-11-26 11:09

想法很好，应仔细分析、总结程序解决问题的每一步骤，尽早发现所有bug。
由于没有找到24行解法可能性非常大，“现代数学三大难题”之一的“20棵树植树问题”被成功破解的难点可能就剩下论证程序的正确性

mathe

现在测试的结果是这个程序速度比我们现在使用的还慢（也许是因为为了找更多的23行解而导致搜索空间增加），所以就没有必要继续测试了。
而现在版本的程序的可靠性已经比较高了，至少现在我们已经知道的一些特殊解（比如已经知道的17棵树16行的结果，18棵树18行的结果，20棵树23行的结果）都能够成功找到。
至于完全解决20棵树问题，还需要一个使用有理数而不是有限域上数的版本才能够完全确信。现在的方法只是可以带给我们极大的信心最优解为我们所找到的。
根据我过去的经验，如果直接使用gmp中的有理数库替换程序s8m.cpp中的有限域中的数，程序速度估计要慢10倍左右，这个对于我们现在的计算量是不可以忍受的，所以我没有去尝试。
不过考虑到实际上参与运算的有理数通常分子分母都不会太大，而且程序如果设计的好，可以只使用整数而不是分数。所以如果设计良好，可以设计一个整数版本的s8m.cpp(只使用普通32比特的整数），但是要添加一个计算溢出判断（如果计算溢出，抛出异常，中断当前的过滤，认为这个解可能是潜在的合法解即可）。估计这样处理以后的程序比现在版本不会慢多少，这个应该是比较可行的方案。
不过还有两个问题:
i)让所有解方程过程只使用整数而不是有理数（或有限域中的数），我们需要避免所有除法运算，为此代码要复杂很多，我们需要花费不少时间修改这一部分代码以及测试
ii)对所有运算需要添加溢出判断和异常处理，这一步要相对容易很多。但是如何高效实现依旧是一个问题

liangbch

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

现在开始检查fid24,请mathe 更新任务分配表格

winxos

操作出了一些问题，耽误了一些进度，目前：
计算人员：winxos
计算文件:fid3
当前文件大小：0
进度：9522

sheng_jianguo

昨天不知谁把电源关掉了，害得一晚上没算，目前进度是:
fid26：11160
fid27：12357
fid28：9502
fid29：17572
fid30：14916
target20文件：都是0KB

sheng_jianguo

请教mathe：
至少到18棵树（每行4棵），都能得出最多行的明确结论，包括整数解、实数解、复数解。采用的方法和现在计算方法有什么区别？

Frankenstein

计算人员：Frankenstein
开始时间：09.11.22
计算文件:fid4
当前文件大小：0
进度：
计算机1：0~12125
计算机2：15000~18754