数学建模社区-数学中国

标题: 图论在算法设计中的应用 [打印本页]
作者: 雩风三日    时间: 2020-12-29 15:12
标题: 图论在算法设计中的应用
图论在算法设计中的应用
4 X- S# A. K& Z0 {+ g! }1 e' }; Q* e- y% [8 P. R
: I4 Q  l3 e6 P. }% J7 c* W
   图论是一门古老的学科，它的诞生可追溯到1736年。在离散数学领域内，图论占有主导地位。图论具有直观、清晰、解决问题简捷等特点，更重要的是，实际中的许多实际问题可以划成等价的图论问题。正因为如此，图论具有广泛的应用价值，图论可将各种复杂的工程系统和管理问题用“图”来描述，然后用数学方法求得最优结果。图论中所研究的“图”，是由若干个点，称作顶点和若干条连接两顶点的线段称作边，组成。通常顶点可用来表示事物，边用来表示这些事物之间的关系。顶点的位置、边的长短是无关紧要的，当是可以设定不同的边的权值来表示顶点间的关系强弱。图论是解决许多工程问题中算法设计的一种有效地数学模型，便于计算分析和计算机存储。* U2 ^' ~. i1 r9 X% G
    算法是解决问题的一系列步骤的集合。因此，算法设计与分析对于问题的解决至关重要。作为离散数学重要的组成部分，图论已成为当今算法设计中的一项重要内容。因为图论与算法问题有着密切关系，“图”为一些算法问题提供了一个直观的数学平台，图的理论也为这些算法的实现提供了理论依据。事实上，众多的算法问题都直接或间接地与图有关。例如在NP完全问题中有相当一部分是图论问题或与”图”有关。8 v( m, m  s" U# a6 j6 S
    基于图论的上述优点，从而将图论的相关理论引用到算法设计中来。本文首先介绍一些图论的理论以及他们的应用。从最小生成树得到的算法出发，分析和总结最小生成树算法的优点和不足，进而提出一种基于最小生成树的改进算法应用于聚类分析算法中，之后对算法进行了分析，从中解释它在解决一些聚类问题的高效性优点。* X4 \! I: v( h

# ]% ~1 D9 u, S7 w% c  `2 h: w6 Y- p' Z关键词:图论；算法设计；聚类；最小生成树；改进的最小生成树算法
6 T( u' ~) U8 x9 d2 O2 h# t3 w0 P. c( ]  ~" d' }; t
8 A7 o. ^0 D" G3 Z

搜术网soosci.com_图论在算法设计中的应用.caj

2.48 MB, 下载次数: 0, 下载积分: 体力 -2 点



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5