果树问题最优解大全
在这个帖子里面，我希望我们能够果树问题20棵树以下所有最优解都整理。而其中每个解可以有多个不同的图形。在链接果树问题讨论2#中给出了14到20棵树的一些候选解，其中包含14棵到19棵树的所有最优解（20棵树23行的所有最优结果现在还没有能力完全遍历，到现在我们还只知道两组解）。众人智慧攻克难题在那里632#,程序norm.exe可以根据两个图的点线关系判断是否同构。633#中solver.exe可以试着根据一个点线关系给出一组经过优化以后的方程组（通常可以直接通过maxima解出这个方程）。634#包含一个Pari/gp程序，可以用来辅助判断数据合法性（比如是否存在5点共线），进行射影变换或作图等
而这个工作量将会比较大，所以请大家共同帮忙来完成。
https://blog.emath.ac.cn/shared/
站内链接:
果树问题讨论
20棵树最优解计算
果树问题最优解大全
果树种植最优解精美图形作法探讨
植树问题王兴君解
植树问题蔡上人解 现在以文件s19from11为例子（部分19棵树的解）。里面包含两个候选解。
在命令行输入
C:>solver.exe<s19from11 >s19from11.out 2>s19from11.err
执行完毕以后，s19from11.err里面还是这两行（如果某一行从这个文件里面消失，代表那组必定无解）
而s19from11.out里面包含了一些maxima命令，其中两个solve()里面内容代表对应的方程。而print里面内容分别输出对应的问题和部分事先指定的坐标，比如第一个：
print(ADHLCGKLBEGMAFIMBDJNDGIOCEJOBFLOCFHPDKMPAENPAGJQBHKQCINQEHIRFJKRLMNROPQRABCSDEFS);
solve([+1-1*R_Y+1/3*R_Y*R_Y,+2-1*R_Y+1*S_Y,+1*C_X-2/3*R_Y,-3+1*R_X+1*R_Y,+3/2+1*O_Y-1*R_Y,-1+1*Q_X+1/3*R_Y,-2+1*S_X,+1*P_Y-1/2*R_Y,+1*N_Y-2/3*R_Y,-2+1*N_X+2/3*R_Y,+1+1*M_Y-1*R_Y,-3+1*H_Y+1*R_Y,+3+1*F_Y-2*R_Y,+2+1*I_Y-1*R_Y,-1+1*M_X,-1+1*J_Y,+1+1*E_Y-1*R_Y,-2+1*J_X+2/3*R_Y,-1+1*Q_Y,-1+1*P_X,-2+1*B_X+2/3*R_Y,+1+1*B_Y-1*R_Y,-2+1*F_X,-2+1*E_X],);
print("A_x=0 A_y=1 C_y=0 D=(0,1,0) G=(1,0,0) H_x=0 I=(1,I_y,0) K_x=1 K_y=0 L_x=0 L_y=0 O=(1,O_y,0) ");
第一行输出这个候选解，第二行是方程，用于求大部分点的坐标（其中大部分方程是线性的，比如最后一个-2+1*E_X就代表E_X=2,也就是E的横坐标为2),
而最后一行print代表一些事先指定的坐标值。其中有些点如I=(1,I_y,0)表示这是一个无穷远点。而I_y需要由方程组来确定。
而对于这组方程，输入maxima得到如下结果：
(%o1) [,]
可以看出这个方程有两组解，而且都是复数解（说明这个候选解不是实数范围内的解） mathe尝试写个论文吧
等解决了20颗树后再写篇 而如果为了能够让后面的Pari/gp程序继续处理，由于gp里面不能直接表示精确的代数数，我们采用模多项式来表示，比如这里主要是代数数sqrt(3)%i。由于它是方程$t^2+3=0$的解，我们可以将所有的sqrt(3)%i用t代替，得到所有点坐标表示如下:
$t^2+3=0$
A(0,1),B(t/3+1,(1-t)/2),C(1-t/3,0),D(0,1,0),E(2,(1-t)/2),F(2,-t),G(1,0,0),H(0,(3+t)/2),I(1,-(1+t)/2,0),J(1+t/3,1),K(1,0),L(0,0),M(1,(1-t)/2),N(1+t/3,1-t/3),O(1,-t/2,0) P(1,(3-t)/4) Q((3+t)/6,1) R((3+t)/2,(3-t)/2) S(2,-(1+t)/2)
然后我们需要修改ocd.gp中前6个函数同这个结果匹配。其中这里get_float_t()函数由于没有实数解，所以没有意义，不用管它。而get_nodes_info里面按字母顺序给出所有点的射影坐标，如果不是无穷远点，最后一维输入1就可以了。
然后把ocd.gp放在c:盘根目录，进入pari/gp后，输入命令
\r ocd
然后按例子find_trans()中的样子，输入命令
nnodes=get_node_num();
nedges=get_edge_num();
edge_matrix=get_edge_matrix(nedges,get_edge_string());
oldnc=get_nodes_info();
node_coord=Mod(oldnc,get_mod_poly());
接下去，可以输入命令
verify_input(nnodes,nedges,edge_matrix,node_coord)
确认我们的输入没有问题。如果返回结果为1表示没有问题，如果是0，表示我们某处输入出错。
然后输入
verify_inputs()
如果没有报错，说明这是一个合法的解，不然，应该存在5点共线，不是合法的解。
比如这里，没有报错，说明这是一个合法的复数解。
而如果这时是实数解，只要对应的get_float_t()函数设置了对应的浮点值，那么就可以直接使用函数
show_algebra(edge_matrix, node_coord)来显示图。
而同样，我们还可以任意使用一个3*3可逆矩阵对图像进行射影变换，比如我们输入
M=那么M是个可逆矩阵，然后输入
node_coord=node_coord*M;
那么就可以进行射影变换，然后再调用show_algebra(edge_matrix,node_coord)来显示对应的图。
同样直接输入node_coord会给出各点的坐标 还有一个问题是经过射影变换以后，某些点的射影坐标最后一项不再是0或1了，这时可以通过函数normalize_coord来进行归一化，而且上面忘了说明函数show_algebra必须要求其中node_coord是标准化过的，所以我们可以使用show_algebra(edge_matrix,normalize_coord(node_coord)) 3# 无心人
我不知道该投到什么地方去。大家有什么好建议？ 我们现在看s19from11中第二个问题，对应maxima解为
[,]
这是一组实数解，但是不是有理数解。其中我们可以使用参数$t=+-sqrt(5)$,既$t^2-5=0$
解为
A(0,1)
B((1-t)/2,1)
C(1,0,0)
D(0,1,0)
E(-(1+t)/2,(3+t)/2)
F(-(1+t)/2,3+t)
G(1,0)
H(0,(3+t)/2)
I(0,0)
J(1,-2-t,0)
K(-1,0)
L(1,-(3+t)/2,0)
M(1,-1-t)
N(-1,3+t)
O(1,-(1+t)/2)
P(-1,(3+t)/2)
Q(-1/t,(5+t)/5)
R(-t,3+t)
S(-(1+t)/2,1)
同样首先验证解通过计算。 在GP下显示上面的图的结果如下（可以看出有一个点只有一行通过，有点奇怪，不知道是否程序有错）
在进行射影变换后，我发现使用normalize_coord进行归一化得到结果不对，主要是混合使用了数值1和多项式。可以将它改为
normalize_coord(node_coord)=
{
local(nnodes,onc);
nnodes=get_node_num();
onc=node_coord;
for(u=1,nnodes,
if(node_coord!=0,
onc=node_coord/node_coord;
onc=node_coord/node_coord;
onc=node_coord/node_coord;
);
);
onc
}
然后我使用了变换矩阵M=变换后没有无穷远点（使用matdet(M)计算矩阵行列式确认矩阵可逆）
变换后图如下
对应坐标为:
通过手工化上面第一个图可以发现pari/gp画丢了一条直线DEFS 上面问题是由于我错误将edge_num设置成19而不是20，所以最后一条边丢了