mathe

现在我提供一个程序，这个程序可以将任何一个问题二（包括问题一）的结果（要求不超过20棵树）转化为一种标准化表示，也就是说，如果两个方案等价，虽然由于字母排序不同看起来不同，它们的输出会相同。
此外除了输出标准化结果以外，另外输出一行字母对应关系来表示点的变换过程。
比如对于过去比较早产生的程序的标准化输入和现在的字母顺序会相反
例子:
ABCPAHIQAJKRBHLRBJMQCLNQCMORDEIKDHMNDOPQEJLOENPRFGQRFHKOFILPGIJNGKMP
CFHLEIJLCGJMDHKMABLMACENDGINBCDOEFKOHJNOADFPBEGPBFIQAGKQAHIRBJKRCPQR
PMKGNJIGPLIFOKHFRQGFRPNEOLJEQPODNMHDKIEDROMCQNLCQMJBRLHBRKJAQIHAPCBA
其中第一行是输入，第二行是标准化输出，第三行是每个字母在原图像中的字母（可以看到这里正好是第一行的逆序）
norm.zip (11.63 KB)

下载次数: 9

2009-12-19 11:45

mathe

下面这个是求解程序。
在标准输入中输入一个可能解，如果程序求解成功或无法判断是否无解，会输出一组方程，输出的方程可以直接用maxima求解（当然有可能太复杂而maxima也无法求解，大家也可以使用其他更好的数学软件对输出的方程组进行处理）
solver.zip (34.02 KB)

下载次数: 12

2009-12-19 16:59

mathe

这里这个附件是一个Pari/gp程序，可以对一个数据进行射影变换。
只是Pari/gp输入输出我不会做，需要通过修改前面几个函数达到。
其中假设输入数据中有一个参数，参数满足方程get_mod_poly().
get_float_t()指定一个浮点参数（可以用于画图）。
get_node_info()给定每个点的坐标，采用射影坐标（正常点为(x,y,1),无穷远点可为(1,k,0)，k为这个方向的斜率）
其中函数verify_input()用于确认输入是正确的（确保用户输入过程没有错误）
而verify_inputs()函数除了验证所有的4点共线成立外，还要确保没有5点共线。如果这个函数也通过，说明前面用solver解出的解是正确的候选解。
show_algebra函数可以用来以图像方式显示

mathe

现在在2#中给出了14到18棵树的很多结果（包含所有最优结果，18棵还不全，19~20棵树以后再继续添加）。以后大家有空还可以将14棵到20棵的所有最优结果整理一下，将图画出来。而且最好能够通过射影变换，将图变换得更加漂亮。

hujunhua

这两个问题不等价。问题一（即果树问题）属于实射影几何，问题二属于有限射影几何。

实射影几何与有限射影几何一个本质区别是：前者遵守Desargues公理，后者不遵守。这个区别导致这样一个结果：在有限射影几何中的共直线的3点，在实射影几何中不一定找得到模型。

hujunhua

比如，最小的有限射影平面包含7个点和7条直线。每点恰好结着3条直线，每条直线恰好穿过3个点。

如果你要尽力在欧氏平面（可视为实射影平面的有限部分）上画出其模型，就会得到一个类似这样的构图：一个三角形以及它的3条中线，3个中点和重心。
7个点有了：3个顶点，3个中点，再算上重心
6条直线：3条边，3条中线。还差一条直线在哪里呢，你清理一下哪些点还不够3条直线就会发现，剩下的那条直线是经过3个中点的！

在实射影平面上，三角形的3个中点当然不可能共线。很直观吧，但是真要证明起来还有点麻烦呢，不信你试试看。

mathe

google了一下,有限射影平面是指有限域内的射影平面,所以同问题二也不等价.而选择不同的有限域,得到的有限射影平面也不等价.