数学研发论坛

 找回密码
 欢迎注册
查看: 18425|回复: 111

[原创] 果树问题最优解大全

[复制链接]
发表于 2009-12-21 09:06:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
在这个帖子里面,我希望我们能够果树问题20棵树以下所有最优解都整理。而其中每个解可以有多个不同的图形。在链接果树问题讨论2#中给出了14到20棵树的一些候选解,其中包含14棵到19棵树的所有最优解(20棵树23行的所有最优结果现在还没有能力完全遍历,到现在我们还只知道两组解)。
精华

在那里632#,程序norm.exe可以根据两个图的点线关系判断是否同构。633#中solver.exe可以试着根据一个点线关系给出一组经过优化以后的方程组(通常可以直接通过maxima解出这个方程)。634#包含一个Pari/gp程序,可以用来辅助判断数据合法线(比如是否存在5点共线),进行射影变换或作图等

而这个工作量将会比较大,所以请大家共同帮忙来完成。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 09:21:52 | 显示全部楼层
现在以文件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]]
可以看出这个方程有两组解,而且都是复数解(说明这个候选解不是实数范围内的解)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-21 09:32:50 | 显示全部楼层
mathe尝试写个论文吧
等解决了20颗树后再写篇
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 09:45:55 | 显示全部楼层
而如果为了能够让后面的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会给出各点的坐标
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 09:52:00 | 显示全部楼层
还有一个问题是经过射影变换以后,某些点的射影坐标最后一项不再是0或1了,这时可以通过函数normalize_coord来进行归一化,而且上面忘了说明函数show_algebra必须要求其中node_coord是标准化过的,所以我们可以使用show_algebra(edge_matrix,normalize_coord(node_coord))
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 09:53:17 | 显示全部楼层
3# 无心人

我不知道该投到什么地方去。大家有什么好建议?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 10:23:12 | 显示全部楼层
我们现在看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)
同样首先验证解通过计算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 10:27:31 | 显示全部楼层
在GP下显示上面的图的结果如下(可以看出有一个点只有一行通过,有点奇怪,不知道是否程序有错)

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

  1. normalize_coord(node_coord)=
  2. {
  3.     local(nnodes,onc);
  4.     nnodes=get_node_num();
  5.     onc=node_coord;
  6.     for(u=1,nnodes,
  7.         if(node_coord[u,3]!=0,
  8.             onc[u,1]=node_coord[u,1]/node_coord[u,3];
  9.             onc[u,2]=node_coord[u,2]/node_coord[u,3];
  10.             onc[u,3]=node_coord[u,3]/node_coord[u,3];
  11.         );
  12.     );
  13.     onc
  14. }
复制代码
然后我使用了变换矩阵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)]

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 11:00:04 | 显示全部楼层
通过手工化上面第一个图可以发现pari/gp画丢了一条直线DEFS

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-21 11:05:46 | 显示全部楼层
上面问题是由于我错误将edge_num设置成19而不是20,所以最后一条边丢了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-7-21 05:49 , Processed in 0.054241 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表