划分问题新拟多项式算法与背包问题新求解方法研究

摘要

划分问题（PAR）是经典NP-hard类问题,是6个基本NPC问题之一,也是典型的数问题,且具有拟多项式时间算法.该文利用一种新方法即平衡技术来解答划分问题.我们仅对所有的平衡态进行枚举来解答划分问题.为提高效率,避免重复执行某些操作,算法实施了动态规划技术,最后得出的时空复杂度为O（nD）.背包问题是经典的组合优化问题,也是基本的搜索问题.文章概述了背包家族问题,详细阐述了背包问题的特性,着重讨论了迄今为止求解背包问题的典型算法及算法涉及的典型技术.在回顾前期研究成果的基础上,主要介绍当今的研究焦点和最新的研究进展,阐述了今后应采取的新方法,即紧缩界与动态规划算法的结合.

目录

摘要

ABSTRACT

第一章前言

1.1研究意义

1.2研究历史和我们的工作

第二章解答划分问题的现有算法

2.1划分问题属于NPC

2.2现有算法

第三章解答划分问题的新算法

3.1平衡操作

3.2解答划分问题的平衡算法

3.3算法时空复杂性分析

第四章背包问题及其基本特性

4.1问题概述

4.2基本特性

第五章解答背包问题的典型算法

5.1分支定界和核算法

5.2动态规划算法

5.3紧缩上界算法

5.4背包问题算法研究新趋势

第六章背包问题的典型应用

附录1划分问题实例求解程序

附录2背包问题实例求解程序

参考文献

致谢

发表论文