首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

求最短路径有关问题

2012-02-12 
求最短路径问题平面上有 N 堆点,将这些点两两相连起来(两两相连的意思是:只要求某两个点连接,而这两个点不

求最短路径问题
平面上有 N 堆点,将这些点两两相连起来(两两相连的意思是:只要求某两个点连接,而这两个点不与其他的点连接),求一种方法,能使得最后,所有的连接着的两个点的之间的距离总和最小; 要求:堆与堆之间有且只有一个连接;

[解决办法]
N为奇数,怎么办? 忽略掉那个点? 还是把它也连进去?
[解决办法]
肯定不是最优解,不过在一般情况下应该能蒙混过关吧~~

初步的思路:如果这些点集合能分成比较密集的2组,不严密的说可以看做这2个集合内部点的距离基本上会小于集合之间的点的距离。自然的,优先在这2组内进行内部点的连接,然后再考虑集合之间。
然后再在每一个集合内不停的往下分

于是大致的算法就是:
Step1:将全集采用某种分类策略分成2个子集。
Step2:若其中有子集中的点数>2,则将该子集再拆分为2个子集,依次递归。
经过这样的拆分,最后会出来一大堆包含1个点以及包含2个点的集合。
Step3:将所有包含两个点的集合对其中的两个点进行直连,并将它们从全集中除去。
Step4:若全局中仍然有点,返回Step1。

================================================
砖头拍出来了,后面的跟上~~

热点排行