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

liangbch

回290楼，我没有仔细看你的代码，你说的解方程是指求解多元连立线性方程组吗？如果是，你用的是什么算法，或许可以改用一个高效的算法来提高速度。

gxqcn

没有细究 GMP 是如何处理分数的，

但分数的通分和约分是两个矛盾体，
什么时候该通分或该约分是很难判断的，
甚至分数四则运算的先后次序都可造成难易不同，
这在小学算术中都有体现。

尤其是约分，涉及到公约数的计算，比较麻烦。
所以，若可以用大整数则用大整数，自己去模拟分数运算，
并控制好约分化简的时机。

以上建议仅供参考。

mathe

其实我觉得我的代码里面的瓶颈可能不仅仅在使用了有理数，而是在进行解方程过程中，无论矩阵的行还是列的数目变化都很厉害，而我的算法对于这个没有很好的优化。当然如果能够只使用整数，肯定对效率有帮组，不过代码就更加难写了,对现在的代码我已经觉得头疼了。实际上我觉得还可以试验只使用普通的整数类型而不是大整数（只是计算可能会发生溢出，那就会出错了）
另外昨天做了一个实验，从一个包含了大概14万个17颗树14行的解（文件大概80M)出发构造出一批18颗树17行和18行的解，共产生了2G多的文件（都还是问题二的解）。然后从中随机抽取了一个100多M的文件，分析里面的数据，结果发现全部不是合法的解。也就是说明到了18颗树时，实际上构造出来的问题二的解是正确的问题一的解的概率已经非常之低了。所以这个时候，快速判断一个问题二的解是否问题一的解更加关键了，估计如果能够解决这个问题，那么产生的T18不会太大，从而我们可以继续产生T19和T20而彻底解决20颗树问题。

无心人

能否转化成一个线性代数问题？

mathe

如果能这个问题就不会这么难了。
不过昨天想到也许可以用迪沙格定理过滤掉一些非法解。这个在过去树的数目比较少的时候作用不大，但是随着现在树的数目的增加，应该会有些作用，特别18颗树的时候非法解比例如此之高，说不定可以解决这里的问题

无心人

这个字母排列能否转化成一个图？
这个图能否进行拓扑变换
比如，无论如何变换，必定存在非预期的交叉
则解无效

mathe

试验了一下，在17颗树和18颗树时，采用迪沙格定理过滤效果甚微，意义不大（才过滤掉万分之一到千分之一）。
同样我还试验了一下采用16颗树中的合法解去匹配17颗树中去掉任何一颗经过行的数目最小的树时候的情况（如果出现不匹配说明不是合法解），同样效果不是很明显（过滤掉数据小于10%)，而速度已经不快了（由于内存访问过于频繁）。

无心人

假如
我说假如
使用浮点运算，肯定能得到一些近似解
再筛选如何？
会减少多少比例？

mathe

浮点运算很难，主要是0的判断容易出问题。
我现在弄了一个版本，使用普通long long类型的整数，速度可以提高8倍左右，不过好像现在看来出来的结果有些问题。有可能程序运行过程中遇上异常退出。

无心人

你设最小限制
比如小于10^(-7)算0