最小生成树算法及其应用

《最小生成树算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业设计文献综述信息与计算科学最小生成树算法及其应用最小生成树(minimumspanningtree,MST)是计算机学科中一重要内容,其算法也是重要的计算方法,是现代科学中比较热门的研究方向.树是图论的重要内容,在计算机科学技术,特别是数据结构中有广泛的应用.关于加权图的应用,常常需要我们求解一棵无向生成树,使其边的总权值最小.这样的一棵生成树称作最小生成树.许多应用问题都是一个求无向连通图的最小生成树问题.例如:要在个城市之间铺设光缆,主要目标是要使这个城市的任意两个之间都可以通信,但铺设光缆的费用很高

2、,且各个城市之间铺设光缆的费用不同;另一个目标是要使铺设光缆的总费用最低.这就需要找到带权的最小生成树.MST性质:最小生成树性质:设是一个连通网络,是顶点集的一个真子集.若是中一条“一个端点在中(例如:),另一个端点不在中”的边(例如:),且具有最小权值,则一定存在的一棵最小生成树包括此边.求MST的一般算法可描述为:针对图,从空树开始,往集合中逐条选择并加入条安全边,最终生成一棵含条边的MST.当一条边加入时,必须保证仍是MST的子集,我们将这样的边称为的安全边.其中主要有两种算法:Prim算法和Krus

3、kal算法.Prim算法:该算法由Prim提出,但事实上Jarnik于1930年更早提出.用于求无向图的最小生成树.设图.步骤1:取一个顶点,则,.步骤2:选取与邻接的的最近邻元,并且边不与中元素形成回路.则添加到中,添加到中.步骤3:重复步骤2直到包含图所有顶点,则此时包含图的最小生成树的边.Prim算法实现：（1）集合:设置一个数组,初始值为,代表对应顶点不在集合中（注意:顶点号与下标号差1）.（2）图用邻接矩阵或邻接表表示,路径不通用无穷大表示,在计算机中可用一个大整数代替.Kruskal算法:每次选择

4、条边,所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小权的边加入已选择的边的集合中.注意到所选取的边若产生环路,则不可能形成一棵生成树.Kruskal算法分步,其中是网络中边的数目.按耗费递增的顺序来考虑这条边,每次只考虑一条边.当考虑某条边时,如果将其加入到已选边的集合中会出现环路,则将其抛弃,否则,把它选入.假设是一个含有个顶点的连通网,则根据Kruskal算法构造最小生成树的过程为:先构造一个只含个顶点,而边集为空的子图,若将该子图中的各个顶点看成是各棵树上的根结点,则它是一个含有棵树的一

5、个森林.然后,从网的边集中选取一条权值最小的边,若该边的两个顶点分别属于不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已经在同一棵树上,则不可取,而应该取下一条权值最小的边再尝试.依次类推,直至森林中只有一棵树,也即子图中含有条边为止.对于一个随机加权无向图,寻找其最小生成树的问题有许多重要的应用,而且解决此问题的算法至少从1920年就已经出现.然而,研究人员仍在寻求更好的方法.因为这个问题并没有得到完全的理解.经典的MST算法其实现的效率大相径庭,这些算

6、法（例如Boruvka、Prim算法等）在做运算时大都要求一次将数据读入内存中以做比较,如果处理的是大型图,内存没办法在一次就把所有的数据读入时,这些算法将受到一定局限性（虽然也有一些片外排序的技术,但其实现也不容易）.针对这个问题,罗竣友,赵军辉等提出的一种新的算法以实现在无向连通图中寻找最小生成树,基于分治法的思想,将主要的排序分为两部分,在每部分中的子运算只需求读入内存很少的数据以做比较.最小生成树不仅在计算科学中有很大应用,而且在信息,遗传问题,生物地理甚至在配电网架优化规划等方面都有着及其积极的作用

7、.陶午沙,沈振康,李吉成提出一种融合多元模糊空间关系信息的支撑树搜索算法,即S2Prim(spatialPrim)算法,用以识别低分辨率环境下(红外、多光谱遥感、SAR、恒星导航等图像中)具有规则空间分布关系的目标斑点集合.徐磊,张兢引入了节点的度的定义,据此提出了广义最小生成树的概念.采用遗传算法来求解最小生成树,井针对普通遗传算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略,通过一个有线电视网络的建摸与仿真,表明了广义最小生成树模型的适用性.分别采用普通遗传算法和改进后的遗传算

8、法进行求解,井将结果进行比较,证明了改进后的遗传算法的有效性.刘健,杨文宇,余健明,宋蒙提出了一种用于配电网络规划的改进最小生成树算法：将配电网的电源点和负荷点当作顶点,将各个顶点间可能架设线路的走廊当作边,将线路的建设费用和运行费用(主要为线损)之和作为各条边的权,在采用基本最小生成树算法获得初步规划方案的基础上,采取动态调整各条边的权值并反复迭代的方法,获得总费用最小的优化规划结果,并采用随机初