最小点覆盖近似算法及其应用研究

发布时间：2017-06-25 06:07

  本文关键词：最小点覆盖近似算法及其应用研究，由笔耕文化传播整理发布。

【摘要】：最小点覆盖问题,是指给定一个无向图?EVG),(,其中V为顶点集,E为边集,求顶点集V的一个最小子集S,使得对于边集E的任意一条边Euv?,有Su?或Sv?.最小点覆盖问题是组合优化中一个典型的NP完全问题,因其有着广泛的应用,所以备受关注.至今虽然已经有很多求解该问题的近似算法,但许多人仍致力于最小点覆盖的研究,以便寻求更简洁、更精确的算法.因此,本文利用经典的最短路算法Dijkstra算法和蚁群算法对最小点覆盖问题分别进行了研究,具体内容如下:(1)基于最短路算法,分别研究了无权图与赋权图的最小点覆盖问题,并设计了算法.首先,在给定的图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.(2)关于蚁群算法,研究了赋权图的最小点覆盖问题.给出了一个基于蚁群算法的近似算法,求解最小点覆盖问题的近似解.通过修改蚂蚁的状态转移概率公式,简化状态转移规则,建立了相应的数学模型,从而得出求解最小点覆盖的近似算法步骤,最后进行了实例解析.(3)将最小点覆盖问题应用到求解停车场选址问题中.利用已获得的近似算法,对停车场选址问题进行了求解,并且给出了停车场选址问题的较优方案.
【关键词】：最小点覆盖 近似算法 Dijkstra算法 蚁群算法 停车场选址
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-8
• 1 绪论8-10
• 1.1 研究动态及现状8-9
• 1.2 研究目的及意义9
• 1.3 目前该领域存在的问题9
• 1.4 研究内容和方法9-10
• 2 基于最短路算法的最小点覆盖问题10-24
• 2.1 引言10
• 2.2 算法设计10-14
• 2.2.1 无权图的最小点覆盖问题12
• 2.2.2 点赋权图的最小点覆盖问题12-13
• 2.2.3 边赋权图的最小点覆盖问题13
• 2.2.4 点、边赋权图的最小点覆盖问题13-14
• 2.3 算法实例14-22
• 2.3.1 无赋权图算法实例14-16
• 2.3.2 点赋权图算法实例16-18
• 2.3.3 边赋权图算法实例18-20
• 2.3.4 点、边赋权图算法实例20-22
• 2.4 算法性质22-23
• 2.5 本章小结23-24
• 3 基于蚁群算法的最小点覆盖问题24-30
• 3.1 蚁群算法24-27
• 3.1.1 蚁群算法基本原理24-25
• 3.1.2 蚁群算法解决最小点覆盖问题的基本原理25-27
• 3.2 算法设计27-28
• 3.3 算法实例28-29
• 3.4 本章小结29-30
• 4 最小点覆盖问题在实际中的应用30-33
• 4.1 引言30
• 4.2 模型建立及应用30-32
• 4.3 本章小结32-33
• 结论33-34
• 致谢34-35
• 参考文献35-37
• 读学位期间的研究成果37

【相似文献】

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

1 孙俊逸;一类函数最小点及最小值的插值解法[J];阜阳师范学院学报(自然科学版);1993年01期

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

1 崔笑川;最小点覆盖近似算法及其应用研究[D];兰州交通大学;2015年

2 许小双;二分图的受约束最小点覆盖问题研究[D];中南大学;2007年

3 常乐;参数化点覆盖及最小点覆盖问题研究[D];中南大学;2007年

  本文关键词：最小点覆盖近似算法及其应用研究，由笔耕文化传播整理发布。

，

本文编号：481019