多值传播的相容性技术  

Consistency Technique of Multi-value Propagation

作　　者：朱兴军[1,2] 张永刚[1,2] 李莹[1,2] 张长胜[3] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [3]东北大学信息科学与技术学院,沈阳110004

出　　处：《自动化学报》2009年第10期1296-1301,共6页Acta Automatica Sinica

基　　金：国家自然科学基金(60773097);吉林省青年科研基金(20080107)资助~~

摘　　要：相容性技术是求解约束满足问题的重要手段.本文针对目前已有相容性算法的单值传播特点,提出多值传播理论,证明出k次单值传播与一次多值传播的等价性,在此基础上,给出多值传播的弧相容定理.将该定理与目前流行的Singleton弧相容技术结合,得到多值传播算法SAC-MP,并证明其完备性和正确性.通过对随机问题、N皇后、鸽巢问题及基准用例的测试表明,算法SAC-MP的执行效率是已有算法SAC-SDS和SAC-3的2～3倍.Consistency technique is an important method to solve constraint satisfaction problem （CSP） instances. Since all existing algorithms have the same feature of single propagation, we propose a multi-value propagation theory and prove that k-single propagation is equivalent to 1-multi-value propagation. Based on this, we present arc consistency （AC） theory of multi-value propagation and combine it with SAC （singleton AC） to form a new multi-value propagation algorithm SAC-MP. Besides, we also prove its soundness and completeness. In our experiments on random CSPs, N-queens problems, pigeon problems and benchmarks, the efficiency of our algorithm SAC-MP is 2 - 3 times those of the existing SAC-SDS and SAC-3 algorithms.

关 键 词：约束满足问题 相容性技术 多值传播 Singleton弧相容 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]