Knapsacks约束的弧相容改进算法

• 作者: 付兴宇 李占山 黄蔚
• 来源期刊: 吉林大学学报（理学版）
• 学科: 工学
• 关键词: 约束满足问题 弧相容 Knapsacks约束
• 年，卷（期）: 2017,（1）
• 所属期刊栏目: 计算机科学
• 页码范围: 95-102
• 页数: 8页
• 分类号: TP18
• 字数: 6062字
• 语种: 中文
• DOI: 10.13413/j.cnki.jdxblxb.2017.01.17

摘要

通过修改背包约束弧相容算法的数据结构,将点阵图改为有向图,解决了原背包约束弧相容算法中存在冗余计算和无效操作的问题,加快了算法对问题的求解效率.对比实验结果表明:在面对同一类问题时,因为数据结构更复杂,改进算法的初始化时间虽增加,但求解时间提高了20%~50%;在面对求解难度较高的问题时,改进算法能更好地缩减求解问题的时间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李占山	吉林大学计算机科学与技术学院	43	234	7.0	13.0
5	黄蔚	吉林大学计算机科学与技术学院	5	19	2.0	4.0
6	付兴宇	吉林大学软件学院	1	0	0.0	0.0