来点复杂的吧

无心人

能不能用构造法？？

先取直线1，然后取2，3
依次的画，直到遇到相交
则判断是非法的解

mathe

同样对于常数项所在列就是columnid[0][0]
对于变量v一次项所在的列就是columnid[0][v]或columnid[v][0].

变量_matrix是系数矩阵,每一行是一条方程,表示这些项乘上对应系数后和必须为0.
而变量_valid如果被置成false就表示方程没有符合果树问题的解.

由于计算过程中会出现很多二次项所有系数都是0,为了提高速度,这些项没有必要保留,所以我提供了一个
left_column数组和lc变量,来收集那些对应列至少有一个非0数据的列(列的编号)
只是现在每次更新它们都要完全扫描一次,其实效率不高.

方程求解过程就是通过高斯消元法构造一些所有非0项都是存在某个变量v的方程.
比如如果我们构造出方程
a*v+b*v1*v+c*v2*v+d*v*v=0
由于所有这些变量必须非0(问题几何意义的要求),
我们可以得到线性关系
a+b*v1+c*v2+d*v=0,从而得到一个线性关系而可以消除一些变量.
由此我们需要一下一些变量来保存一些数据
_t表示所有的方程数目
_m表示所有余下的二次方程(在_matrix前_m行)
而_matrix后_t-_m行由来保存那些已经找到的线性关系.
为此我们需要两个辅助信息row_var和row_evar
其中像上面的关系,其中row_var里面就保存了变量v的编号,也就是这一行中,每一项都可以忽略掉一个v从而形成一个线性组合.
而row_evar表示我们得到这个线性关系后,从前_m中消除的变量的编号.
比如我们得到上面的线性关系后,就可以消除变量v1,于是对应的row_evar就是v1,而这时候前_m行中所有用掉的变量v1就需要全部被消除.

而最后函数simplify_result()中判断一些特殊情况,比如余下只有一条二次方程是一个二次型,那么我们可以判断二次型的$\Delta$是否不小于0来判断是否有实数解.如果没有实数解也可以淘汰.

无心人

拓扑变换有否能判定两点必然在一条直线两边的算法么？

mathe

原帖由 无心人 于 2009-2-19 10:35 发表


只看到极端复杂， 呵呵
有否能转化成一个小矩阵，按照矩阵运算处理的思路

比如按18个字母的18 * 14的矩阵
以0, 1表示

7楼的基本就是矩阵元算,几乎是全线性的,不过里面元素不仅仅0,1,而是可能出现有理数,所以我使用了gmp中的有理数来表示

mathe

Windows版本的,带编译后的程序(不过不带测试数据)

无心人

需要GMP的DLL？？

无心人

一个机房一个月大概是150小时
即7500机时
每机时能计算5个
一个月大概是37500个
==================
呵呵，似乎我在短消息里的说错了

mathe

原帖由 无心人 于 2009-2-20 16:17 发表
需要GMP的DLL？？

我静态链接了,不需要DLL

mathe

我现在将一半的输入数据存放在csdn中了:
http://mathe.download.csdn.net/
有兴趣(也有空闲cpu时间)的朋友也可以自己下载下去帮忙运行部分数据.
当然对于大部分情况,输出是空的.

无心人

呵呵

mathe给我的windows程序可能不如我重新编译的好