约束满足问题的结构特征和算法分析

项目名称： 约束满足问题的结构特征和算法分析

项目编号： No.60973033

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 刘田

作者单位： 北京大学

项目金额： 29万元

中文摘要： 在约束满足问题中要求为一组变量赋值来满足给定的一组约束条件，这类问题覆盖了计算机科学、人工智能、运筹学等很多领域的重要问题。值域可变的约束满足问题可以更好地描述实际问题，近年来逐渐引起关注，但过去在固定值域条件下取得的结论往往不能直接应用。随机约束满足问题通过一个随机过程产生随机实例，通过调整随机过程的控制参数，可以观察到实例性质的相变现象，包括从有解到无解的可满足性相变、在可满足性临界点附近算法行为的相变等，但目前还没有建立起可满足性相变与难解性之间的确切关联。本项目研究值域可变的随机约束满足性问题的结构特征和算法分析，包括结构参数的取值和解空间的结构变化、各种求解算法的相变点、在算法模型和证明系统下的指数下界、近似算法和精确算法研究等，目标是比较其与固定值域的约束满足问题的差别，刻画值域可变的随机约束满足问题的难解性，建立起相变现象与难解性之间的确切联系，为实际应用打下坚实的理论基础。

中文关键词： 约束满足；RB模型；相变现象；结构分解；算法分析

英文摘要：

英文关键词： Constraint Satisfaction；Model RB；Phase Transition；Structural Decomposition；Algorithm Analysis