数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

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

[复制链接]
 楼主| 发表于 2009-12-26 11:07:53 | 显示全部楼层
现在我那个gp的程序非常有用,有了这个程序的分析,我们可以对每个图找出最漂亮的方案。
在这里,我们可以用下面三个准则来评价是否漂亮:
i)对称性,这个是优先考虑的准则。
ii)统计独立性(各个方向方差相等,垂直的两个方向分布不相关)
iii)清晰度,用两点间最小距离和最大距离的比值来衡量,越大越清晰。
其中,前面两个都非常容易计算,而最后一个现在没有好的办法,在保证前面两个准则下,可以通过随机产生多个图来选择最优的方案。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-26 11:13:42 | 显示全部楼层
其中关于对称性,如果只找到一个对称轴,如前面处理就可以。
如果找到三个(或以上)对称轴交于一点,而对称轴的极点共线,那么如果k个对称轴共点(gp程序应该可以找到k+1个),那么可以将对图形转化成类型正k边形的形状(旋转${2pi}/k$不变)
如果总是只有两条对称轴交于一点,应该可以找到一些“对称轴三角形”,其中三条对称轴的极点为三角形顶点,三条对称轴为三边。可以将其中两条投影成横坐标和纵坐标,另外一条投影成无穷远直线,得到一个横坐标纵坐标都是对称轴的图。由于无穷远直线有3个不同选择,有3个不同的方案。
当然对于所有k点共线的对称轴,如果k为偶数,总是可以通过后面的“对称轴三角形”来处理。
而所有情况,都可以任意选择一条对称轴,采用一条对称轴的方案得出多种次优(只有一条轴)的方案。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-26 11:16:15 | 显示全部楼层
本帖最后由 数学星空 于 2009-12-26 11:17 编辑

嗯,我昨晚按照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值)???
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-26 11:20:09 | 显示全部楼层
74#各个命令其实可以封装成一个函数。此外得到所有对称轴的信息需要判断一下对称轴的数目。
主要是数据输入,就是修改前面6个函数比较麻烦(包含输入点的数目,边的数目,非有理参数(如果存在)的方程和浮点值,点的齐次坐标,点线关系)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-26 11:22:14 | 显示全部楼层
一种比较可行的方法是直接让mathematica产生gp文件的前6个函数(甚至整个gp文件)。
当然也可以用mathematica或c将所有gp函数重写。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-26 11:22:56 | 显示全部楼层
嗯,我昨晚按照mathe提供的程序及方法也试过了..
但是,不知道怎么载入数据
比如: 对于 14棵树10行有一个结果              
                   BEGH  BCFI  ACEJ  DFHJ   ABDK  CDGL  EIKL  AFGM   AHIN   JKMN   ...
数学星空 发表于 2009-12-26 11:16

你这里坐标信息还不全,除了方程的解,还有一些预定义的点的坐标
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-26 11:30:04 | 显示全部楼层
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程序中吗?
若能直接读取就好了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-26 11:34:37 | 显示全部楼层
呵呵,现在没有提供这样的程序,所以可以自己写程序转化
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-12-26 11:41:47 | 显示全部楼层
关于统计独立性或方向无关性,我们可以查看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可以将图像变得同方向无关

评分

参与人数 1鲜花 +5 收起 理由
wayne + 5 太有创造性了 我发现我越来越崇拜你了

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-26 12:23:30 | 显示全部楼层
本帖最后由 wayne 于 2009-12-26 12:24 编辑
比较好的想法,若能将坐标转化邻接矩阵,就有统一的格式,
例如:BEGH  BCFI  ACEJ  DFHJ   ABDK  CDGL  EIKL  AFGM   AHIN   JKMN  (1)
显然有每组(BEGH),(BCFI),..., 中的任两个值可定义为1,其余的定义为0 ,即(B ...
数学星空 发表于 2009-12-26 10:38

邻接矩阵确实不能给出完整的信息。
但Mathematica只需要邻接矩阵就可以画出图来,
我怀疑Mathematica内部的自动美化的功能足可以不全失去的图信息

呵呵,当然了,我们不能投机取巧,应该先把理论吃透了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-12-13 15:32 , Processed in 0.085394 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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