开题报告
信息与计算科学
最小生成树算法及其应用
一、综述本课题国内外研究动态, 说明选题的依据和意义
最小生成树(minimum spanning tree,MST)是计算机学科中一重要内容, 其算法也是重要的计算方法, 是现代科学中比较热门的研究方向.
一个有个结点的连通图的生成树是原图的极小连通子图,
且包含原图中的所有个n n 结点, 并且有保持图联通的最少的边.
许多应用问题都是一个求五项连通图的最小生成树问题. 例如: 要在个城市之间铺设n 光缆, 主要目标是要使这个城市的任意两个之间都可以通信, 但铺设光缆的费用很高, n 且各个城市之间铺设光缆的费用不同; 另一个目标是要使铺设光缆的总费用最低. 这就需要找到带权的最小生成树.
MST 性质: 最小生成树性质: 设是一个连通网络, 是顶点集的一个真(,)G V E =U V 子集. 若是中一条“一个端点在中(例如: ), 另一个端点不在中”的边(,)n u v G U u U ∈U (例如:), 且具有最小权值, 则一定存在的一棵最小生成树包括此边v V U ∈-(,)u v G .
(,)u v 求MST 的一般算法可描述为: 针对图, 从空树开始, 往集合中逐条选择并G T T 加入条安全边, 最终生成一棵含条边的MST.
1n -(,)u v 1n -当一条边加入时, 必须保证仍是MST 的子集, 我们将这样的边称(,)u v T {}(,)T u v 为的安全边. 其中主要有两种算法: Prim 算法和Kruskal 算法.
T Prim 算法: 该算法由Prim 提出, 但事实上Jarnik 于1930年更早提出. 用于求无向图的最小生成树.
设图 .
(),G V E =步骤1: 取一个顶点, 则, .
1v {}1V v ={}E =
步骤2: 选取与邻接的的最近邻元, 并且边不与中元素形成回路. j v V ∈V i v (),i j v v E 则添加到中, 添加到中.
i v V (),i j v v E 步骤3: 重复步骤2直到包含图所有顶点, 则此时包含图的最小生成树的边. V G E G Prim 算法实现：
（1）集合: 设置一个数组, 初始值为, 代表对应顶点不在集合()0,1,,1set i n =- 0中（注意: 顶点号与下标号差1）.
（2）图用邻接矩阵或邻接表表示, 路径不通用无穷大表示, 在计算机中可用一个大整数（如 ）代替.
130=Kruskal 算法: 每次选择条边, 所使用的贪婪准则是: 从剩下的边中选择一条不会1n -产生环路的具有最小权的边加入已选择的边的集合中. 注意到所选取的边若产生环路, 则不可能形成一棵生成树. Kruskal 算法分步, 其中是网络中边的数目. 按耗费递增的顺序来e e 考虑这条边, 每次只考虑一条边. 当考虑某条边时, 如果将其加入到已选边的集合中会出e 现环路, 则将其抛弃, 否则, 把它选入. 假设是一个含有个顶点的连通[]9{}()
,WN V E =n 网, 则根据Kruskal 算法构造最小生成树的过程为: 先构造一个只含个顶点, 而边集为空n 的子图, 若将该子图中的各个顶点看成是各棵树上的根结点, 则它是一个含有棵树的一个n 森林. 然后, 从网的边集中选取一条权值最小的边, 若该边的两个顶点分别属于不同的E 树, 则将其加入子图, 也就是说, 将这两个顶点分别所在的两棵树合成一棵树; 反之, 若该条边的两个顶点已经在同一棵树上, 则不可取, 而应该取下一条权值最小的边再尝试. 依次类推, 直至森林中只有一棵树, 也即子图中含有条边为止.
1n -因此, 最小生成树是一种很有现实意义的算法, 熟练的运用最小生成树的几种重要算法可以解决各类现实问题.
算法的诸多优势也自然越发受到数学、计算机等不同领域内学者的重视.
最小生成树不仅在计算科学中有很大应用, 而且在信息, 遗传问题, 生物地理甚至在配电网架优化规划等方面都有着及其积极的作用.
陶午沙, 沈振康, 李吉成提出一种融合多元模糊空间关系信息的支撑树搜索算法,即S2Prim(spatial Prim)算法, 用以识别低分辨率环境下(红外、多光谱遥感、SAR 、恒星导航等图像中)具有规则空间分布关系的目标斑点集合.
徐磊, 张兢引入了节点的度的定义, 据此提出了广义最小生成树的概念. 采用遗传算法
来求解最小生成树, 井针对普通遗传算法求解该问题的不足, 提出了自调整的变异算子和限制父代个体数目的混合选择策略, 通过一个有线电视网络的建摸与仿真, 表明了广义最小生成树模型的适用性. 分别采用普通遗传算法和改进后的遗传算法进行求解, 井将结果进行比较, 证明了改进后的遗传算法的有效性.
因此, 最小生成树是一种很有现实意义的算法, 熟练的运用最小生成树的几种重要算法可以解决各类现实问题. 算法的诸多优势也自然越发受到数学、计算机等不同领域内学者的重视.
二、研究的基本内容, 拟解决的主要问题
研究的基本内容: 最小生成树算法
解决的主要问题：
1. 阐述计算机学科中的最小生成树算法.
C
2. 用语言实现几种具有代表性的算法, 并分析所得到的结果, 以达到对比各种算法
的目的.
3. 简略的介绍最小生成树在各领域的发展及应用.
三、研究步骤、方法及措施
研究步骤:
1. 查阅相关资料, 做好笔记;
2. 仔细阅读研究文献资料;
3. 撰写开题报告;
4. 翻译英文资料;
5. 在老师指导下, 修改英文翻译, 撰写文献综述;
6. 开题报告通过后, 撰写毕业论文;
7. 上交论文初稿;
8. 反复修改论文;
9. 论文定稿.
措施: 通过到图书馆、上网等方式查阅收集资料, 在学校图书馆数据库里查找所需的文章与电子书, 并参考与研究相关的资料. 在老师指导下, 通过全面与具体相结合的方法对问题进行阐述.
四、参考文献
[1] 马叔良. 离散数学[M]. 北京: 电子工业出版社, 2009. 319~320.
[2] 王元元, 张桂芸.计算机科学中的离散结构[M]. 北京: 机械工业出版社, 2004, 15(4): 23～25.
[3] Seth Pettie, Vijaya Ramachandran, An Optimal Minimum Spanning Tree Algorithm [J], Journal of the ACM, 2002, 49(1): 16~34.
[4] Anany Levitin, Introduction to The Design and Analysis of Algorithms, 北京: 清华大学出版社, 2004 .
[5] 罗竣友, 赵军辉. 一种新的最小生成树算法[J]. 澳门科技大学, 2009, 35(3): 1793~1797.
[6] 陶午沙, 沈振康, 李吉成. 一种基于模糊信息融合的Prim算法及应用[J]. 国防科技大学, 2005, 3, (26): 80~81.
[7] 徐磊, 章兢. 广义最小生成树的遗传算法求解及应用[J]. 系统工程与电子技术, 2004,26(3):390~392.。