| 目录 | 第3-5页 |
| 摘要 | 第5-7页 |
| ABSTRACT | 第7-8页 |
| 第1章 引言 | 第9-11页 |
| 第2章 算法概述 | 第11-17页 |
| 2.1 问题的复杂度 | 第11-12页 |
| 2.2 问题的多项式时间变换 | 第12页 |
| 2.3 P类、NP类、NPC类和NP-HARD问题 | 第12-13页 |
| 2.4 回溯和分支定界技术 | 第13-16页 |
| 2.4.1 回溯法 | 第13-14页 |
| 2.4.2 分支定界法 | 第14-16页 |
| 2.5 近似算法及其性能评估 | 第16-17页 |
| 第3章 问题介绍 | 第17-21页 |
| 3.1 概述 | 第17-19页 |
| 3.2 无环二分图可表达的集合覆盖问题 | 第19-21页 |
| 第4章 经典的SCP的近似算法 | 第21-30页 |
| 4.1 贪心法求解SCP问题 | 第21-25页 |
| 4.1.1 集合覆盖的贪心算法(Greedy Set cover) | 第21-23页 |
| 4.1.2 带权重的集合覆盖贪心算法(Greedy Weighted Set Cover) | 第23-25页 |
| 4.2 线性规划法 | 第25-30页 |
| 4.2.1 线性规划问题(linear program) | 第25页 |
| 4.2.2 集合覆盖问题的线性规划后取整 | 第25-30页 |
| 第5章 无环二分图可表达的集合覆盖问题的多项式时间算法 | 第30-37页 |
| 5.1 集合覆盖问题的二分图表示法 | 第30-31页 |
| 5.2 无环二分图可表示的带容量限制集合覆盖精确算法 | 第31-37页 |
| 第6章 用分支定界技术解决带权重有容量限制的集合覆盖问题 | 第37-46页 |
| 6.1 解树与回溯搜索法 | 第38-40页 |
| 6.2 加速搜索的技术与编程实现 | 第40-42页 |
| 6.3 随机近似算法 | 第42-46页 |
| 第7章 结论和展望 | 第46-47页 |
| 参考文献 | 第47-49页 |
| 致谢 | 第49-50页 |
| 攻读学位期间发表的学术论文和参加的工作 | 第50-51页 |
| 学位论文评阅及答辩情况表 | 第51页 |
