多值传播的相容性技术

相容性技术是求解约束满足问题的重要手段. 本文针对目前已有相容性算法的单值传播特点, 提出多值传播理论, 证 明出k 次单值传播与一次多值传播的等价性, 在此基础上, 给出多值传播的弧相容定理. 将该定理与目前流行的Singleton 弧 相容技术结合, 得到多值传播算法SAC-MP, 并证明其完备性和正确性. 通过对随机问题、N 皇后、鸽巢问题及基准用例的测 试表明, 算法SAC-MP 的执行效率是已有算法SAC-SDS 和SAC-3 的2»3 倍.