约束满足问题易解性的研究

项目名称： 约束满足问题易解性的研究

项目编号： No.61402516

项目类型： 青年科学基金项目

立项/批准年度： 2014

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

项目作者： 沈静

作者单位： 中国人民解放军海军工程大学

项目金额： 25万元

中文摘要： 约束满足问题(CSP)是计算机科学和人工智能领域的一个重要问题。一般情况下，CSP是NP难的，易解类指的是能在多项式时间内求解的子类。随着控制参数的变化，许多随机CSP模型的求解难度发生从易到难再到容易的变化，目前还没有针对不同算法的易解区域和难解区域的准确划分。另一方面，对约束超图的结构和约束语言加以限制，能找到CSP中的易解子类。本项目主要研究约束满足问题的易解性判定，包括随机CSP模型的难度相变现象、各种结构参数、约束满足问题的混合易解性质和相应的算法分析。目标是给出更多的新易解子类，以及针对易解子类的性质提出有效的求解算法。

中文关键词： 约束满足问题；易解性；相变现象；结构参数；树分解

英文摘要： The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence. In general the CSP is NP-hard, and the tractable classes are constraint problems which can be solved in polynomial time. The hardness o

英文关键词： constraint satisfaction problem；tractability；phase transition；structure parameter；tree decomposition