基于聚类分析的背包问题求解方法研究及其应用

摘要

背包问题是组合优化学科中一个经典而著名的问题，它的研究价值不言而喻，吸引了众多专家学者从各个角度开展对其的研究工作，各种算法设计思想也应运而生。由于背包问题的NP完全性，如何在算法的时间效率和求解精度上取得有效的平衡，成为背包问题算法设计主要的考虑因素。数据挖掘是近几年信息领域发展最快的技术之一。由于数据挖掘具有强大的发现有用知识的功能，可以利用它来发现背包问题解的相似的状态空间，然后进行约减，从而克服背包问题的NP困难性。 本文研究了背包问题的背景、国内外研究现状和发展趋势，分析了背包问题的性质、各种形式的数学模型和算法设计策略。在完成以上的基础工作后，提出自己的理论创新，构建了基于聚类分析的背包问题求解模型，并将其应用于求解0/1背包问题、子集和问题和多维背包问题。在实验部分，评估了模型的性能，发现模型具有良好的性能和稳定的近似比，并且在时间效率和求解精度两者之间能够找到一个比较有效的平衡点。本文的创新点如下： (1)在掌握数据挖掘核心技术和理念的基础上，根据对背包问题特性的分析，将经典的背包问题和新兴的数据挖掘技术有机地结合起来，在背包问题节点扩展的过程中引入集中性和多样性策略，提出了一个基于聚类分析的背包问题求解模型； (2)基于聚类分析的背包问题求解模型具有良好的可扩展性，它可以根据不同的求解实例采用适合情况的模块。在减少背包问题解的状态空间的过程中，模型可以实现无监督自动学习，去掉比较相似的状态空间，为状态空间的扩展创造有利的条件；通过二分法的使用，进一步优化了模型的性能； (3)根据基于聚类分析的背包问题求解模型，实现了0/1背包问题、子集和问题和多维背包问题的算法研究。

目录

文摘

英文文摘

声明

第一章绪论

1.1 选题背景及意义

1.2 背包问题的研究现状及发展趋势

1.3 背包问题研究中存在的问题

1.4 论文的主要内容和创新点

第二章背包问题的综述

2.1 背包问题各种形式的数学模型

2.2 背包问题的性质

2.2.1 难解性

2.2.2 可分性

2.2.3 内核性

2.3 背包问题的算法设计策略

2.3.1 精确算法

2.3.2 近似算法

2.4 数据挖掘在背包问题中的应用

2.4.1 背包问题现有的求解方法

2.4.2 数据挖掘与聚类分析

2.4.3 相关的分类统计量

2.5 小结

第三章基于聚类分析的背包问题求解模型

3.1 背包问题求解模型的原理

3.1.1 近似算法的性能

3.1.2 背包问题的组合可加性

3.1.3 集中性和多样性策略

3.2 背包问题求解模型的描述

3.2.1 模型描述

3.2.2 模型修整模块的阐述

3.2.3 用二分法优化模型

3.3 小结

第四章背包问题的求解算法

4.1 0/1背包问题算法

4.1.1 AAKP算法描述

4.2 子集和问题算法

4.2.1 AASP算法描述

4.2.2 算法复杂度分析

4.2.3 算法性能分析

4.3 多维背包问题算法

4.3.1 AAMKP算法描述

4.3.2 算法复杂度分析

4.3.3 算法性能分析

4.4 背包问题求解模型的评估

4.4.1 背包问题的数据实例分析

4.4.2 模型性能的衡量

4.4.3 模型评估结果的有效分析

4.5 小结

第五章SMSKP系统设计及模型的应用

5.1 SMSKP系统设计

5.1.1 SMSKP系统框架

5.1.2 SMSKP系统功能

5.2 市场投资问题

5.2.1 数学模型

5.2.2 实例分析

5.3 小结

第六章总结和展望

6.1 本文工作的总结

6.2 下一步的研究工作

致 谢

参考文献

攻读硕士学位期间取得的成果