弧一致性符号ADD算法及在CSP求解中的应用

约束满足问题(CSP)是人工智能领域中一个重要的研究课题,弧一致性(AC)技术是提高约束满足问题求解效率的一种有效技术。对传统弧一致性技术进行了改进,给出了弧一致性的符号代数决策图(ADD)算法并将其应用于CSP求解。传统弧一致性技术在压缩问题的搜索空间时,一次只能处理一条约束上的一个值对;而借助ADD技术来压缩问题搜索空间,可以一次处理多条约束。算法首先通过01编码将CSP问题描述成伪布尔函数,并由ADD进行表示。然后基于传统弧一致性技术的算法思想,利用ADD的交、并和提取操作来实现约束传播和变量域过滤。最后将弧一致性的符号ADD算法嵌入到BT搜索算法中来实现对CSP的求解。对标准库中的测试用例以及随机生成的测试用例进行了实验仿真,结果表明,该算法求解CSP的时间既优于带弧一致性维护的回跳算法MAC3+BJ和MAC2001+BJ,也优于采用传统数据结构进行预处理的CSP求解算法BT+MPAC和BT+MPAC*。     

加权约束满足问题的改进RDS符号代数决策图求解算法*

加权约束满足问题(WCSP)是一类约束最优化问题.文中基于RDS思想,从减少RDS分解的子问题个数及提高各个子问题的求解效率入手,提出WCSP的改进RDS符号代数决策图(ADD)求解算法.通过改进最多约束变量的变量选择法,引入RDS变量引导原问题的子问题分解,进而减少RDS中分解的子问题个数.利用变量的后向度,进一步改进子问题的分解方法.为提高各个子问题的求解效率,利用桶消元算法并结合ADD操作消去子问题中的非RDS变量,进而减少子问题中的变量个数,提高深度优先分支界定法的下界.在大量随机生成的测试用例上的实验证明文中算法的优越性.     

网络最大流问题求解的符号ADD增广路径算法

本文通过对网络及网络最大流问题的符号代数判定图（ADD）描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法.与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善.实验结果表明,本文算法是切实有效的,且可处理更大规模的问题.     

基于关联约束非二元弧一致性的约束满足问题求解

弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(NCSP).本文提出了处理NCSP的关联约束非二元弧一致性算法.通过随机NCSP生成器产生问题实例,分别采用关联约束非二元弧一致性算法和非二元弧一致性算法进行预处理,并对预处理后的问题实例应用回溯算法进行求解.对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能,仿真实验结果表明关联约束非二元弧一致性算法可以有效地剔除冗余的约束元组和变量域值,使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性.     

约束满足问题求解的符号OBDD桶消元算法

桶消元算法是求解约束满足问题的一种典型推理方法.针对桶消元算法面临的状态空间爆炸问题,将有序二叉决策图( OBDD)技术与该算法结合起来,给出了约束满足问题的一种求解算法.通过对约束满足问题中变量和域值的编码,将CSP问题转化为命题可满足性问题,给出了约束满足问题的OBDD表示方法;基于桶消元的算法思想,在约束满足问题...     

一个基于最小冲突修补的动态约束满足求解算法

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu_LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu_LC算法在求解效率和解的质量上都明显优于LC算法.     

基于约束满足搜索算法的测试用例生成策略

针对约束系统中非线性谓词函数、指针、数组等复杂运算的求解问题,运用约束满足搜索算法,通过减少约束方程组中参数变量的个数,逐步缩小参数变量的取值范围,提出基于符号法求解约束的改进算法。对含有非线性谓词、数组的程序实例进行实验,结果表明改进算法能有效生成测试用例。     

一种基于环切割的约束满足问题求解算法

该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search,然后将环切割思想嵌入到目前最流行的MAC3rm算法中,给出一种新算法CCS.CCS将原同溯搜索过程分为两部分:第1部分通过回溯搜索求解环切割集中变量,将原问题化简成一个满足弧相容的无环问题；第2部分通过无回溯的Tree_Search算法求解化简后的...     

无圈与或图搜索的符号OBDD算法研究

