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

sheng_jianguo · 发表于 2009-11-11 14:57:44

请教mathe，我的想法对不对：按您的程序全部算完并处理完结果后，有两种可能 1.找到20棵树的24行种树法（很容易验证是否正确）。 2.没有找到20棵树的24行种树法，是否能推出不存在20棵树的24行种树法（包括实数点种法）？另：我又找到一台机器（虽然运算较快，但不能24小时计算），开始计算fid29。

数学星空 · 发表于 2009-11-11 15:35:06

呵,若大伙都像您这样积极,踊跃参与合作,那将提前完成... 但是,好像并没有想象中的那么好哟.. 计算的确很费时,我想在一个月内出结果就已经很不错了....

mathe · 发表于 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棵树以下的最优解都同过去的一样（而且还可以轻松的找出最优的复数解和整数解）

sheng_jianguo · 发表于 2009-11-12 10:25:20

请教mathe：为什么中断程序后计算时间(第二个数)明显减少？有问题吗？注：为了比较，中断程序后我将tag文件中的数字1257改为1255。

mathe · 发表于 2009-11-12 11:02:22

处理每行数据的时间是前后两个时间的差值。相差很明显吗？如果有细微的差别，应该比较正常。通常不应该有很大的变化

数学星空 · 发表于 2009-11-12 11:57:29

呵，计算进展缓慢哟，通过三天的时间（每天7小时），才计算到3000行哟。。。。不知道一个月时间能否算完。。顺便问一句：算完后，程序给出什么提示吗？

mathe · 发表于 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行代码对速度的影响。等我第一部分运行完测试一下（很快就要结束了）

mathe · 发表于 2009-11-15 20:23:53

呵，计算进展缓慢哟，通过三天的时间（每天7小时），才计算到3000行哟。。。。不知道一个月时间能否算完。。顺便问一句：算完后，程序给出什么提示吗？数学星空发表于 2009-11-12 11:57

没给提示，不过程序结束，命令行的提示符会出来

mathe · 发表于 2009-11-16 09:12:14

现在做了一下测试，发现删除哪些过滤条件后，程序丝毫没有变慢，反而可能变快一些（不过程序运行时间还是挺不稳定的，所以到底是否便快不好判断）。所以删除了过滤条件重新编译了一下。此外，发现直接用s8m（旧的过滤算法，更慢，但是效率更加高）来过滤也不会导致速度变慢，所以也做了相应的修改。只是修改以后，输出文件target20通常都会是空的。如果产生了一个结果，那么是合法解的可能性会非常大。另外，将程序分别用intel c++编译器和vc编译。第一个版本是intel c++编译器编译的结果

binary.icc.zip (130.98 KB, 下载次数: 2) 如果上面版本不能运行，可以使用下面的版本

binary.zip (77.85 KB, 下载次数: 8)

mathe · 发表于 2009-11-16 09:15:35

我绝对对于已经运行过的数据，就暂时没有必要重复运行了，不过对于后面的数据，可以换新的程序，好像速度可以提高一些（而且搜索范围更大）。不过解压上面程序覆盖原先可执行程序时，最好先备份一下tag和target20文件，我好像不小心覆盖了，所以现在tid1又重新运行了（快结束了，没找到一个解）

账号		自动登录	找回密码
密码			欢迎注册

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