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

mathe · 发表于 2008-8-18 14:21:08

即使增加到4G也没有多大意义。n每增加一个，需要磁盘空间估计要增加10倍。现在解方程中的内存泄漏问题找到了，现在上载上来。对于大家产生的数据，可以试着让这个程序求解一下看看。为了保证计算过程是精确的，程序需要链接到gmp库。现在的参数设置就是解决20个点的问题。输入参数是一个文件名，这个文件中每一行是一个问题2中的解，要求每一行中所有字母都在A~T之间,每个字母代表一个点。每4个相邻字母代表一个过四点的"直线"，不同"直线"之间没有空格作为间隔（可能大家需要转化一下自己的格式，或者修改一下process_one_line代码开始输入部分）如果程序没有任何输出，代表无解。不然程序会输出输入行，然后一条wxmaxima命令（如果还存在非线性的表达式),以及所有已经求出的线性表达式。余下部分还需要人工或计算机另外检查。我修改了一下我前面的程序，对于n=20产生了部分解，其中24条直线3222个,25条直线29734个,26条直线9544个,27条直线860个，28条直线2个，程序全部证明无解。同样对于n=17,也产生了部分解，其中18条直线7780个，19条直线63个，20条直线5个，也全部被直接证明无解。

solve4.tar.gz (5.62 KB, 下载次数: 3)

mathe · 发表于 2008-8-18 14:26:35

71#中zgg的方法还是不错的，可以借鉴。我觉得从直线角度出发应该更加好一些。这样基本上就不需要将中间结果保存到文件里面了。

mathe · 发表于 2008-8-19 12:36:45

现在试着修改了程序，让中间结果输出到多个文件，而不是一个文件。看来证明n=16是没有问题的了，只是时间可能稍微有点长（计算n=13是瞬间的，但是现在n=16的情况估计要数小时），而且要产生大量中间数据(数G数据总是需要的）但是n=17可能已经比较困难了（也许我的计算机还能够解决），但是更加大一点的估计不行了（估计磁盘空间不够用了）

fm10.tar.gz (5.71 KB, 下载次数: 1)

mathe · 发表于 2008-8-19 16:02:15

Linux的外部命令sort挺慢的，发现用于调用sort的时间比其他计算时间加起来还要长。

无心人 · 发表于 2008-8-19 17:21:47

当然了还要两次环境切换不如你用STL自己做排序吧

mathe · 发表于 2008-8-19 18:08:30

呵呵，主要担心单个文件太大，无法全部读入内存。那种情况无法用STL来排序的。现在n=16的情况下面将边数不小于16的所有情况计算出来了，总共412种完全不等价的问题2解，见附件：

16.tar.gz (8.29 KB, 下载次数: 1) 用我的程序来过滤，马上得出全部没有合法解。所以n=16情况可以得到最多边数15。而wolfram已经得出不小于15，所以n=16的情况最大边数就是15。

无心人 · 发表于 2008-8-19 18:10:02

呵呵那就不好作了要不你实现文件排序吧

mathe · 发表于 2008-8-21 08:38:05

只要能够实现功能就行，稍微慢一点无所谓。现在在产生n=17时所有总边数不小于17条的结果（16条的不敢产生，估计计算机硬盘空间受不了，wolfram给出n=17时有15条边的结果）。现在运行了一天半了，才计算到程序的第5步，已经在硬盘上产生近50G的临时数据了，而且还没有停下来的迹象。不过估计第5步应该能够通过，但是不知道第6步数据量是增加还是减少，如果继续增加，估计我的机器也受不了了（硬盘空间不够）

mathe · 发表于 2008-8-21 09:58:07

后面我要贴一个英文版的总结，然后等待我们网页能够被游客访问的时候把结果提交到The On-Line Encyclopedia of Integer Sequences

mathe · 发表于 2008-8-21 09:58:38

灌水翻一页

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

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