资源描述：
《最小生成树算法及其应用【开题报告】》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、毕业设计开题报告信息与计算科学最小生成树算法及其应用一、综述本课题国内外研究动态,说明选题的依据和意义最小生成树(minimumspanningtree,MST)是计算机学科中一重要内容,其算法也是重要的计算方法,是现代科学中比较热门的研究方向.一个有个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有个结点,并且有保持图联通的最少的边.许多应用问题都是一个求五项连通图的最小生成树问题.例如:要在个城市之间铺设光缆,主要目标是要使这个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同;另一个目标是
2、要使铺设光缆的总费用最低.这就需要找到带权的最小生成树.MST性质:最小生成树性质:设是一个连通网络,是顶点集的一个真子集.若是中一条“一个端点在中(例如:),另一个端点不在中”的边(例如:),且具有最小权值,则一定存在的一棵最小生成树包括此边.求MST的一般算法可描述为:针对图,从空树开始,往集合中逐条选择并加入条安全边,最终生成一棵含条边的MST.当一条边加入时,必须保证仍是MST的子集,我们将这样的边称为的安全边.其中主要有两种算法:Prim算法和Kruskal算法.Prim算法:该算法由Prim提出,但事实上Jarnik于1930年
3、更早提出.用于求无向图的最小生成树.设图.步骤1:取一个顶点,则,.步骤2:选取与邻接的的最近邻元,并且边不与中元素形成回路.则添加到中,添加到中.步骤3:重复步骤2直到包含图所有顶点,则此时包含图的最小生成树的边.Prim算法实现：（1）集合:设置一个数组,初始值为,代表对应顶点不在集合中（注意:顶点号与下标号差1）.（2）图用邻接矩阵或邻接表表示,路径不通用无穷大表示,在计算机中可用一个大整数（如）代替.Kruskal算法:每次选择条边,所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小权的边加入已选择的边的集合中.注意到所
4、选取的边若产生环路,则不可能形成一棵生成树.Kruskal算法分步,其中是网络中边的数目.按耗费递增的顺序来考虑这条边,每次只考虑一条边.当考虑某条边时,如果将其加入到已选边的集合中会出现环路,则将其抛弃,否则,把它选入.假设是一个含有个顶点的连通网,则根据Kruskal算法构造最小生成树的过程为:先构造一个只含个顶点,而边集为空的子图,若将该子图中的各个顶点看成是各棵树上的根结点,则它是一个含有棵树的一个森林.然后,从网的边集中选取一条权值最小的边,若该边的两个顶点分别属于不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合
5、成一棵树;反之,若该条边的两个顶点已经在同一棵树上,则不可取,而应该取下一条权值最小的边再尝试.依次类推,直至森林中只有一棵树,也即子图中含有条边为止.因此,最小生成树是一种很有现实意义的算法,熟练的运用最小生成树的几种重要算法可以解决各类现实问题.算法的诸多优势也自然越发受到数学、计算机等不同领域内学者的重视.最小生成树不仅在计算科学中有很大应用,而且在信息,遗传问题,生物地理甚至在配电网架优化规划等方面都有着及其积极的作用.陶午沙,沈振康,李吉成提出一种融合多元模糊空间关系信息的支撑树搜索算法,即S2Prim(spatialPrim)算
6、法,用以识别低分辨率环境下(红外、多光谱遥感、SAR、恒星导航等图像中)具有规则空间分布关系的目标斑点集合.徐磊,张兢引入了节点的度的定义,据此提出了广义最小生成树的概念.采用遗传算法来求解最小生成树,井针对普通遗传算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略,通过一个有线电视网络的建摸与仿真,表明了广义最小生成树模型的适用性.分别采用普通遗传算法和改进后的遗传算法进行求解,井将结果进行比较,证明了改进后的遗传算法的有效性.因此,最小生成树是一种很有现实意义的算法,熟练的运用最小生成树的几种重要算法可以解决各
7、类现实问题.算法的诸多优势也自然越发受到数学、计算机等不同领域内学者的重视.二、研究的基本内容,拟解决的主要问题研究的基本内容:最小生成树算法解决的主要问题：1.阐述计算机学科中的最小生成树算法.2.用语言实现几种具有代表性的算法,并分析所得到的结果,以达到对比各种算法的目的.3.简略的介绍最小生成树在各领域的发展及应用.三、研究步骤、方法及措施研究步骤:1.查阅相关资料,做好笔记;2.仔细阅读研究文献资料;3.撰写开题报告;4.翻译英文资料;5.在老师指导下,修改英文翻译,撰写文献综述;6.开题报告通过后,撰写毕业论文;7.上交论文初稿;
8、8.反复修改论文;9.论文定稿.措施:通过到图书馆、上网等方式查阅收集资料,在学校图书馆数据库里查找所需的文章与电子书,并参考与研究相关的资料.在老师指导下,通过全面与具体相结合
