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

0→∞

什么方法？

无心人

呵呵 19的如果能并行 可以考虑分解任务做的 要不你写个程序 我拿我机房50台双核3.0并行下

mathe

呵呵，暂时先不考虑并行执行。我现在都是半手工的。 方法过几天再介绍。最近比较忙，还同时考虑这个问题，而介绍方法也不是一句两句可以说清楚的

无心人

你估计下20个字母的4字母组的解24组的 在筛除无效的后 还能剩多少？

mathe

17颗树的最优结果找到了，可以达到16行，所以看来18颗以上弹性还不小：

无心人

mathe

从现在结果来看，估计分析18颗树的情况还是不难的，但是19颗树就很难了。而得出20颗树情况的最优的的可能性很小。

mathe

晕，像将我的程序搬到windows上计算18颗树的情况，结果发现程序慢了至少一个数量级。 不知道是硬盘不同还是操作系统不同的原因（程序会大量访问文件）

mathe

现在介绍一下是如何解决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个版本，第一个版本速度最快，但是效率不高，大概每秒能够筛选数千个不同过的数据。而第二个程序效率已经挺高的，单每秒只能筛选十几个不通过的数据。而第三个程序效率非常高（大部分情况都能够给出解或报告无解），但是遇上不通过的数据需要花费数秒钟。产生了如此大量的数据光这部分筛选花费的时间可能也受不了了。

无心人

Linux继承了UNIX的特点 适合做服务器 当然性能好 我想FreeBSD性能更好 我觉得有必要设计一个简单的 可索引的文件数据格式 或者，干脆取前多少字母作文件名 应该能减少查询次数