基于AC-4的动态值启发式约束满足问题求解算法

AC-4 based dynamic value ordering heuristic algorithm for solving constraint satisfaction problems

通过对弧相容算法AC-4的研究,提出了基于AC-4的动态值启发式约束满足问题求解算法MAC-DMSV。算法充分利用AC-4在初始化阶段建立的计数器信息,选择计数最大者为优先实例化的值。将此值启发式加入MAC算法之中,在MAC的相容性检查时,更新计数器的值,实现了动态值启发式。实验结果表明,MAC-DMSV算法比MAC和BT+MPAC算法具有更高的求解效率。

By studying the arc consistency algorithm,AC-4,a dynamic value ordering heuristic algorithm,MAC-DMSV,is proposed for solving constraint satisfaction problems based on AC-4.This algorithm uses the counter information created in the initialization of the AC-4 algorithm,and chooses the biggest counter value as the prior instantiation value.Then the ordering heuristic of this value is added to MAC,and the values of the counters are updated when checking the consistency.So the dynamic value ordering heuristic can be realized.The algorithm is tested by random problems and benchmark,and results show that the efficiency of MAC-DMSV is higher than that of MAC and BT＋MPAC.