连接n*n的点阵，要求两点间的连线长度尽可能小

KeyTo9_Fans

用$(n^2-1)$条线段将$(1,1)$到$(n,n)$范围内的整点连起来，形成一棵生成树。

要求任意两点在生成树上的距离之和$f(n)$最小。 （即$f(n)=\sum_{1<=i 距离表： 距离之和$f(2)=1+3+2+2+1+1=10$ 例$2$：当$n=3$时，连接方案如下： 距离表： 距离之和$f(3)=1+2+3+2+...+1+2+1=84$

gxqcn

这个问题比较有意思。 对于$n=3$，考察纳粹标志“卐”，其距离和$f(3)=88>84$。

litaoye

先随机一个生成树，然后换一条边找增广，直到找不到增广，可以么？

zeroieme

就是N条横杠加中间一竖

KeyTo9_Fans

3#: 恐怕不行。这样只能找到一个局部最优解。 要找到全局最优解，可能需要多次随机初值，这样就可以找到不同的局部最优解。当局部最优解找得足够多的时候，全局最优解很可能就包括在里面了。 4#: 这种方案在$n<6$的时候都是最优解。 当$n>=6$时，这种方案可以改进。

litaoye

虽然我也认为有问题，不过一时没想到反例，另外对于这道题，不知道是否存在某个数k，同时换k个的话，就可以跳出局部最优。不过就算有，也不好证明。 总的来说，感觉是np的，所以只想了一些歪招，Fans同志的问题都挺难的，所以我只管不负责任的提出一些思路。

3#: 恐怕不行。这样只能找到一个局部最优解。 要找到全局最优解，可能需要多次随机初值，这样就可以找到不同的局部最优解。当局部最优解找得足够多的时候，全局最优解很可能就包括在里面了。

qianyb

用$(n^2-1)$条线段将$(1,1)$到$(n,n)$范围内的整点连起来，形成一棵生成树。 看似简单，实则复杂有趣。要求任意两点在生成树上的距离之和$f(n)$最小。 （即$f(n)=\sum_{1 KeyTo9_Fans 发表于 2011-5-12 12:57

这个用米字形连接时，只有$32+32sqrt(2)$ 其它的用米字形连接是不是也是这样呢 刚才没看到要求平行坐标轴

qianyb

谁把现在最短的结果列出来，然后再看看有没有更短的方案

KeyTo9_Fans

$f(4)=392$ $f(5)=1200$ $f(6)=3074$

litaoye

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