求解度约束最小生成树问题的启发式算法研究

声明

1 绪论

1.1课题背景及意义

1.2相关问题描述

1.2.1最小生成树问题

1.2.2哈密顿回路问题

1.2.3斯坦纳树问题

1.2.4 DCMST问题

1.3国内外研究现状

1.4本文主要研究内容

2 相关理论基础

2.1与DCMST相关的理论

2.1.1图

2.1.2简单图

2.1.3子图

2.1.4删除或增加图中的边

2.1.5连通图

2.1.6树

2.2带度约束的最小生成树问题数学模型

2.3 DCMST问题分析

2.3.1 DCMST问题难点分析及复杂度证明

2.3.2 DCMST求解过程中的影响因素

2.3.3不同类型求解算法的优势和劣势

2.4启发式算法相关理论

2.4.1组合优化问题

2.4.2启发式算法

2.5本章小结

3 求解DCMST问题的禁忌搜索算法

3.1算法总体流程

3.2 TS-DCST算法中的策略设计

3.2.1局部搜索策略

3.2.2禁忌及解禁策略

3.2.3扰动策略

3.2.4增量评估技术

3.3 TS-DCST算法分析

3.3.1时间复杂度分析

3.3.2空间复杂度分析

3.4 TS-DCST算法讨论

3.5本章小结

4 实验与结果分析

4.1算例介绍

4.2求解环境

4.3求解结果与分析

4.3.1测试相关影响因素

4.3.2求解质量分析

4.4本章小结

5 总结与展望

5.1论文工作总结

5.2未来工作展望

致谢

参考文献