摘要
通过修改背包约束弧相容算法的数据结构,将点阵图改为有向图,解决了原背包约束弧相容算法中存在冗余计算和无效操作的问题,加快了算法对问题的求解效率.对比实验结果表明:在面对同一类问题时,因为数据结构更复杂,改进算法的初始化时间虽增加,但求解时间提高了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.
作者
黄蔚
付兴宇
李占山
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)
出处
《吉林大学学报（理学版）》
CAS
CSCD
北大核心
2017年第1期95-102,共8页
Journal of Jilin University:Science Edition
基金
吉林省科技发展计划项目(批准号:20140101200JC)
