学位论文 > 优秀研究生学位论文题录展示

最小标记生成树问题的研究与拓展

作　者: 徐忆晨
导　师: Rudolf Fleischer
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 最小标记生成树启发式算法确定参数可解限制树宽
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 42次
引　用: 0次
阅　读: 论文下载

内容摘要

许多组合最优问题都可以抽象为计算图的生成树问题。最小标记生成树就是其中之一,它的目标是给出一个边上带有颜色的图,计算使用颜色种类最少的生成树。这个问题在通信网络领域有广泛应用,其中颜色代表了通信使用材料,这些材料可能是由竞争关系的厂商提供,如果能找到使用材料种类最少的通信网络的生成树,就可以减少构造成本和网络复杂性。最小标记生成树问题最早由Chang R.S.和Leu S.J.在1997年提出。它是NP-hard问题,而且不存在近似度为常数的近似算法,除非P=NP。本文使用了另一种研究方向,研究一类满足特殊性质的图,也就是树宽为常数的一类图,在这类图上得到了时间复杂度良好的算法。另外,在一般图上,本文基于MVCA贪婪算法提出了基于一般图的几个重要的启发式算法,包括轴方法算法、变邻域搜索算法,并给出了实验结果,得出了一些有用的结论,为未来的进一步研究提供了借鉴,指出了方向。此外,我们对最小生成树的变体问题,多重标记最小标记生成树做了初步研究,提出了启发式算法并和MVCA做了对比,下一步的研究方向可能从理论上给出严格的证明,并且挖掘更多高效的启发式算法。

全文目录

摘要  5-6
ABSTRACT  6-7
第一章引言  7-10
  1.1 研究背景与动机  7-8
  1.2 历史回顾  8
  1.3 本文工作  8-9
  1.4 文章结构  9-10
第二章最小标记生成树的研究与进展  10-15
  2.1 MLST的研究以及相关的启发式算法  10-13
  2.2 MLST的精确算法  13-15
第三章限制树宽图的最小标记生成树算法  15-23
  3.1 参数复杂性  15-16
  3.2 一般图的确定参数可解算法  16-18
  3.3 限制树宽图的确定参数可解算法  18-23
第四章 MLST启发式算法的研究与拓展  23-43
  4.1 启发式算法概述  23-24
  4.2 MLST的启发式算法  24-29
  4.3 实验结果与分析  29-42
  4.4 实验结论  42-43
第五章最小标记生成树变体问题的研究  43-57
  5.1 多标记最小标记生成树算法  43-46
  5.2 实验数据与分析  46-54
  5.3 数据统计和结论  54-57
第六章总结与展望  57-58
参考文献  58-59
附录  59-60
  5.4 硕士在读期间发表的学术论文  59-60
致谢  60-61

最小标记生成树问题的研究与拓展

内容摘要

全文目录

相似论文