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

KeyTo9_Fans

用$(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$

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