随机约束满足问题相变研究综述

随机约束满足问题是经典的NP完全问题,在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象,近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手,从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。     

基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP）,提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。     

启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

一种基于变量熵求解约束满足问题的置信传播算法

在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.     

几何设计约束的表示与满足问题研究

对于智能ＣＡＤ系统来说，具有解决几何设计约束的功能是重要的。本文提出了一种面向对象的几何设计约束表示方法，它可以通过两种方式来表达。文中给出了一个约束传播算法，用于解决约束满足问题。     

二元约束满足问题求解的结点开销模型

提出了在二元约束满足问题中以搜索结点个数为衡量标准的求解开销模型,该模型被应用于随机二元约束满足问题的求解开销相变分析中,并且比较了模型所导出的理论开销和实际中的搜索结点个数、约束检查次数、求解时间3种衡量标准的开销之间的相似性.在模型的基础上，探讨了求解启发式减少求解开销的作用，给出了一个新的变量选择启发式.     

约束满足问题求解途径之比较与分析

本文从逻辑，自动机理论，代数方法，连接主义框架和遗传算法的角度深入地探讨了ＣＳＰ问题的不同表示框架和求解风范，详细分析和讨论了不同表示和求解方法的特点以及它们之间的内在联系和可能的结合。     

几何约束满足问题的图重构策略

通过对图缩并算法的介绍和分析 ,以约束网络图的形式对几何约束系统中的约束关系进行映射表达 ,提出了一种基于自由度分析的图重构推理策略 ,实现了问题的最大分解 ,大大降低了问题的复杂程度和系统求解的规模 ,使得相当一部分具有高耦合性的问题最终可以用解析方法求解。     

基于约束满足问题的应急决策

针对如何快速、高效地生成应对突发事件处置方案的问题,提出一种基于约束满足问题(CSP)的应急决策方法。根据为应对突发事件而预先制定的应急预案,采用变量和约束来表示应急决策问题的对象和规则,构建应急决策模型,通过CSP的求解迅速生成满足约束规则的应急处置方案。以国家地震应急预案为例进行分析,结果证明了该方法在应急决策中的可行性。     

Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

We consider a random constraint satisfaction problem named model RB, which exhibits a sharp satisfiability phase-transition phenomenon when the control parameters pass through the critical values denoted by rcr and pcr. Using finite-size scaling analysis, we bound the width of the transition region for finite problem size n, which might be the first rigorous study on the threshold behaviors of NP-complete problems.     

Backtracking and random constraint satisfaction

The average running time used by backtracking on random constraint satisfaction problems is studied. This time is polynomial when the ratio of constraints to variables is large, and it is exponential when the ratio is small. When the number of variables goes to infinity, whether the average time is exponential or polynomial depends on the number of variables per constraint, the number of values per variable, and the probability that a random setting of variables satisfies a constraint. A method for computing the curve that separates polynomial from exponential time and several methods for approximating the curve are given. The version of backtracking studied finds all solutions to a problem, so the running time is exponential when the number of solutions per problem is exponential. For small values of the probability, the curve that separates exponential and polynomial average running time coincides with the curve that separates an exponential average number of solutions from a polynomial number. For larger probabilities the two curves diverge. Random problems similar to those that arise in understanding line drawings with shadows require a time that is mildly exponential when they are solved by simple backtracking. Slightly more sophisticated algorithms (such as constraint propagation combined with backtracking) should be able to solve these rapidly. This revised version was published online in June 2006 with corrections to the Cover Date.     

Predicting phase transitions of binary constraint satisfaction problems with constraint graph information

Constraint satisfaction is at the core of many applications, such as scheduling. The study of phase transition has benefited algorithm selection and algorithm development in constraint satisfaction. Recent research provides evidence that constraint graph topology affects where phase transitions occur in constraint satisfaction problems. In this article, a new phase transition predictor which takes constraint graph information into consideration is proposed. The new predictor allows variation in the tightness of individual constraints and node degree variation in constraint graph. Experiments were conducted to study the usefulness of the new predictor on random binary constraint satisfaction problems. Results show that the new predictor is able to produce predictions as good as the state-of-the-art predictor in general, but do considerably better in sparsely constrained problems, particularly when the node degree variation in their constraint graphs is high.     

Production management as a constraint satisfaction problem

Production management problems can be quite straightforwardly presented as constraint satisfaction problems, where values for some variables are searched for under a set of constraints. A combination of an operation and a resource is usually interpreted as the variable, and a time window is usually interpreted as the value to be searched for. This convention is challenged. A case is considered where the most appropriate interpretation treats the combination of a resource and a time window as the variable, and an operation as the value. A third possible interpretation is also briefly covered, where the combination of an operation and a time window is the variable, and the resource is the value.     

基于约束满足的测试计划方法

测试经理在制定测试计划时,往往只能依靠个人经验,缺乏理论方法的指导,面对复杂软件系统时难以全面考虑测试模块间关系及测试人员能力等复杂因素,往往使得测试效果并不令人满意.将约束规划技术引入测试领域,结合测试计划自身特点,提出了一种全新的基于约束满足的测试计划方法.方法将软件产品划分为测试模块,通过确定各模块测试过程及过程间顺序约束、资源能力约束,对测试计划问题进行了约束建模和求解.并以项目管理软件SoftPM的测试过程为例,对方法的具体应用进行了介绍.     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

Formulating the template ILP consistency problem as a constraint satisfaction problem

Inductive Logic Programming (ILP) deals with the problem of finding a hypothesis covering positive examples and excluding negative examples, where both hypotheses and examples are expressed in first-order logic. In this paper we employ constraint satisfaction techniques to model and solve a problem known as template ILP consistency, which assumes that the structure of a hypothesis is known and the task is to find unification of the contained variables. In particular, we present a constraint model with index variables accompanied by a Boolean model to strengthen inference and hence improve efficiency. The efficiency of models is demonstrated experimentally.     

On the phase transitions of random k-constraint satisfaction problems

Constraint satisfaction has received increasing attention over the years. Intense research has focused on solving all kinds of constraint satisfaction problems (CSPs). In this paper, first we propose a random CSP model, named k-CSP, that guarantees the existence of phase transitions under certain circumstances. The exact location of the phase transition is quantified and experimental results are provided to illustrate the performance of the proposed model. Second, we revise the model k-CSP to a random linear CSP by incorporating certain linear structure to constraint relations. We also prove the existence of the phase transition and exhibit its exact location for this random linear CSP model.     

Spines of random constraint satisfaction problems: definition and connection with computational complexity

We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a class of random constraint satisfaction problems, a limited connection between the two phenomena indeed exists. Specifically, we extend the definition of the spine order parameter of Bollobás et al. [10] to random constraint satisfaction problems, rigorously showing that for such problems a discontinuity of the spine is associated with a 2^Ω(n) resolution complexity (and thus a 2^Ω(n) complexity of DPLL algorithms) on random instances. The two phenomena have a common underlying cause: the emergence of “large” (linear size) minimally unsatisfiable subformulas of a random formula at the satisfiability phase transition.We present several further results that add weight to the intuition that random constraint satisfaction problems with a sharp threshold and a continuous spine are “qualitatively similar to random 2-SAT”. Finally, we argue that it is the spine rather than the backbone parameter whose continuity has implications for the decision complexity of combinatorial problems, and we provide experimental evidence that the two parameters can behave in a different manner.AMS subject classification 68Q25, 82B27