数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2008-11-8 13:56:00 | 显示全部楼层
什么方法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-8 16:56:28 | 显示全部楼层
呵呵
19的如果能并行
可以考虑分解任务做的
要不你写个程序
我拿我机房50台双核3.0并行下
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-8 19:24:49 | 显示全部楼层
呵呵,暂时先不考虑并行执行。我现在都是半手工的。
方法过几天再介绍。最近比较忙,还同时考虑这个问题,而介绍方法也不是一句两句可以说清楚的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-8 20:34:11 | 显示全部楼层
你估计下20个字母的4字母组的解24组的
在筛除无效的后
还能剩多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-11 18:09:18 | 显示全部楼层
17颗树的最优结果找到了,可以达到16行,所以看来18颗以上弹性还不小:
17trees.GIF
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-11 21:03:48 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-11 22:03:33 | 显示全部楼层
从现在结果来看,估计分析18颗树的情况还是不难的,但是19颗树就很难了。而得出20颗树情况的最优的的可能性很小。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-12 14:15:21 | 显示全部楼层
晕,像将我的程序搬到windows上计算18颗树的情况,结果发现程序慢了至少一个数量级。
不知道是硬盘不同还是操作系统不同的原因(程序会大量访问文件)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-12 14:47:13 | 显示全部楼层
现在介绍一下是如何解决17颗树问题的。
对于一个种树的方案g,我们记N(g)为树的数目,R(g)为其中正好4颗树的行的数目,mD(g)为g中经过的行的数目最小的树所经过的行数目。比如方案g="ABCD ABCE",那么N(g)=5,R(g)=2,mD(g)=1 (树D只一行经过).
这个新方法我从一开始就将目标直接指向了20颗树。由于我们知道20颗树已经存在23行的结果,所以只要让计算机直接搜索24行以上的结果就行了。拿24行作为例子,我们需要搜索集合$R={g|N(g)=20,R(g)=24}$
我们知道对于集合R中每个方案g,$"mD"(g)<=4$(因为如果$mD(g)>=5$,那么$R(g)>="round"({N(g)*mD(g)}/4)=25$.所以如果我们从g中删除一颗经过的行的数目最小的树,得到g',那么$N(g')=19$,$R(g')=R(g)-mD(g)$,$mD(g')>=mD(g)-1$.而最后一个不等式非常重要,它是因为任何其它树和这颗被删除的树最多只有一个公共行。
类似上面过程我们可以知道g'必然在集合$T_19={g|N(g)=19,R(g)+"mD"(g)>=23,R(g)>=20}$中。
同样从$T_19$中去掉经过行的数目最小的一颗树得到的结果必然在集合$T_18={g|N(g)=18,R(g)+"mD"(g)>=19}$中
同样从$T_18$中去掉经过行的数目最小的一颗树得到的结果必然在集合$T_17={g|N(g)=17,R(g)+"mD"(g)>=15}$中
同样从$T_17$中去掉经过行的数目最小的一颗树得到的结果必然在集合$T_16={g|N(g)=16,R(g)+"mD"(g)>=12}$中
同样从$T_16$中去掉经过行的数目最小的一颗树得到的结果必然在集合$T_15={g|N(g)=15,R(g)+"mD"(g)>=10}$中
同样从$T_15$中去掉经过行的数目最小的一颗树得到的结果必然在集合$T_14={g|N(g)=14}$中.
而我的新思路就是从$T_14$出发,逐步构造$T_15$,...,$T_20$.
当然计算机每次都是按照第二个问题构造结果,对于每步构造的结果,利用我的筛选程序将不符合平面约束条件的部分解筛选掉(当然不能完全筛选掉),然后再进行下一步的计算。
现在$T_16$已经计算出来了,其对应的问题一数据文件大概在150M左右,由于大部分数据是边数比较少的情况,平面约束过滤掉的也不多。
而计算$T_17$就很难了,有两个问题:
1。总数据量很大,估计可能达到10G左右存储空间,而产生过程每个数据都可能会被重复产生很多次,所以需要不断的去查询以前已经产生的数据进行比较,避免保存重复的数据(不然磁盘空间肯定不够)。
2。现在我的筛选程序虽然比较有效,但是速度非常慢(要不然第一步产生过程中我就会直接使用了)。现在有3个版本,第一个版本速度最快,但是效率不高,大概每秒能够筛选数千个不同过的数据。而第二个程序效率已经挺高的,单每秒只能筛选十几个不通过的数据。而第三个程序效率非常高(大部分情况都能够给出解或报告无解),但是遇上不通过的数据需要花费数秒钟。产生了如此大量的数据光这部分筛选花费的时间可能也受不了了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-11-12 15:38:01 | 显示全部楼层
Linux继承了UNIX的特点
适合做服务器
当然性能好

我想FreeBSD性能更好
我觉得有必要设计一个简单的
可索引的文件数据格式

或者,干脆取前多少字母作文件名
应该能减少查询次数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-6-19 02:53 , Processed in 0.055857 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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