约束程序是人工智能的重要研究方向,约束推理是约束程序领域中一个重要的概念,它包括在求解一个约束满足时,为找到满足所有约束的解而用到的各种技术。而约束传播即为众多的约束推理技术之一,目前已经成为约束求解的核心技术。本文的主要工作是围绕约束传播而展开的,具体包括五个方面:(1)分析了当前流行的弧相容算法各自的优势和特点,并针对随机约束满足问题对系列弧相容算法性能进行了测试;(2)使用变量论域缩减比例对弧相容传播深度进行参数化描述,提出一个约束传播程度可以控制的弧相容传播算法,研究了在不同参数下约束求解算法的效率;(3)基于对现有技术的研究,提出一种在约束网络中确立双向singleton弧相容的新算法—BiSAC-2,并给出其正确性和完备性证明及随机约束满足问题的测试结果;(4)将本地动态变量启发式策略和展望策略与并发回溯搜索相结合,提出一个新的基于约束传播的并发搜索算法;(5)将研究成果嵌入我们已有的“明月”约束求解工具中,采用随机产生的约束问题来测试各个弧相容算法及其与多种智能回溯算法相结合的混合算法,实验表明,我们所提出的算法提高了“明月”约束求解工具的性能。