Consistency Technique of Multi-value Propagation
Xingjun Zhu, Yonggang Zhang, Ying Li, Changsheng Zhang · Acta Automatica Sinica · 2009
摘要: 相容性技术是求解约束满足问题的重要手段. 本文针对目前已有相容性算法的单值传播特点, 提出多值传播理论, 证明出k次单值传播与一次多值传播的等价性, 在此基础上, 给出多值传播的弧相容定理. 将该定理与目前流行的Singleton弧相容技术结合, 得到多值传播算法SAC-MP, 并证明其完备性和正确性. 通过对随机问题、N皇后、鸽巢问题及基准用例的测试表明, 算法SAC-MP的执行效率是已有算法SAC-SDS和SAC-3的2～3倍. 关键词: 约束满足问题 / 相容性技术 / 多值传播 / Singleton弧相容