论文部分内容阅读
约束满足问题广泛出现于人工智能领域。在搜索过程中维持一定程度上的约束一致性是十分必要的。为了降低这种约束一致性维护的代价，人们对约束一致性算法作了不断的改进，并加入启发式约束次序等策略，其目的是通过减少约束检测次数来降低维护代价。该文首次立足于更高点，从高层到低层分析了约束一致性维护方法，提出了动态维护策略以及其相应算法ＭＡＣ－Ｄｙｎａｍｉｃ，进一步减少约束一致性维护的代价。文中以两个典型的ＣＳＰｓ问题：斑马难题和Ｎ－皇后问题作为例子，对其进行了测试与分析。有力地证实了动态维护策略的有效性。