论文部分内容阅读
约束程序CP（Constraint Programming）作为一种可以解决组合搜索类的问题的有效方法，已经被成功地运用在很多领域，比如：规划，调度，配置，网络以及生物信息学等等。约束程序的基本思想是：首先根据问题需求声明出所有的约束，然后用一个合适的求解算法来解决它们。约束的本质是关系（Relation），而约束满足问题CSP（Constraint Satisfaction Problem）声明了哪些关系对于给定的决策变量是成立的。为了解决约束满足问题，往往结合使用推理和搜索的方法。推理技术旨在通过变量的去除或者某些相容性技术来使得一个约束网络更易于求解；搜索技术被用于遍历问题中所有变量的当前论域来寻找解。此外，在求解过程中，往往使用启发式来提高效率。由于搜索算法的框架大同小异，相容性技术和启发式就成为了影响求解CSP问题效率的关键因素。相容性技术在求解约束满足问题的过程中有着至关重要的作用：在预处理阶段，即搜索解的过程开始之前的阶段，有效地采用合理的相容性技术能够删除一些不相容的值；在搜索过程中，采用相容性技术来强化网络有助于判断搜索树的当前节点是否扩展正确。因此，各种相容性技术以及实现这些相容性的算法成为了研究的热点。常见的相容性技术有：弧相容AC（Arc Consistency）、单弧相容SAC（Singleton Arc Consistency）、路径相容PC（Path Consistency）、路径逆向相容PIC（Path Inverse Consistency）和最大受限路径相容maxRPC（max-Restricted Path Consistency）等等。在这些相容性中，弧相容AC由于其轻便性和有效性，得到了最多的青睐，而将弧相容技术和搜索算法结合的MAC算法，成为了求解的最有效的手段。在使用搜索算法来求解一个约束满足问题时，需要使用启发式来帮助做一些决定，比如：选取哪一个值进行赋值，或者，该给某个变量赋何值等等。这些启发式被称为变量选择启发式和值选择启发式。已有的实验表明，变量和值的选择会对解决一个问题的效率有着非常关键的作用。如今，随着相关研究的发展，动态的变量启发式得到了最多的重视。常见的变量启发式有： dom， dom+deg， dom/deg， dom/wdeg等等。其中，dom/wdeg是当前最先进的启发式，它能够在不同类别的问题上有着较好的性能。本文主要从相容性技术和启发式入手，对求解CSP问题的技术做出相关的研究工作，具体如下：（1）提出一种新的单相容：单强边界相容SSBC （Singleton Strong BoundConsistency）。SSBC的删值能力介于SAC和AC之间，它的轻量版本LSSBC（Light SSBC）实现了在计算开销和删值能力间的较好的均衡，因而适用于求解中使用。实验证明，使用LSSBC作为推理技术的求解算法能够在很多问题上比MAC更为高效。（2）对一类非常重要的相容性maxRPC做了效率上的提升。本文提出两个新的粗粒度的算法maxRPCbit和maxRPCbit+rm，并在实验中将这两个算法和国际现有的最高效的算法进行比较。实验结果表明，新的算法比所有现有的maxRPC都更为高效。（3）以AC和maxRPC为例提出了一个可行的混合使用不同的相容性的机制：PmaxRPC。PmaxRPC保证了那些论域被清空的概率更大的变量被用较强的相容性检查的概率也更大。实验证明，在求解过程中使用了PmaxRPC的求解算法比单独使用AC或者lmaxRPC的求解算法高效很多。（4）指出当前最先进的启发式dom/wdeg的一个缺陷，并且给出了一个新的启发式dom/(wdeg/exist_ratio)。实验证明，dom/(wdeg/exist_ratio)在大部分问题上都比dom/wdeg更为高效。