最大流问题及欧几里德Steiner树问题初探

发布时间：2017-12-19 12:24

  本文关键词：最大流问题及欧几里德Steiner树问题初探　出处：《青海师范大学》2016年硕士论文　论文类型：学位论文

  更多相关文章： 增广路算法 最短增广路 Steiner最小树 Steiner点

【摘要】：最大流问题及欧几里德Steiner树问题都是运筹学领域取得迅速发展的理论,无论从理论上还是实际应用中,它们的建立和求解算法的不断改进为解决很多实际问题提供了十分重要的工具.除了用于具体的数学问题的优化外,它们还在工程计算机原理、通信系统、应用数学、社会以及军事等实际领域方面有着广泛的应用.它们都是组合优化中的一个NP难解问题,难求解是该问题的固有属性,虽然对于最大流问题及欧几里德Steiner树问题研究已经持续了几十年,该类问题的研究进展已经得到很大的提高,但是它们的研究还有很大的空间去探索.本文具体内容包括:第一章阐述最大流问题及欧几里德Steiner树问题的研究进展、应用背景以及研究意义.第二章概述最大流问题的研究、经典增广路算法、算法进展以及算法时间复杂度,并对最短路增广路算法改进最大流问题的证明进行了补充修正.第三章介绍Steiner树问题、算法研究现状,重点讨论欧几里德Steiner树问题.概述欧几里德Steiner最小树的性质以及构造Steiner树的复杂性,并讨论证明欧式平面内三个点、四个点、五个点的Steiner最小树的构造情况.第四章对本文内容进行总结,给出问题研究的难点与期望.
【学位授予单位】：青海师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O224

【相似文献】

中国期刊全文数据库 前10条

1 曹翠珍;最大流问题与突发事件的应对[J];科技进步与对策;2004年09期

2 凌永发;王杰;李正明;;网络最大流问题典型组合算法研究[J];云南民族大学学报(自然科学版);2006年03期

3 张丰;罗罕勋;;一类网络最大流问题的简便算法[J];中国科技信息;2009年07期

4 朱永津,田丰,马仲蕃,蔡茂诚;网络上两类物资联合最大流问题的极流特征[J];中国科学;1974年06期

5 周玉涛;;基于层次网络的最大流问题研究[J];科技广场;2008年01期

6 柴丽琴;王红昌;;网络最大流问题应用实例研究[J];全国商情(理论研究);2013年17期

7 张远福,叶正道,唐静波;一个制造网络的最大流算法[J];工程数学学报;2005年05期

8 毛华;毛晓亮;李斌;;网络最大流部分割矩阵算法[J];计算机科学;2011年12期

9 周隆盛;;计算机用‘自学习’算法求解网络最大流问题[J];郑州大学学报(自然科学版);1986年01期

10 盖宇仙;李方豫;颉栋栋;;一类流量增减最大值可预见的不确定网络最大流的模型与算法[J];兰州交通大学学报;2007年04期

中国重要会议论文全文数据库 前2条

1 刘文涛;张群;陈子毅;;基于网络最大流的瓶颈分析[A];管理科学与系统科学研究新进展——第8届全国青年管理科学与系统科学学术会议论文集[C];2005年

2 史新生;董志强;方志耕;;应用逻辑割树模型求解模糊可靠条件下的网络最大流问题研究[A];面向复杂系统的管理理论与信息系统技术学术会议专辑[C];2000年

中国硕士学位论文全文数据库 前10条

1 杜政均;一种新的最大流算法的研究[D];电子科技大学;2015年

2 刁强强;最大流问题及欧几里德Steiner树问题初探[D];青海师范大学;2016年

3 许显胜;快速求解大规模网络最大流问题的研究[D];安徽大学;2013年

4 景虹;最大流算法的仿真与分析[D];华中科技大学;2009年

5 周广露;不确定图上的最大流研究[D];哈尔滨工业大学;2014年

6 郭玉芬;网络最大流及回收中心选址问题研究[D];湖南大学;2008年

7 孟晓婉;网络最大流算法与应用研究[D];南京邮电大学;2013年

8 陈静;容差修正网络最大流算法研究[D];燕山大学;2009年

9 李天南;基于最大流的车辆容迟网络路由算法研究[D];上海交通大学;2011年

10 苏建忠;基于粒化思想求解大规模网络最大流的研究[D];安徽大学;2014年

，

本文编号：1307969