稳定匹配问题在1962年由诺贝尔奖获得者埃尔文·罗斯(Alvin Roth)和罗伊德·沙普利(Lloyd Shapley)提出。匹配问题是将一组对象与另外一组对象进行匹配,在匹配的过程中受到偏好序列和容量的约束。偏好序列是某个对象对其他对象的偏好排序,对象的偏好序列可能是完全的(对所有对象进行偏好排序),也可能是非完全的(仅对部分对象进行偏好排序)。容量表示对象至多可以匹配其他对象的数目。稳定性是评价匹配好坏的重要标准之一,当一个匹配满足稳定性的条件时,就认为该匹配是稳定的匹配,否则为不稳定的匹配。匹配问题在实际生活中有许多应用,如美国医院/医生匹配问题、波士顿小学招生问题、纽约高中招生问题和新英格兰肾移植交换问题。稳定婚姻问题(Stable Marriage,SM)、医院/医生问题(Hospitals/Residents,HR)和稳定室友问题(Stable Roommates problem,SR)被称为三大经典稳定匹配问题。本文主要研究的内容是基于完全偏好序列和非完全偏好序列的稳定婚姻问题和稳定室友问题的约束建模和求解。约束满足问题(Constraint Satisfaction Problems,CSPs)是人工智能领域一个重要的研究方向,相关技术被广泛应用到配置、调度及组合问题求解等领域。我们可以将一个稳定婚姻问题或者稳定室友问题定义为约束满足问题,将求解稳定匹配问题转换为求解约束满足问题。目前,已经存在很多成熟的求解约束满足问题的求解器,如Ilog Solver、Gecode、Choco、Mistral等。其中Choco求解器是一个求解约束满足问题和优化问题的java库。它提供了一套比较完整的建模语言,能够简单、快速地对问题进行建模和求解。因为Choco求解器易于使用和扩展的特点,被广泛的应用于教学和研究中。本文的主要工作如下:(1)本文主要对稳定匹配问题进行研究。首先,介绍了稳定婚姻问题;然后,介绍了稳定婚姻问题的几种常见变型,并给出了求解这类问题的一般解法;最后介绍了医院/医生问题和求解的算法。(2)深入分析和研究Choco求解器和约束程序。首先,介绍了Choco求解器的结构和主要用到的jar包;其次,介绍了如何使用Choco求解器进行简单的建模和求解;再次,介绍了约束满足问题和约束程序;最后,描述了约束传播的机制。(3)主要对求解稳定匹配问题的约束模型进行了改进。首先描述了CP模型的特点;其次分析了CP约束模型存在的缺点;再次,针对原模型没有对初始偏好序列进行预处理,和执行弧相容算法后偏好序列中仍然存在大量冗余的数据的缺点提出对应的改进算法;最后将改进后的模型和原模型进行实验对比并给出结论实验表明,我们的算法改进具有明显的效果。