果树问题最优解大全

mathe

在这个帖子里面，我希望我们能够果树问题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棵树最优解计算
果树问题最优解大全
果树种植最优解精美图形作法探讨
植树问题王兴君解
植树问题蔡上人解

mathe

现在以文件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],[R_Y,S_Y,C_X,R_X,O_Y,Q_X,S_X,P_Y,N_Y,N_X,M_Y,H_Y,F_Y,I_Y,M_X,J_Y,E_Y,J_X,Q_Y,P_X,B_X,B_Y,F_X,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) [[R_Y=-(sqrt(3)*%i-3)/2,S_Y=-(sqrt(3)*%i+1)/2,C_X=-(sqrt(3)*%i-3)/3,R_X=(sqrt(3)*%i+3)/2,O_Y=-(sqrt(3)*%i)/2,Q_X=(sqrt(3)*%i+3)/6,S_X=2,P_Y=-(sqrt(3)*%i-3)/4,N_Y=-(sqrt(3)*%i-3)/3,N_X=(sqrt(3)*%i+3)/3,M_Y=-(sqrt(3)*%i-1)/2,H_Y=(sqrt(3)*%i+3)/2,F_Y=-sqrt(3)*%i,I_Y=-(sqrt(3)*%i+1)/2,M_X=1,J_Y=1,E_Y=-(sqrt(3)*%i-1)/2,J_X=(sqrt(3)*%i+3)/3,Q_Y=1,P_X=1,B_X=(sqrt(3)*%i+3)/3,B_Y=-(sqrt(3)*%i-1)/2,F_X=2,E_X=2],[R_Y=(sqrt(3)*%i+3)/2,S_Y=(sqrt(3)*%i-1)/2,C_X=(sqrt(3)*%i+3)/3,R_X=-(sqrt(3)*%i-3)/2,O_Y=(sqrt(3)*%i)/2,Q_X=-(sqrt(3)*%i-3)/6,S_X=2,P_Y=(sqrt(3)*%i+3)/4,N_Y=(sqrt(3)*%i+3)/3,N_X=-(sqrt(3)*%i-3)/3,M_Y=(sqrt(3)*%i+1)/2,H_Y=-(sqrt(3)*%i-3)/2,F_Y=sqrt(3)*%i,I_Y=(sqrt(3)*%i-1)/2,M_X=1,J_Y=1,E_Y=(sqrt(3)*%i+1)/2,J_X=-(sqrt(3)*%i-3)/3,Q_Y=1,P_X=1,B_X=-(sqrt(3)*%i-3)/3,B_Y=(sqrt(3)*%i+1)/2,F_X=2,E_X=2]]
可以看出这个方程有两组解，而且都是复数解（说明这个候选解不是实数范围内的解）

无心人

mathe尝试写个论文吧
等解决了20颗树后再写篇

mathe

而如果为了能够让后面的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=[1,0,0;1,1,0;1,1,1]那么M是个可逆矩阵，然后输入
node_coord=node_coord*M;
那么就可以进行射影变换，然后再调用show_algebra(edge_matrix,node_coord)来显示对应的图。
同样直接输入node_coord会给出各点的坐标

mathe

还有一个问题是经过射影变换以后，某些点的射影坐标最后一项不再是0或1了，这时可以通过函数normalize_coord来进行归一化，而且上面忘了说明函数show_algebra必须要求其中node_coord是标准化过的，所以我们可以使用show_algebra(edge_matrix,normalize_coord(node_coord))

mathe

3# 无心人

我不知道该投到什么地方去。大家有什么好建议？

mathe

