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

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 of solving the instances generated by many CSP models will happen the easy-hard-easy phase transition with the change of control parameters. but tractability range and intractability range can not be exactly clarified according to different algorithms until now. On the other hand, the tractable subclasses can be found by restricting the structure of constraint hypergraph and constraint language. In this program we study the tractability of constraint satisfaction problems, including the structural parameters of random CSP models, the hybrid tractability of constraint satisfaction problems and the corresponding algorithmic analysis.Our aim is to identify new tractable classes and to provide more efficient algorithms according to the tractable properties.

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

约束满足问题的复杂性分类是人工智能和计算机科学关注的热点。在一般情况下约束满足问题是NP难的，约束语言和约束结构的限制使一些约束满足问题能在多项式时间内求解。对约束满足问题易解性的研究有助于根据问题的特点设计高效的求解算法。本项目利用相变理论、约束图的结构参数和微结构图的相关性质研究约束满足问题的易解性。一是以随机约束满足问题模型d-k-CSP为平台，利用统计物理的有限规模尺度法研究了随机约束满足问题模型的相变现象，利用一阶矩和二阶矩法研究Freuder宽度等结构参数随模型控制参数的变化情况，划分了d-k-CSP模型的易解区域和难解区域。二是利用d-k-CSP模型给出了产生可满足性难解实例的两种方法，研究结果表明：强迫有解实例和非强迫有解实例的求解难度相当，但产生强迫有解实例的方法更简单有效，为测试局部搜索算法提供了可满足性难解实例；三是以BTP混合易解类为基础，通过约束满足问题的微结构图研究了ETP、k-BTP等混合易解类与局部相容性、值合并和变量消除的联系和相关性质；四是对约束满足问题的约束图进行树分解，基于约束图的平均度提出了新的树分解启发式算法。本项目的研究具有重要的理论和实际应用价值。