多值传播的相容性技术

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

Consistency Technique of Multi-value Propagation

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.