我们现在看s19from11中第二个问题，对应maxima解为
[[S_X=-(sqrt(5)+1)/2,Q_Y=(sqrt(5)+5)/5,B_X=-(sqrt(5)-1)/2,R_X=-sqrt(5),O_Y=-(sqrt(5)+1)/2,J_Y=-sqrt(5)-2,M_Y=-sqrt(5)-1,R_Y=sqrt(5)+3,P_X=-1,M_X=1,P_Y=(sqrt(5)+3)/2,Q_X=-1/sqrt(5),E_Y=(sqrt(5)+3)/2,N_X=-1,O_X=1,L_Y=-(sqrt(5)+3)/2,F_Y=sqrt(5)+3,N_Y=sqrt(5)+3,K_X=-1,H_Y=(sqrt(5)+3)/2,B_Y=1,S_Y=1,E_X=-(sqrt(5)+1)/2,F_X=-(sqrt(5)+1)/2],[S_X=(sqrt(5)-1)/2,Q_Y=-(sqrt(5)-5)/5,B_X=(sqrt(5)+1)/2,R_X=sqrt(5),O_Y=(sqrt(5)-1)/2,J_Y=sqrt(5)-2,M_Y=sqrt(5)-1,R_Y=3-sqrt(5),P_X=-1,M_X=1,P_Y=-(sqrt(5)-3)/2,Q_X=1/sqrt(5),E_Y=-(sqrt(5)-3)/2,N_X=-1,O_X=1,L_Y=(sqrt(5)-3)/2,F_Y=3-sqrt(5),N_Y=3-sqrt(5),K_X=-1,H_Y=-(sqrt(5)-3)/2,B_Y=1,S_Y=1,E_X=(sqrt(5)-1)/2,F_X=(sqrt(5)-1)/2]]
这是一组实数解，但是不是有理数解。其中我们可以使用参数$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)
同样首先验证解通过计算。

mathe

在GP下显示上面的图的结果如下（可以看出有一个点只有一行通过，有点奇怪，不知道是否程序有错）

在进行射影变换后，我发现使用normalize_coord进行归一化得到结果不对，主要是混合使用了数值1和多项式。可以将它改为

1. 
   
2. normalize_coord(node_coord)=
   
3. {
   
4.     local(nnodes,onc);
   
5.     nnodes=get_node_num();
   
6.     onc=node_coord;
   
7.     for(u=1,nnodes,
   
8.         if(node_coord[u,3]!=0,
   
9.             onc[u,1]=node_coord[u,1]/node_coord[u,3];
   
10.             onc[u,2]=node_coord[u,2]/node_coord[u,3];
    
11.             onc[u,3]=node_coord[u,3]/node_coord[u,3];
    
12.         );
    
13.     );
    
14.     onc
    
15. }
    

复制代码

然后我使用了变换矩阵M=[1,0,-2;1,2,3;2,-1,1]变换后没有无穷远点（使用matdet(M)计算矩阵行列式确认矩阵可逆）
变换后图如下

对应坐标为:
[Mod(3/4, t^2 - 5) Mod(1/4, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-5/4*t + 13/4, t^2 - 5) Mod(-1/4*t + 3/4, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-1/2, t^2 - 5) 0 Mod(1, t^2 - 5)]

[Mod(1/3, t^2 - 5) Mod(2/3, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-15/22*t + 39/22, t^2 - 5) Mod(3/22*t + 1/22, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-25/82*t + 79/82, t^2 - 5) Mod(2/41*t + 15/41, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-3, t^2 - 5) Mod(1, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-5/38*t + 31/38, t^2 - 5) Mod(5/38*t + 7/38, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(2, t^2 - 5) Mod(-1, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(5/19*t - 7/19, t^2 - 5) Mod(4/19*t + 2/19, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(1/3, t^2 - 5) Mod(-1/3, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(5/62*t - 1/62, t^2 - 5) Mod(2/31*t + 12/31, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-10/29*t + 23/29, t^2 - 5) Mod(1/29*t + 18/29, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(1/3, t^2 - 5) Mod(1/11*t + 10/33, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-t + 2, t^2 - 5) Mod(1/10*t + 1/2, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(1/3, t^2 - 5) Mod(1/10*t + 1/6, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-3/11*t + 12/11, t^2 - 5) Mod(3/55*t + 2/11, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(t - 2, t^2 - 5) Mod(1/5*t, t^2 - 5) Mod(1, t^2 - 5)]

[Mod(-1/4*t + 3/4, t^2 - 5) Mod(-1/20*t + 1/4, t^2 - 5) Mod(1, t^2 - 5)]

mathe

通过手工化上面第一个图可以发现pari/gp画丢了一条直线DEFS

mathe

上面问题是由于我错误将edge_num设置成19而不是20，所以最后一条边丢了