数学研发论坛

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

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

  [复制链接]
发表于 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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-18 14:26:35 | 显示全部楼层
71#中zgg的方法还是不错的,可以借鉴。我觉得从直线角度出发应该更加好一些。这样基本上就不需要将中间结果保存到文件里面了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-19 12:36:45 | 显示全部楼层
现在试着修改了程序,让中间结果输出到多个文件,而不是一个文件。
看来证明n=16是没有问题的了,只是时间可能稍微有点长(计算n=13是瞬间的,但是现在n=16的情况估计要数小时),而且要产生大量中间数据(数G数据总是需要的)
但是n=17可能已经比较困难了(也许我的计算机还能够解决),但是更加大一点的估计不行了(估计磁盘空间不够用了)
fm10.tar.gz (5.71 KB, 下载次数: 1)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-19 16:02:15 | 显示全部楼层
Linux的外部命令sort挺慢的,发现用于调用sort的时间比其他计算时间加起来还要长。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-19 17:21:47 | 显示全部楼层
当然了
还要两次环境切换
不如你用STL自己做排序吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-19 18:08:30 | 显示全部楼层
呵呵,主要担心单个文件太大,无法全部读入内存。那种情况无法用STL来排序的。
现在n=16的情况下面将边数不小于16的所有情况计算出来了,总共412种完全不等价的问题2解,见附件:
16.tar.gz (8.29 KB, 下载次数: 1)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-19 18:10:02 | 显示全部楼层
呵呵
那就不好作了
要不你实现文件排序吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 08:38:05 | 显示全部楼层
只要能够实现功能就行,稍微慢一点无所谓。
现在在产生n=17时所有总边数不小于17条的结果(16条的不敢产生,估计计算机硬盘空间受不了,wolfram给出n=17时有15条边的结果)。现在运行了一天半了,才计算到程序的第5步,已经在硬盘上产生近50G的临时数据了,而且还没有停下来的迹象。不过估计第5步应该能够通过,但是不知道第6步数据量是增加还是减少,如果继续增加,估计我的机器也受不了了(硬盘空间不够)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 09:58:07 | 显示全部楼层
后面我要贴一个英文版的总结,然后等待我们网页能够被游客访问的时候把结果提交到The On-Line Encyclopedia of Integer Sequences
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 09:58:38 | 显示全部楼层
灌水翻一页
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-10-27 09:07 , Processed in 0.065011 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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