Knapsacks约束的弧相容改进算法

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

Improved Arc Consistency Algorithm for Knapsacks Constraints

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 showthat 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.