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