与或图搜索是人工智能领域一项重要的问题求解技术.基于传统数据结构的与或图表示技术极大地限制了与或图搜索算法可求解问题的规模.在无圈与或图符号OBDD表示的基础上,给出了一种求解无圈与或图最小代价解图的符号搜索算法.实验结果表明,与 AO*算法相比,该算法可处理问题的规模有较大的提高.     

一种基于预处理技术的约束满足问题求解算法

相容性技术作为约束满足问题的一种有效求解技术,不论是在求解前的预处理过程中,还是在搜索过程中,都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取,提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT MPAC和BT MPAC*,给出了其正确性证明,通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明:对于不同类别的用例,新算法的执行效率是弧相容维护算法的2~50倍.     

Redundant modeling in permutation weighted constraint satisfaction problems

In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same from redundant modeling in weighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on a popular and special class of problems, namely, permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP using generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints and relying on the standard node consistency (NC*) and arc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations, we suggest two approaches to handle the combined WCSP models. In our first approach, we propose m\text -NC_{\text c}^*m\text {-NC}_{\text c}^* and m\text -AC_{\text c}^*m\text {-AC}_{\text c}^* and their associated algorithms for effectively enforcing node and arc consistencies in a combined model with m sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated with any local consistency Φ for single models and applied to a combined model with m sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments. Prototype implementations of our proposed algorithms confirm that applying 2\text -NC_{\text c}^*,  2\text -AC_{\text c}^*2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*, and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and EDAC* algorithms on single models of hard benchmark problems.     

Arc and path consistency revisited

Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms [5]. We present here new algorithms for arc and path consistency and show that the arc consistency algorithm is optimal in time complexity and of the same-order space complexity as the earlier algorithms. A refined solution for the path consistency problem is proposed. However, the space complexity of the path consistency algorithm makes it practicable only for small problems. These algorithms are the result of the synthesis techniques used in alice (a general constraint satisfaction system) and local consistency methods [3].     

一种高效的FDE并行传播算法

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题...     

The complexity of some polynomial network consistency algorithms for constraint satisfaction problems

Constraint satisfaction problems play a central role in artificial intelligence. A class of network consistency algorithms for eliminating local inconsistencies in such problems has previously been described. We analyze the time complexity of several node, arc and path consistency algorithms and prove that arc consistency is achievable in time linear in the number of binary constraints. The Waltz filtering algorithm is a special case of the arc consistency algorithm. In the edge labelling computational vision application the constraint graph is planar and so the time complexity is linear in the number of variables.     

A polynomial relational class of binary CSP

Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism).     

最大受限路径相容约束传播算法的研究进展

约束传播技术对于约束满足问题的求解性能至关重要。约束传播技术在一个预处理过程中能彻底地移除一些局部不相容值,或者在搜索期间高效地剪枝搜索树。最大受限路径相容算法(max Restricted Path Consistency,maxRPC)是最近提出的一种强相容性约束传播算法,它能够删除更多不相容值,在解决复杂问题中取得了很好的效果。文中对弧相容算法AC和最大受限路径相容算法maxRPC的相关算法AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3等及其相关变体分别进行介绍和比较。在Mistral求解器上的实验测试结果验证了各种算法的性能。     

A unified framework for consistency check

Constraint Satisfaction Problem (CSP) involves finding values for variables to satisfy a set of constraints. Consistency check is the key technique in solving this class of problems. Past research has developed many algorithms for such a purpose, e.g., node consistency, are consistency, generalized node and arc consistency, specific methods for checking specific constraints, etc. In this article, an attempt is made to unify these algorithms into a common framework. This framework consists of two parts. the first part is a generic consistency check algorithm, which allows and encourages each individual constraint to be checked by its specific consistency methods. Such an approach provides a direct way of practical implementation of the CSP model for real problem-solving. the second part is a general schema for describing the handling of each type of constraint. the schema characterizes various issues of constraint handling in constraint satisfaction, and provides a common language for expressing, discussing, and exchanging constraint handling techniques. © 1995 John Wiley & Sons, Inc.