树覆盖问题的精确算法和启发式算法设计

目录

声明

摘要

第1章绪论

1．1最小最大树覆盖问题和有界树覆盖问题的研究背景

1．2国内外研究现状

1．3解决的主要问题

1．4本文的主要工作

1．5论文的组织结构

第2章最小最大树覆盖问题的精确算法设计与分析

2．1动态规划

2．2集合覆盖问题

2．3具体实现

2．4时间复杂度

第3章有界树覆盖问题的精确算法设计与分析

3．1第一种精确算法

3．1．2时间复杂度

3．2容斥原理

3．3第二种精确算法

3．3．1具体设计

3．3．2时间复杂度

第4章最小最大树覆盖问题的启发式算法及实验

4．1启发式算法

4．2预备知识

4．3基于最小生成树的分割算法

4．3．1随机分割算法

4．3．2最大分割算法

4．3．3平均分剖算法

4．3．4结构分割算法

4．4基于全局分割的贪心算法

4．4．1一次平均

4．4．2多次平均

4．5六种启发式算法性能的衡量与比较

4．5．1伪近似比

4．5．2最优解下界的求解算法

4．5．3测试样例的生成及处理方法

4．5．4实验设计与结果

4．6本章小结

5．1全文总结

5．2展望

参考文献

致谢