一个解答划分问题的新拟多项式算法

摘要：

利用一种新方法即平衡技术来解答划分问题.证明若划分问题存在满足条件的子集,则该子集一定是平衡态.据此,仅对平衡进行枚举即可解答划分问题.若划分问题给定集合中每个元素的长度都被一个常数D界定,则实施动态规划技术且仅考虑平衡状态,解答划分问题的时间复杂度为0nD),即线性时间.该算法降低了划分问题原为(n<”2>D)的复杂度.

关键词： 划分问题 动态规划 平衡 算法复杂度

作者: 雷鹏 朱大铭 马绍汉

作者单位: 山东大学计算机科学系(济南)

会议类型: 国内会议

会议名称: 863计划智能计算机主题学术会议

会议地点: 北京

会议语种:中文

页码: 523-528

在线出版日期: 2001-02-01（万方平台首次上网日期，不代表论文的发表时间）