数学研发论坛

 找回密码
 欢迎注册
12
返回列表 发新帖
楼主: KeyTo9_Fans

[原创] 连接n*n的点阵,要求两点间的连线长度尽可能小

[复制链接]
 楼主| 发表于 2011-5-16 23:40:58 | 显示全部楼层
$f(7)=6636$
c7.png

#####

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

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

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

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

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

要得到全局最优解,首先要顾全大局,对整体进行大致的规划,然后再在细节方面下功夫。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-17 00:47:03 | 显示全部楼层
我认为可以从最中间的一个点,向4个方向扩展,枚举4个方向各分配多少个点,凭感觉,这些点应当是不会走回头路的,也就是向左边分配的点不会向右走。另外,这个图形在每一级根节点上状态压缩的话,是有最优子结构的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-17 02:08:45 | 显示全部楼层
我认为可以从最中间的一个点,向4个方向扩展,枚举4个方向各分配多少个点,凭感觉,这些点应当是不会走回头路的,也就是向左边分配的点不会向右走。另外,这个图形在每一级根节点上状态压缩的话,是有最优子结构的。
litaoye 发表于 2011-5-17 00:47

同意这个观点,应该不会错。只是这个过程也不是唯一的,比如分配好第k层以后,分配第k+1层点时,很多点会有多个选择(可以连接到多个第k+1个点),这时,我认为最有策略应该是尽量不均匀的分配。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-9-2 22:57:45 | 显示全部楼层
我做了一个操作界面,可以通过点击鼠标进行操作,自动计算路径长度。

cn2.PNG

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

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

cn2.rar

425.79 KB, 下载次数: 30, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-7 19:31:00 | 显示全部楼层
自己试着玩的图
阵列图.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-7 19:42:12 | 显示全部楼层
还有
阵列图2.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-13 11:49:42 | 显示全部楼层
继续
阵列图3.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-13 11:55:54 | 显示全部楼层
继续
阵列图4.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-13 11:57:28 | 显示全部楼层
继续
阵列图5.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-9-13 11:59:56 | 显示全部楼层
继续
阵列图6.JPG
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-7-3 01:53 , Processed in 0.065324 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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