生成树的boruvka相对经典算法的优势讨论(附件)【字数：6774】
摘 要摘 要最小生成树是近代网络（如水利流通管道网络、电力系统网络、交通枢纽网络、电信电话网络等）的一个非常重要的图论问题，算法在解决系统设计和搭建中起着非常重要的作用。求解最小生成树的问题就是求网络路的具备最小权重的生成树，而本文中我们将分别介绍贪心算法和Boruvka算法。贪心算法在求解对最小生成树问题的时候，遵循做出当前看似最理想的选择。换一种说法，即不以追求全局最优结果以考虑，它追求做出的是局部最优解。有两个算法是以贪心算法为基础的，一个是Kruskal（克鲁斯卡尔）算法，一个是Prim（普利姆算法），这两种算法的基础核心思想都是贪心算法，了解这两个算法也可以对算法优化有更深入看法。Boruvka算法也是由贪心算法为根基，但是在运算上其主要的思想是通过先完整收集合理的路径然后舍弃较长的路径，以达到算法最后最小权重的目的。通过比较贪心算法和Boruvka算法这两个算法在同一个图求解过程中算法的复杂性和权重对比来讨论两者的优劣。归纳为二个分论题来阐述一、贪心算法及Boruvka算法的基本内容及算法论证方法；二、从算法内容简便和结果精确角度将Boruvka算法与贪心算法进行比较分析。关键词生成树算法；贪心算法；Boruvka算法
目 录
第一章 绪论 1
1.1 研究背景1
1.2 最小生成树研究的进展及成果2
1.3 本文的主要内容3
第二章 生成树的Boruvka算法相对经典算法的优势讨论5
2.1 基本概念5
2.1.1 最小生成树算法5
2.1.2 贪心算法基础介绍7
2.1.3.与贪心算法相关的两个算法9
2.1.4 Boruvka算法的基础介绍11
2.2 两个生成树算法对比优势讨论13
2.3 小结14
结论15
致谢16
参考文献17
第一章 绪论
1.1 研究背景
为了满足科技发展对大数据及信息化处理的需求,伴随计算机信息技术飞速的发展、编程语言的应用技术不断提高,线性规划、贪婪策略等一系列运筹学学科的算法模型接二连三地被在计算机算法学中广泛运用,因而产生了各种解决各种现实问题 *好棒文|www.hbsrm.com +Q: ^351916072#
的有效算法。
虽然设计一个好的求解算法其实需要更多抽象思维的细胞而不是严谨的数学思维，但幸运的是存在用于解决面对各种条件复杂、维度多样的问题的算法设计方法，利用算法实际方法来设计日常应用需要解决复杂问题算法。在设计的同时，观察这些算法解决问题的模式能了解优化设计算法的方向。一般情况下，为了让算法表现得更有艺术感，需要多次尝试对算法进行精致的调整。但是在大部分情况下，简单、没有深入算法精髓的调整，新算法的性能肯定无法达到要求，或者调整后无法适用于现实条件，甚至在最后会出现大相庭径的运算结果，这时就必须寻求另外的方法来解决这个问题。
目前广泛熟知的算法设计技术有分而治法[16]、回溯法[17]、贪心算法[18]、动态规划算法等[19]。其中每个技术都有其最适用的算法，例如贪心算法是一种求最优解问题的最直接高效的设计技术，因为该技术遵循的是当前最优原则，因为并非对所有问题都能得到整体最优解，但有时却能凭借判别每一步中最优的选择以达到整体范围的最优，并且能达到消耗资源最少的效果。
贪心算法最常被运用于求解最小权重生成树。最小权重生成树，简称最小生成树（minimum spanning tree.MST），对设计和研究多点间路程相关的问题中扮演非常重要的角色，其核心考虑的问题是在保持连通最少的边的情况下，一个有n个结点的连通图的生成树是原图的极小连通子图，沟通了原图的所有的点。贪心算法有两个延展的算法，分别是kruskal（克鲁斯卡尔）算法或prim（普里姆）算法。
Boruvka算法也是研究最小权重生成树的一支古老的分支，Boruvka算法一直被认为是Kruskal算法的增广版，然而不仅仅如此。Boruvka算法这是分步完成，每一步都增加多条MST边，最后再将所增的MST边整合。
最小生成树是近年来计算机学术科目中一非常重要的内容，是现代数学及计算机学科中相对热门的研究方向，对该课题的研究在一定程度上对计算机科学在应用及学术有一定积极推进作用的影响。通过深入对比Boruvka算法和贪心算法在算法简洁性和结果精确度两个角度的优劣，了解这个贪心算法算法发展的更优方向，提高算法建议性和准确性。
1.2最小生成树研究的进展及成果
随着最小生成树的研究被广泛应用，近年来许多新的技术也逐渐反过来影响最小生成树的研究以及改变其研究的方向。对最小生成树的研究方向的制定是离不开其在技术方面的实际应用的反向指导的。通过对近年来最小生成树应用成果不断更新的了解，便能清除地看出其研究的进展。
目 录
第一章 绪论 1
1.1 研究背景1
1.2 最小生成树研究的进展及成果2
1.3 本文的主要内容3
第二章 生成树的Boruvka算法相对经典算法的优势讨论5
2.1 基本概念5
2.1.1 最小生成树算法5
2.1.2 贪心算法基础介绍7
2.1.3.与贪心算法相关的两个算法9
2.1.4 Boruvka算法的基础介绍11
2.2 两个生成树算法对比优势讨论13
2.3 小结14
结论15
致谢16
参考文献17
第一章 绪论
1.1 研究背景
为了满足科技发展对大数据及信息化处理的需求,伴随计算机信息技术飞速的发展、编程语言的应用技术不断提高,线性规划、贪婪策略等一系列运筹学学科的算法模型接二连三地被在计算机算法学中广泛运用,因而产生了各种解决各种现实问题 *好棒文|www.hbsrm.com +Q: ^351916072#
的有效算法。
虽然设计一个好的求解算法其实需要更多抽象思维的细胞而不是严谨的数学思维，但幸运的是存在用于解决面对各种条件复杂、维度多样的问题的算法设计方法，利用算法实际方法来设计日常应用需要解决复杂问题算法。在设计的同时，观察这些算法解决问题的模式能了解优化设计算法的方向。一般情况下，为了让算法表现得更有艺术感，需要多次尝试对算法进行精致的调整。但是在大部分情况下，简单、没有深入算法精髓的调整，新算法的性能肯定无法达到要求，或者调整后无法适用于现实条件，甚至在最后会出现大相庭径的运算结果，这时就必须寻求另外的方法来解决这个问题。
目前广泛熟知的算法设计技术有分而治法[16]、回溯法[17]、贪心算法[18]、动态规划算法等[19]。其中每个技术都有其最适用的算法，例如贪心算法是一种求最优解问题的最直接高效的设计技术，因为该技术遵循的是当前最优原则，因为并非对所有问题都能得到整体最优解，但有时却能凭借判别每一步中最优的选择以达到整体范围的最优，并且能达到消耗资源最少的效果。
贪心算法最常被运用于求解最小权重生成树。最小权重生成树，简称最小生成树（minimum spanning tree.MST），对设计和研究多点间路程相关的问题中扮演非常重要的角色，其核心考虑的问题是在保持连通最少的边的情况下，一个有n个结点的连通图的生成树是原图的极小连通子图，沟通了原图的所有的点。贪心算法有两个延展的算法，分别是kruskal（克鲁斯卡尔）算法或prim（普里姆）算法。
Boruvka算法也是研究最小权重生成树的一支古老的分支，Boruvka算法一直被认为是Kruskal算法的增广版，然而不仅仅如此。Boruvka算法这是分步完成，每一步都增加多条MST边，最后再将所增的MST边整合。
最小生成树是近年来计算机学术科目中一非常重要的内容，是现代数学及计算机学科中相对热门的研究方向，对该课题的研究在一定程度上对计算机科学在应用及学术有一定积极推进作用的影响。通过深入对比Boruvka算法和贪心算法在算法简洁性和结果精确度两个角度的优劣，了解这个贪心算法算法发展的更优方向，提高算法建议性和准确性。
1.2最小生成树研究的进展及成果
随着最小生成树的研究被广泛应用，近年来许多新的技术也逐渐反过来影响最小生成树的研究以及改变其研究的方向。对最小生成树的研究方向的制定是离不开其在技术方面的实际应用的反向指导的。通过对近年来最小生成树应用成果不断更新的了解，便能清除地看出其研究的进展。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/717.html
