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

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

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

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

参数化弧相容约束传播

为进一步提高约束满足问题求解算法的效率，对约束传播过程进行了分析，并使用变量论域缩减比例对弧相容传播深度进行参数化描述，同时提出了一个约束传播程度可以控制的弧相容传播算法，研究了在不同参数下约束求解算法的效率。该算法在“明月1．0”架构下实现。实验结果表明，约束传播程度是影响算法求解效率的一个重要因素，通过调整控制参数可以使算法效率提高3～4倍。

基于GPU的约束网络模型和并行弧相容算法

弧相容算法是约束满足问题的基本压缩求解空间算法之一,很多优秀的高级算法都以高性能的弧相容算法作为核心.近年来,以GPU为计算工具加速并行计算被用来尝试解决许多问题.基于GPU和基本的并行算法,提出一种适合GPU运算的约束网络表示模型N-E,给出其生成算法BuildNE.结合细粒度的弧相容算法——AC4,基于N-E模型提出AC4的并行化算法AC4^(GPU)与改进算法AC4^(GPU)+,使弧相容算法得以扩展到GPU上执行.实验结果验证了该算法的可行性,与AC4算法的比较,其在一些规模较小的问题上取得了10%~50%的加速,在一些规模较大的问题上则加速1~2个数量级.为今后进一步在GPU上以并行形式解决其他约束满足问题提供了一种核心算法方案.

约束满足问题并行弧相容算法

本文给出了约束满足问题网络弧相容的两个并行算法ＰＡＣ－１和ＰＡＣ－２。

贪婪的Singleton弧相容算法的优化

通过记录搜索过程中的有用信息避免了一些无用的约束传播,从而对预处理阶段的Singleton弧相容算法进行了改进,提出了改进的Singleton弧相容算法———SAC3-Revised,它能够减少约束传播的次数和时间。实验结果表明:对于随机问题,当p2在一定范围内取值时,算法效率可提高两倍以上;对于标准测试用例,算法SAC3_Revised的效率也优于SAC-3。

维持弧的唯一性优化粗粒度弧相容算法

针对人工智能领域中广泛应用的约束满足问题,本文分析了约束满足问题的粗粒度维持弧相容求解算法在弧相卷(arc corsistency,AC)执行过程中对于弧存在冗余的放回操作,并证明了这类放回是冗余的。同时提出一种改进方法 AC_AO,避免这类冗余的弧放回操作,从而保证了弧的唯一性。改进后框架可用于改进所有的粗粒度弧相容算法。实验结果表明,经过AC_AO改进后的算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间。这将大大减少修正函数的调用次数,从而提高AC的执行效率,应用在维持弧相容算法求解的过程中提高效率是非常有意义的。

Knapsacks约束的弧相容改进算法

通过修改背包约束弧相容算法的数据结构,将点阵图改为有向图,解决了原背包约束弧相容算法中存在冗余计算和无效操作的问题,加快了算法对问题的求解效率.对比实验结果表明:在面对同一类问题时,因为数据结构更复杂,改进算法的初始化时间虽增加,但求解时间提高了20%~50%;在面对求解难度较高的问题时,改进算法能更好地缩减求解问题的时间.

图分割在Singleton弧相容算法中的应用

基于原有SAC-MP算法,提出一种将图分割技术应用到SAC-MP算法中的一种新算法,该算法在执行时能充分利用图分割技术确定适当的k值,避免了由于k值的不确定带来的冗余操作和盲目性.实验结果表明,该算法在求解约束满足问题时效率较高.

一种改进的双向singleton弧相容算法

在现有相容性算法研究的基础上,提出了一种在约束网络中确立双向singleton弧相容的新算法——BiSAC-2,并给出了其正确性和完备性证明。该算法与原有算法BiSAC-1具有相同的化简问题能力,但BiSAC-2能够减少弧相容维护的次数,避免冗余约束传播过程的产生,从而可以快速地到达稳定点,进而实现高效的目的。对随机约束满足问题的测试结果表明,算法BiSAC-2比原始算法BiSAC-1具有更明显的性能优势。

弧相容算法性能比较

为了化简约束满足问题的规模、有效地处理大规模难解问题,从求解算法的角度研究弧相容技术。分析讨论了8种弧相容算法各自的优势和特点。在“明月”约束求解平台上针对随机约束满足问题,对该系列弧相容算法的性能进行了测试。实验结果表明,无论是在搜索之前还是搜索过程中,AC-2001(AC-3.1)都比其他算法表现出更优异的性能。

多值传播的相容性技术

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

基于论域折半的最大限定路径相容算法

针对绝大多数不可满足问题的特点,提出了一种将弧相容算法与最大限定路径相容算法相结合的相容性算法——基于论域折半的最大限定路径相容的算法。该算法充分利用了弧相容计算开销小和最大限定相容删值能力强的优点,可以减少在求解不可满足问题中生成的结点数,进而提高求解效率。实验结果表明,本文算法在处理不可满足问题时的求解效率明显优于传统的维持弧相容算法。

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

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

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

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

求解约束满足问题的改进蚁群优化算法

为了克服传统的回溯算法在求解大型的约束满足问题时效率低,难以在合理的时间内求解这一问题。提出了基于启发式搜索的不完备性算法。结合不同算法特性,主要在蚁群优化元启发式约束求解算法的基础上提出了改进:一是在搜索之前用弧相容检查进行预处理以压缩搜索空间,二是提出了一种新的蚁群算法参数设置方案,提高算法的适应性。最后将改进后的算法应用于求解随机问题和组合优化问题。实验结果表明,改进后的算法求解效率得到大幅度提高。

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

该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search,然后将环切割思想嵌入到目前最流行的MAC3 rm算法中,给出一种新算法CCS.CCS将原回溯搜索过程分为两部分:第1部分通过回溯搜索求解环切割集中变量,将原问题化简成一个满足弧相容的无环问题;第2部分通过无回溯的Tree_Search算法求解化简后的无环问题,改进了MAC3rm算法.证明了MAC3rm算法在环切割集上求得的局部解一定可以扩展为一个全局解,并且如果原问题无解,则MAC3rm算法在环切割集上找不到局部解.实验结果显示,CCS的效率在大多数情况下高于MAC3rm.在求解随机问题相变阶段的测试用例时,CCS的效率最高可以达到MAC3rm的140倍.Benchmark中几组问题的测试结果显示,CCS在整体上效率高于MAC,最高可以达到MAC3rm的100倍以上.

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

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

基于动态值启发式的约束满足求解算法

为提高约束满足问题的求解效率,提出了一种基于动态值启发式的约束满足问题求解算法。该算法在求解过程中吸收了以往启发式算法的优点,充分利用了预处理和弧相容检查阶段的信息。不但加入了变量启发式,而且在实例化变量时,对所有值的优先级进行动态的改变,从而实现了动态值启发式。比较了静态值启发式和动态值启发式的效率,分析了该算法的优缺点。通过随机问题标准库用例测试表明,该算法比经典主流算法具有更好的效率优势。

稀疏二元约束满足问题的环割集粒子群算法(英文)

提出了一个基于环割集的粒子群算法求解稀疏二元约束满足问题,把环割集和粒子群算法结合在一起,利用环割集减少粒子群算法中粒子的维数。用随机的稀疏二元约束满足问题进行实验,结果表明改进后的粒子群算法是有效的,迭代次数约为原算法的十分之一,运行时间比原算法运行时间少约7倍。