求解多维背包约束下下模函数最大值问题的近似算法及性能保证

声明

摘要

1 绪论

1．1 组合优化问题实例

1．2 优化问题定义

1．3 组合优化定义

1．4 研究背景

1．5 本文任务

2 算法及其问题复杂性分类

2．1 算法概述

2．1．1 精确算法和近似算法

2．1．2 现代优化算法

2．1．3 全局最优与局部最优

2．2 计算复杂性

2．2．1 计算复杂性概述

2．2．2 算法的时间复杂性

2．2．3 算法的空间复杂性

2．3 问题复杂性分类

2．3．1 多项式时间算法和指数时间算法

2．3．2 判定问题和优化问题

2．3．3 P类和NP类问题

2．3．4 NP完全问题和NP难题

2．4 组合优化问题的可近似性

3 近似算法及性能保证

3．1 近似算法概述

3．2 贪婪算法介绍

3．3 算法性能保证

4 下模函数及其基本性质

4．1 下模函数的基本概念

4．2 下模函数基本性质

4．3 本章小结

5 求解d-Knapsack Problem的一种贪婪算法及其性能保证

5．1 d-维背包约束下模函数问题描述及拓展

5．1．1 d-维背包数学模型

5．1．2 上述问题的拓展

5．2 相关引理及其证明

5．3 算法及其分析

5．3．1 基本思想

5．3．2 具体算法

5．3．3 算法的时间复杂性

5．3．4 算法的性能保证

结论

致谢

参考文献

攻读学位期间的研究成果