果树问题最优解大全

mathe

现在我那个gp的程序非常有用，有了这个程序的分析，我们可以对每个图找出最漂亮的方案。 在这里，我们可以用下面三个准则来评价是否漂亮: i)对称性，这个是优先考虑的准则。 ii)统计独立性（各个方向方差相等，垂直的两个方向分布不相关） iii)清晰度，用两点间最小距离和最大距离的比值来衡量，越大越清晰。 其中，前面两个都非常容易计算，而最后一个现在没有好的办法，在保证前面两个准则下，可以通过随机产生多个图来选择最优的方案。

mathe

其中关于对称性，如果只找到一个对称轴，如前面处理就可以。 如果找到三个（或以上）对称轴交于一点，而对称轴的极点共线，那么如果k个对称轴共点（gp程序应该可以找到k+1个），那么可以将对图形转化成类型正k边形的形状（旋转${2pi}/k$不变） 如果总是只有两条对称轴交于一点，应该可以找到一些“对称轴三角形”，其中三条对称轴的极点为三角形顶点，三条对称轴为三边。可以将其中两条投影成横坐标和纵坐标，另外一条投影成无穷远直线，得到一个横坐标纵坐标都是对称轴的图。由于无穷远直线有3个不同选择，有3个不同的方案。 当然对于所有k点共线的对称轴，如果k为偶数，总是可以通过后面的“对称轴三角形”来处理。 而所有情况，都可以任意选择一条对称轴，采用一条对称轴的方案得出多种次优（只有一条轴）的方案。

数学星空

嗯,我昨晚按照mathe提供的程序及方法也试过了.. 但是,不知道怎么载入数据 比如: 对于 14棵树10行有一个结果 BEGH BCFI ACEJ DFHJ ABDK CDGL EIKL AFGM AHIN JKMN (1) 算出来的有理解为 M_Y = 2/5, N_Y = 2/3, N_X = 2/3, J_X = 1/2, L_X = -2, M_X = 3/5, L_Y = 2, D_Y = -1, G_Y = -1, D_X = 1, H_Y = -2, K_Y = 2, I_Y = 2, K_X = 1 (2) 还有,不知有没有更快捷的输入方式,因为按照74#的方法输入,还是太麻烦,并且也不知道能否修改,复制74#的每个步骤并修改其中的参数( x值)???

mathe

74#各个命令其实可以封装成一个函数。此外得到所有对称轴的信息需要判断一下对称轴的数目。 主要是数据输入，就是修改前面6个函数比较麻烦（包含输入点的数目，边的数目，非有理参数（如果存在）的方程和浮点值，点的齐次坐标，点线关系）。

mathe

一种比较可行的方法是直接让mathematica产生gp文件的前6个函数（甚至整个gp文件）。 当然也可以用mathematica或c将所有gp函数重写。

mathe

嗯,我昨晚按照mathe提供的程序及方法也试过了.. 但是,不知道怎么载入数据 比如: 对于 14棵树10行有一个结果 BEGH BCFI ACEJ DFHJ ABDK CDGL EIKL AFGM AHIN JKMN ... 数学星空 发表于 2009-12-26 11:16

你这里坐标信息还不全，除了方程的解，还有一些预定义的点的坐标

数学星空

BEGHBCFIACEJDFHJABDKCDGLEIKLAFGMAHINJKMN M_Y = 2/5, N_Y = 2/3, N_X = 2/3, J_X = 1/2, L_X = -2, M_X = 3/5, L_Y = 2, D_Y = -1, G_Y = -1, D_X = 1, H_Y = -2, K_Y = 2, I_Y = 2, K_X = 1 A_x=1 A_y=0 B=(0,1,0) C_x=0 C_y=0 E=(1,0,0) F_x=0 F_y=1 G=(1,G_y,0) H=(1,H_y,0) I_x=0 J_y=0 例如:上面的数据就是完整的信息了... 但是,必须依次输入到gp程序中吗? 若能直接读取就好了

mathe

呵呵，现在没有提供这样的程序，所以可以自己写程序转化

mathe

关于统计独立性或方向无关性，我们可以查看64#或70#中中心对称的图，可以看到图像总体趋势是从左下到右上方向比较长，而左上到右下的方向比较短。如果能够将左上到右下方向拉长，图像会更加好看一些。这个可以通过统计各个方向方差来处理。 假设所有点笛卡儿坐标为$(x_i,y_i)$，计算$\bar{x}={sum_ix_i}/n,\bar{y}={sum_iy_i}/n$ $Var(x)={sum_i(x_i-\bar{x})^2}/n,Var(y)={sum_i(y_i-\bar{y})^2}/n,Col(x,y)={sum_i(y_i-\bar{y})(x_i-\bar{x})}/n$ 于是存在可逆矩阵P使得$P'[(Var(x),Col(x","y)),(Col(x","y),Var(y))]P$变成单位阵，那么线性变换P可以将图像变得同方向无关

wayne

比较好的想法,若能将坐标转化邻接矩阵,就有统一的格式, 例如:BEGH BCFI ACEJ DFHJ ABDK CDGL EIKL AFGM AHIN JKMN (1) 显然有每组(BEGH),(BCFI),..., 中的任两个值可定义为1,其余的定义为0 ,即(B ... 数学星空 发表于 2009-12-26 10:38

邻接矩阵确实不能给出完整的信息。 但Mathematica只需要邻接矩阵就可以画出图来， 我怀疑Mathematica内部的自动美化的功能足可以不全失去的图信息 呵呵，当然了，我们不能投机取巧，应该先把理论吃透了