基于空腔方法的随机约束满足问题相变复杂性与高效算法研究

项目名称： 基于空腔方法的随机约束满足问题相变复杂性与高效算法研究

项目编号： No.11301339

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

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 赵春艳

作者单位： 上海理工大学

项目金额： 22万元

中文摘要： 随机约束满足问题的相变现象及其形成机制是探索NP-完全问题难解本质的关键之一。基于目前在具有固定取值域的随机约束满足问题上已经取得的理论研究基础，本项目针对一个典型的具有增长取值域的随机约束满足问题，引入随机无序系统中自旋玻璃理论的空腔方法，结合组合数学与概率方法等数学工具，对问题解空间的各种结构性相变现象及其复杂性成因进行研究，并进一步利用解空间的统计特征和分布规律，开发能够处理变量取值域可变的随机约束满足问题的高效、可靠的算法及其实现机制，从而建立起求解此类随机约束满足问题的基本理论框架。此外，本项目将分析具有增长取值域的随机约束满足问题的相变机制与具有固定取值域的随机约束满足问题相比所表现出的新特性，并阐述相变复杂性与求解算法之间的内在联系。这些研究结果将能更好地促进对NP-完全问题难解性的全面理解，同时对计算应用中可以归约为具有可变取值域的随机约束满足问题的求解具有一定的指导意义。

中文关键词： 随机约束满足问题；相变现象；复杂性分析；模拟退火；空腔方法

英文摘要： The phenomenon and mechanics of phase transitions in random constraint satisfaction problems is the key to explore the nature of hardness in NP-complete problems. Previous researches are focused on random constraint satisfaction problems with fixed domains in which the domain size of each variable is independent of the problem size. In this project, we study a representative random constraint satisfaction problem with growing domains. Using the cavity method in the field of spin glass from statistical physics in disordered systems and rigorous mathematical tools, we investigate the various structural phase transitions in the solution space of the problems, and we analysis the complexity of these transitions. By identifying critical behaviors in the evolution of solution space, we develop efficient heuristic message-passing algorithms to find solutions of random constraint satisfaction problems with growing domains. Therefore, we can establish the fundamental theory frame for solving these random constraint satisfaction problems with growing domains. These studies can precisely describe the phase diagram of the set of solutions of the random constraint satisfaction problems with growing domains as the control parameter increases. Moreover, we performed the algorithms to verify the locations of the transition thre

英文关键词： Random constraint satisfaction problems；Phase transitions；Complexity analysis；Simulated annealing；Cavity method