Knapsacks约束的弧相容改进算法  

Improved Arc Consistency Algorithm for Knapsacks Constraints

作　　者：黄蔚[1] 付兴宇 李占山[1,2] HUANG Wei FU Xingyu LI Zhanshan(College of Computer Science and Technology, J ilin University, Changchun 130012, China College of Software, Jilin University, Changchun 130012, China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学软件学院,长春130012

出　　处：《吉林大学学报（理学版）》2017年第1期95-102,共8页Journal of Jilin University:Science Edition

基　　金：吉林省科技发展计划项目(批准号:20140101200JC)

摘　　要：通过修改背包约束弧相容算法的数据结构,将点阵图改为有向图,解决了原背包约束弧相容算法中存在冗余计算和无效操作的问题,加快了算法对问题的求解效率.对比实验结果表明:在面对同一类问题时,因为数据结构更复杂,改进算法的初始化时间虽增加,但求解时间提高了20%~50%;在面对求解难度较高的问题时,改进算法能更好地缩减求解问题的时间.By modifying the data structure of arc consistency algorithm of Knapsacks constraints, we transformed the bitmap to a directed graph, which solved the problem of redundant computation and invalid operation in the arc consistency algorithm of the original knapsack constraint, and accelerated the algorithm to solve the problem of efficiency. Comparative experimental results show that in the face of the same kind of problem, the initialization time of the improved algorithm is increased because the data structure is more complex, but the solution time is improved by 20%--50%. The improved algorithm can reduce the time of solving the problem in the face of the high difficulty of solving the problem.

关 键 词：约束满足问题 弧相容 Knapsacks约束 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]