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

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

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

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

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

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

概率最大受限路径相容算法

研究了可用于求解约束满足问题的最大受限路径相容算法(maxRPC).maxRPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高maxRPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(PmaxRPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:PmaxRPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,PmaxRPC效率高于maxRPC.在某些测试用例上,PmaxRPC比maxRPC和最流行的弧相容算法效率更高.     

多值传播的相容性技术

相容性技术是求解约束满足问题的重要手段. 本文针对目前已有相容性算法的单值传播特点, 提出多值传播理论, 证明出k次单值传播与一次多值传播的等价性, 在此基础上, 给出多值传播的弧相容定理. 将该定理与目前流行的Singleton弧相容技术结合, 得到多值传播算法SAC-MP, 并证明其完备性和正确性. 通过对随机问题、N皇后、鸽巢问题及基准用例的测试表明, 算法SAC-MP的执行效率是已有算法SAC-SDS和SAC-3的2～3倍.     

Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3 frame ARR改进后的算法最多可以节省80％的修正检查次数和40％的求解耗时.     

改进求解约束满足问题粗粒度弧相容算法

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.     

一种维持约束网络相容性的双向传播策略

约束满足问题是经典NP-hard问题,其基本算法是递归形式的回溯算法和弧一致性算法.将弧相容与回溯搜索结合,可以有效降低解空间大小.针对弧相容的维持问题,提出一种新的基于时序计数的传播方案,用于增量更新约束子网.将accumulateRevision和pushRevison作为双向修订的主要方法,以减少修订次数和域过滤变量的数量.实验结果表明,与经典的基于关系的方案和基于变量的传播方案相比,该方案的整体求解速度明显提高,且具有较少的修订时间.     

优化求解约束满足问题的MDDc和STR3算法

广义弧相容是求解约束满足问题应用最广泛的相容性,MDDc、STR2和STR3是表约束上维持广义弧相容应用较多的算法,其中MDDc基于对约束压缩表示的思想,将表约束表示成多元决策图,对各个元组之间存在较多交叠部分的约束具有很好的压缩效果;STR3同STR2一样基于动态维持有效元组的思想,当元组集规模缩减较慢时STR3维持广义弧相容的效率高于STR2.通过深入分析发现MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.本文分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR,对于同一操作,可以根据回溯搜索不同阶段的局势自适应地选择代价最小的实现方法,得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比原算法速度提升显著,其中AdaptiveSTR在一些问题上相比STR3提速三倍以上.     

最先失败原则的约束传播算法

约束满足问题是人工智能研究领域的重要问题.而弧相容算法是求解约束满足问题的重要工具.在弧相容算法中应用启发式规则已经证明是一种很有效的方式.本文提出一个基于最先失败原则的约束传播算法,该算法在搜索过程中更早地发现含有空域的变量并提前进行回溯,从而提高问题求解效率.同时,在"明月1.0"架构下实现了该算法,实验结果表明使用最先失败原则的弧相容算法要比原来的算法效率上提高了约40%.     

Parallel consistent labeling algorithms

Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms.⁽¹⁾ Mohr and Henderson have given new algorithms, AC-4 and PC-3, for arc and path consistency, respectively, and have shown that the arc consistency algorithm is optimal in time complexity and of the same order space complexity as the earlier algorithms.⁽²⁾ In this paper, we give parallel algorithms for solving node and arc consistency. We show that any parallel algorithm for enforcing are consistency in the worst case must have O(na) sequential steps, wheren is number of nodes, anda is the number of labels per node. We give several parallel algorithms to do arc consistency. It is also shown that they all have optimal time complexity. The results of running the parallel algorithms on a BBN Butterfly multiprocessor are also presented.This work was partially supported by NSF Grants MCS-8221750, DCR-8506393, and DMC-8502115.     

Theoretical analysis of singleton arc consistency and its extensions

Singleton arc consistency (SAC) is a consistency property that is simple to specify and is stronger than arc consistency. Algorithms have already been proposed to enforce SAC, but they have a high time complexity. In this paper, we give a lower bound to the worst-case time complexity of enforcing SAC on binary constraints. We discuss two interesting features of SAC. The first feature leads us to propose an algorithm for SAC that has optimal time complexity when restricted to binary constraints. The second feature leads us to extend SAC to a stronger level of local consistency that we call Bidirectional SAC (BiSAC). We also show the relationship between SAC and the propagation of disjunctive constraints.     

基于动态度的回溯算法求解大值域约束满足问题

针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域与动态度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容（MAC）技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明：在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。     

负表约束的简单表缩减广泛弧相容算法

广泛弧相容算法（generalized arc consistency,简称GAC）,是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势.     

Parallel path consistency

Filtering algorithms are well accepted as a means of speeding up the solution of the consistent labeling problem (CLP). Despite the fact that path consistency does a better job of filtering than arc consistency, AC is still the preferred technique because it has a much lower time complexity. We are implementing parallel path consistency algorithms on multiprocessors and comparing their performance to the best sequential and parallel arc consistency algorithms.^(1,2) (See also work by Kerethoet al. ⁽³⁾ and Kasif⁽⁴⁾) Preliminary work has shown linear performance increases for parallelized path consistency and also shown that in many cases performance is significantly better than the theoretical worst case. These two results lead us to believe that parallel path consistency may be a superior filtering technique. Finally, we have implemented path consistency as an outer product computation and have obtained good results (e.g., linear speedup on a 64K-node Connection Machine 2).     

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

On the arc consistency problem

In this paper,we propose a new arc consistency algorithm,AC-8,which requires less computation time and space than AC-6 and AC-7.The main idea of the optimization is the divide-and-conquer strategy,thereby decomposing an arc consistency problem into a series of smaller ones and trying to solve them in sequence. In this way,not only the space complexity but also the time complexity can be reduced.The reason for this is that due to the ahead of time performed inconsistency propagation(in the semse that some of them are executed before the entire inconsistency checking has been finished),each constraint subnetwork will be searched with a gradually shrunk domain.In addition,the technique of AC-6 can be integrated into our algorithm,leading to a further decrease in computational complexity.     

Approximate Boyer-Moore String Matching for Small Alphabets

Recently a new variation of approximate Boyer-Moore string matching was presented for the k-mismatch problem. The variation, called FAAST, is specifically tuned for small alphabets. We further improve this algorithm gaining speedups in both preprocessing and searching. We also present three variations of the algorithm for the k-difference problem. We show that the searching time of the algorithms is average-optimal and the preprocessing also has a lower time complexity than FAAST. Our experiments show that our algorithm for the k-mismatch problem is about 30% faster than FAAST and the new algorithms compare well against other state-of-the-art algorithms for approximate string matching.