连接n*n的点阵，要求两点间的连线长度尽可能小
用$(n^2-1)$条线段将$(1,1)$到$(n,n)$范围内的整点连起来，形成一棵生成树。看似简单，实则复杂有趣。要求任意两点在生成树上的距离之和$f(n)$最小。
（即$f(n)=\sum_{1<=i<j<=n^2}d(i,j)$，其中$d(i,j)$表示点$i$和点$j$在生成树上的距离）
为了简单起见，我们要求线段的长度均为$1$，并且平行于坐标轴。
下面是$2$个例子：
例$1$：当$n=2$时，连接方案如下：
距离表：
距离之和$f(2)=1+3+2+2+1+1=10$
例$2$：当$n=3$时，连接方案如下：
距离表：
距离之和$f(3)=1+2+3+2+...+1+2+1=84$ 这个问题比较有意思。
对于$n=3$，考察纳粹标志“卐”，其距离和$f(3)=88>84$。 先随机一个生成树，然后换一条边找增广，直到找不到增广，可以么？ 就是N条横杠加中间一竖 3#:
恐怕不行。这样只能找到一个局部最优解。
要找到全局最优解，可能需要多次随机初值，这样就可以找到不同的局部最优解。当局部最优解找得足够多的时候，全局最优解很可能就包括在里面了。
4#:
这种方案在$n<6$的时候都是最优解。
当$n>=6$时，这种方案可以改进。 虽然我也认为有问题，不过一时没想到反例，另外对于这道题，不知道是否存在某个数k，同时换k个的话，就可以跳出局部最优。不过就算有，也不好证明。
总的来说，感觉是np的，所以只想了一些歪招，Fans同志的问题都挺难的，所以我只管不负责任的提出一些思路。
3#:
恐怕不行。这样只能找到一个局部最优解。
要找到全局最优解，可能需要多次随机初值，这样就可以找到不同的局部最优解。当局部最优解找得足够多的时候，全局最优解很可能就包括在里面了。 本帖最后由 qianyb 于 2011-5-16 08:55 编辑
用$(n^2-1)$条线段将$(1,1)$到$(n,n)$范围内的整点连起来，形成一棵生成树。
看似简单，实则复杂有趣。要求任意两点在生成树上的距离之和$f(n)$最小。
（即$f(n)=\sum_{1
KeyTo9_Fans 发表于 2011-5-12 12:57 http://bbs.emath.ac.cn/images/common/back.gif
这个用米字形连接时，只有$32+32sqrt(2)$
其它的用米字形连接是不是也是这样呢
刚才没看到要求平行坐标轴 谁把现在最短的结果列出来，然后再看看有没有更短的方案 $f(4)=392$
$f(5)=1200$
$f(6)=3074$
Fans同学的作图太NB了！
再不负责任的提一些想法，从上面的解来看，所有的叶子结点都可以往回收缩一个单位距离(我手头没有Fans这样的绘图工具)，这时他的父节点的权值就变为了2，其他所有节点到他的距离都减少了1，这种收缩可以一步一步的进行下去，直到最后收缩为1个点。反过来，不知道能否利用这个特性进行展开，直到布满整个格子。另外又感觉有一点点像哈夫曼树的问题，不同的是这次是有相同前缀的。
$f(4)=392$
2712
$f(5)=1200$
2713
$f(6)=3074$
2714
KeyTo9_Fans 发表于 2011-5-16 22:07 http://bbs.emath.ac.cn/images/common/back.gif
页:
[1]
2