-
摘要: 相容性技术是求解约束满足问题的重要手段. 本文针对目前已有相容性算法的单值传播特点, 提出多值传播理论, 证明出k次单值传播与一次多值传播的等价性, 在此基础上, 给出多值传播的弧相容定理. 将该定理与目前流行的Singleton弧相容技术结合, 得到多值传播算法SAC-MP, 并证明其完备性和正确性. 通过对随机问题、N皇后、鸽巢问题及基准用例的测试表明, 算法SAC-MP的执行效率是已有算法SAC-SDS和SAC-3的2～3倍.
-
关键词:
- 约束满足问题 /
- 相容性技术 /
- 多值传播 /
- Singleton弧相容
Abstract: 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. -
点击查看大图
计量
- 文章访问数: 2000
- HTML全文浏览量: 60
- PDF下载量: 1040
- 被引次数: 0
下载:
