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

KeyTo9_Fans

$f(7)=6636$


#####

确实可以把一个可行解看成一个收缩叶子的过程。

存在的问题是，如何确定哪些点是叶子，哪些点不是叶子。

接下来是如何确定收缩的顺序。

反过来也是同样的问题：从哪里开始扩展，往哪个方向扩展。

原问题是一个全局的优化问题。各个局部都达到了最优仍然不能保证全局是最优的。

要得到全局最优解，首先要顾全大局，对整体进行大致的规划，然后再在细节方面下功夫。

litaoye

我认为可以从最中间的一个点，向4个方向扩展，枚举4个方向各分配多少个点，凭感觉，这些点应当是不会走回头路的，也就是向左边分配的点不会向右走。另外，这个图形在每一级根节点上状态压缩的话，是有最优子结构的。

mathe

我认为可以从最中间的一个点，向4个方向扩展，枚举4个方向各分配多少个点，凭感觉，这些点应当是不会走回头路的，也就是向左边分配的点不会向右走。另外，这个图形在每一级根节点上状态压缩的话，是有最优子结构的。
litaoye 发表于 2011-5-17 00:47

同意这个观点，应该不会错。只是这个过程也不是唯一的，比如分配好第k层以后，分配第k+1层点时，很多点会有多个选择（可以连接到多个第k+1个点），这时，我认为最有策略应该是尽量不均匀的分配。

KeyTo9_Fans

我做了一个操作界面，可以通过点击鼠标进行操作，自动计算路径长度。



大家可以在操作界面上玩一下，看看能否突破我的记录。

我以后还会改进操作界面，使得操作更加方便。

wsc810

自己试着玩的图

wsc810

还有

wsc810

继续

wsc810

继续

wsc810

继续

wsc810

继续