基于相容优化的并行约束求解方法

摘要

本发明涉及一种基于相容优化的并行约束求解方法，含有下列步骤：1：初始化任务队列；2：如果任务队列中没有搜索向量，则结束；如果有搜索向量，则选择一个作为当前工作任务；3：从所有未赋值的约束变元中选择要赋值的约束变元；4：对要赋值的约束变元的所有可能取值进行赋值，形成新的搜索向量放入任务队列中；5：对新的搜索向量进行并行相容检查；6：如果相容检查发现冲突，则进行回溯分析，重建搜索向量，更新任务队列，执行2；如果相容检查没有发现冲突，且所有约束变元已经赋值，则说明找到了可满足的求解，结束；如果不是所有约束变元已经赋值，则将新构建的搜索向量加入任务队列，执行2；本发明实现了约束求解的并行高效执行。

说明书

（一）、技术领域：本发明涉及一种并行约束求解方法，特别是涉及一种基 于相容优化的并行约束求解方法。

（二）、背景技术:约束满足问题(ConstraintSatisfactionproblem,CSP)是人 工智能的中心问题之一。在计算机科学特别是人工智能领域中的很多问题，都 可表示为约束满足问题。求解这类问题一般采用回溯搜索法，一般情况下求解 比较困难，甚至是NP-hard（non-deterministicpolynomial-timehard）问题，为减 少回溯次数，提高搜索算法的执行效率，多是采用相容技术进行优化。相容技 术在解决约束满足问题中起着重要作用。一方面，在搜索之前进行相容的检查， 可以产生解的集合或极大地化简问题的规模；另一方面，在搜索过程中保持相 容，相比其它算法在付出一定的时空代价的情况下能够得到合理的问题规模的 压缩，因此仍然被认为是处理大规模难解问题的最有效的一般方法。相容算法 可以看成是求解约束满足问题回溯搜索的一种优化和预处理过程。

随着分布式硬件平台的发展，越来越多的学者希望利用更强计算能力处理 耗费时间和资源的约束求解问题，开始从事并行搜索或并行相容技术的相关研 究。搜索方法的并行通过对搜索空间的划分实现，将问题切分成若干规模较小 的子问题进行求解；相容技术的并行是对任务的切分，提升了某次搜索过程的 优化进程。由于约束求解时大多数时间用于相容检查，因此搜索和相容的并行 同样重要。

（三）、发明内容：

本发明要解决的技术问题是：克服现有技术的缺陷，提供一种基于相容优 化的并行约束求解方法，该方法实现了约束求解的并行高效执行。

本发明的技术方案：

一种基于相容优化的并行约束求解方法，含有下列步骤：

步骤1：用整个约束变元域的搜索空间初始化任务队列；

步骤2：如果任务队列中没有搜索向量，表示求解结束、问题无解，执行步 骤7；如果任务队列中有搜索向量，则从任务队列中选择一个搜索向量作为当前 工作任务，然后执行步骤3；

步骤3：进行变元决策，按照值域搜索空间最小原则从所有未赋值的约束变 元中选择要赋值的约束变元；

步骤4：对步骤3中要赋值的约束变元的所有可能取值进行赋值，形成新的 搜索向量放入任务队列中；

步骤5：对步骤4中的新的搜索向量进行并行相容检查，修剪向量空间；

步骤6：如果相容检查发现冲突，则进行回溯分析，找到引起冲突的约束变 元及该约束变元的赋值，将该约束变元的赋值删除后重建搜索向量，更新任务 队列，然后，执行步骤2；

如果相容检查没有发现冲突，且所有约束变元已经赋值，则说明找到了可 满足的求解，执行步骤7；

如果相容检查没有发现冲突，且不是所有约束变元已经赋值，则将新构建 的搜索向量加入任务队列，然后，执行步骤2；

步骤7：结束。

步骤1中：用整个约束变元域的搜索空间做笛卡尔积，形成初始任务队列。

步骤3中，采用启发式的方法做变元决策，做变元决策时选择值域搜索空 间最小的约束变元作为要实例化的约束变元，因为这样的约束变元所取的值成 为解的可能性当前最大。

步骤5中，采用基于集中式存储的全局约束并行相容模型对新的搜索向量 进行并行相容检查，对变元值域搜索空间进行修剪，缩小优化问题规模。

基于集中式存储的全局约束并行相容模型含有变量域更新节点和分布式相 容检查节点；变量域更新节点含有全局约束队列、全局变量域和变量域管理更 新引擎，变量域更新节点中进行全局约束队列的分发、全局变量域的管理；分 布式相容检查节点含有一个相容检查引擎，分布式相容检查节点负责实际的约 束相容检查，对变量值域进行局部更新。

分布式相容检查节点的工作步骤如下：

步骤301：从变量域更新节点获取约束条件和约束条件中包含的变元值域；

步骤302：执行相容检查，进行变元值域剪枝；如果出现冲突，转到步骤 303；如果没有冲突，转到步骤304；

步骤303：通知变量域更新节点已发生冲突，停止当前的工作，结束检查；

步骤304：将剪枝发送到变量域更新节点进行更新，结束检查；

变量域更新节点的工作步骤如下：

步骤401：接收新复制的变元或来自分布式相容检查节点的变元域更新请 求；

步骤402：执行变元域更新，即：对当前变元域与新赋值变元进行交运算， 或对当前变元域与相容检查后的变元域进行交运算；如果出现某个变元值域为 空，则转入步骤403；否则，转入步骤404；

步骤403：检查出现冲突，相容检查结束；

步骤404：把包含刚修改过值域的变量的约束加入到待相容检查任务队列；

步骤405：如果待相容检查任务队列为空，剪枝不会再发生变化，相容检查 结束，停止工作；如果待相容检查任务队列不为空，则转入步骤401。

步骤6中，如果相容检查发现冲突，采用回跳算法进行回溯分析；进行回 溯分析后，如果找不到引起冲突的约束变元，则表示问题无解，执行步骤7。

本发明的有益效果：

1、本发明针对相容优化技术耗费时间、占用资源的问题，提出了基于集中 式存储的并行相容技术，既能够及时检测冲突，又利用了剪枝单调性的特点， 异步实现可以提高并行程度，扩展性好。

2、本发明依赖对搜索空间的划分与调度，实现了与相容技术结合的并行搜 索方法，保证了搜索的完整性和不重复性，有效地改进了目前并行约束求解负 载分配不均衡、并行效率不高的问题，在相同分布式硬件平台下，大大提高了 并行处理能力和执行效率。

3、本发明利用并行搜索实现数据并行（or-并行），利用并行相容实现任务 并行（and-并行），并将这两种技术相结合，实现了约束求解的并行高效执行。

（四）、附图说明：

图1为基于集中式存储的全局约束并行相容模型的示意图；

图2为Cnode节点相容检查方法的流程图；

图3为Snode节点变量域管理更新的流程图。

（五）、具体实施方式：

基于相容优化的并行约束求解方法含有下列步骤：

步骤1：用整个约束变元域的搜索空间初始化任务队列；

步骤2：如果任务队列中没有搜索向量，表示求解结束、问题无解，执行步 骤7；如果任务队列中有搜索向量，则从任务队列中选择一个搜索向量作为当前 工作任务，然后执行步骤3；

步骤3：进行变元决策，按照值域搜索空间最小原则从所有未赋值的约束变 元中选择要赋值的约束变元；

步骤4：对步骤3中要赋值的约束变元的所有可能取值进行赋值，形成新的 搜索向量放入任务队列中；

步骤5：对步骤4中的新的搜索向量进行并行相容检查，修剪向量空间；

步骤6：如果相容检查发现冲突，则进行回溯分析，找到引起冲突的约束变 元及该约束变元的赋值，将该约束变元的赋值删除后重建搜索向量，更新任务 队列，然后，执行步骤2；

如果相容检查没有发现冲突，且所有约束变元已经赋值，则说明找到了可 满足的求解，执行步骤7；

如果相容检查没有发现冲突，且不是所有约束变元已经赋值，则将新构建 的搜索向量加入任务队列，然后，执行步骤2；

步骤7：结束。

步骤1中：用整个约束变元域的搜索空间做笛卡尔积，形成初始任务队列。

步骤3中，采用启发式的方法做变元决策，做变元决策时选择值域搜索空 间最小的约束变元作为要实例化的约束变元，因为这样的约束变元所取的值成 为解的可能性当前最大。

步骤5中，采用基于集中式存储的全局约束并行相容模型对新的搜索向量 进行并行相容检查，对变元值域搜索空间进行修剪，缩小优化问题规模。

基于集中式存储的全局约束并行相容模型含有变量域更新节点和分布式相 容检查节点；变量域更新节点含有全局约束队列、全局变量域和变量域管理更 新引擎，变量域更新节点中进行全局约束队列的分发、全局变量域的管理；分 布式相容检查节点含有一个相容检查引擎，分布式相容检查节点负责实际的约 束相容检查，对变量值域进行局部更新。

分布式相容检查节点的工作步骤如下：

步骤301：从变量域更新节点获取约束条件和约束条件中包含的变元值域；

步骤302：执行相容检查，进行变元值域剪枝；如果出现冲突，转到步骤 303；如果没有冲突，转到步骤304；

步骤303：通知变量域更新节点已发生冲突，停止当前的工作，结束检查；

步骤304：将剪枝发送到变量域更新节点进行更新，结束检查；

变量域更新节点的工作步骤如下：

步骤401：接收新复制的变元或来自分布式相容检查节点的变元域更新请 求；

步骤402：执行变元域更新，即：对当前变元域与新赋值变元进行交运算， 或对当前变元域与相容检查后的变元域进行交运算；如果出现某个变元值域为 空，则转入步骤403；否则，转入步骤404；

步骤403：检查出现冲突，相容检查结束；

步骤404：把包含刚修改过值域的变量的约束加入到待相容检查任务队列；

步骤405：如果待相容检查任务队列为空，剪枝不会再发生变化，相容检查 结束，停止工作；如果待相容检查任务队列不为空，则转入步骤401。

步骤6中，如果相容检查发现冲突，采用回跳算法进行回溯分析；进行回 溯分析后，如果找不到引起冲突的约束变元，则表示问题无解，执行步骤7。

下面结合具体的例子进一步说明本基于相容优化的并行约束求解方法（参 见图1～图3），具体执行步骤如下：

步骤一：用整个约束变元域的搜索空间初始化任务队列，从任务队列中选 择搜索向量作为当前工作任务；

步骤二：对当前搜索向量进行变元决策和变元赋值；

步骤三：进行并行相容检查，修剪向量空间；

步骤四：冲突回溯分析或根据新的搜索向量再次进行搜索，直至求解完成。

下面详细说明各步骤所包含的相关内容：

（一）步骤一：

CSP问题中的值域空间和搜索向量定义如下：

值域空间：是所有变元值域的笛卡尔积，如果一个CSP问题的所有变元集 合X={X₁,X₂,…,X_i,…,X_n}，所有变元对应的取值范围集合是D={D₁,D₂,…,D_n}， 约束条件集合是C=C₁,C₂,…,C_m，其中X_i的取值范围是V_i，那么该CSP的值域 空间是Dset=D₁×D₂×…×D_n。该CSP的解是V的子集。

搜索向量：搜索向量是值域空间的部分重新排列，按照搜索的先后顺序形 成一个多叉搜索树，可以表示为V=(V₁×V₂×…V_i…×V_n,grade)(D_j∈D)。 其中，grade表示决策层的最底层，即当前搜索到了哪个变元。grade之前的变 元是有序的（即变元决策顺序）且均赋值，如果i<j<=grade，表明V_i的决策层 高于V_j。grade之后的变元是无序的（待赋值）。当grade=n时，所有变元赋值完 成，找到了一组可满足解。

（二）步骤二：

执行变元决策，要选择当前应该为哪个变元赋值。本发明采用的是值域范 围最小的变元进行优先赋值。这样做找到解的概率更大，如果出现冲突也能更 大程度的减少搜索空间，缩小问题规模。

如果选取的变元v值域为{l₁,l₂,…l_n}，就需要将当前任务V分解成n个任务 以并行执行。v的每个具体赋值对应一个搜索子空间。如，V={v₁×…×v×…× v_m},分解后成为V_i={v₁×…×l_i×…×v_m}，(i=1,2…n)。

（三）步骤三：

基于集中式存储的全局约束并行相容模型由变量域更新节点（Snode）和分 布式相容检查节点（Cnode）组成，如图1所示。Snode包括全局约束队列、全 局变量域以及变量域管理更新引擎，主要负责全局约束队列的分发、变量域的 管理。Cnode只包括一个相容检查引擎，主要负责实际的约束相容检查，对变量 值域进行局部更新。

Cnode的执行通过如图2所示的步骤实现：

步骤:301：从Snode获取约束条件和约束条件中包含的变元值域；

步骤302：执行相容检查，进行变元值域剪枝。如果出现冲突，转到步骤 303；如果没有冲突，转到步骤304；

步骤303：通知Snode已发生冲突，停止当前的工作；

步骤304：:经过相容检查，已经对变量域进行剪枝，将结果发送到Snode 进行更新，结束检查。

Snode的执行通过如图3所示的步骤实现：

步骤401：接收新复制的变元或来自Cnode的变元域更新请求；

步骤402：执行变元域更新，当前变元域与新赋值变元或相容检查后的变元 域交运算。如果出现某个变元值域为空，转入步骤403；否则，转入步骤404；

步骤403：检查出现冲突，相容检查结束；

步骤404：把包含刚修改过值域的变量的约束加入到待相容检查任务队列；

步骤405：如果待相容检查任务队列为空，剪枝（变量域的更新）不会再发 生变化，相容检查已经结束，停止工作；否则，转入步骤401。

（四）步骤四：

当前的决策变元所有赋值均不能满足问题的求解，产生了冲突。此时，需 要进行的回溯分析，找到冲突原因。如果回溯到了最高决策层的变元，且它所 有取值均不能解决冲突，表明该问题不可解。否则，对引起冲突的变元的赋值 剪除，重新构建新的搜索向量。将新的搜索向量放到任务队列。

如果满足相容检查，且所有变元都已经得到了赋值，则找到了该问题的求 解，搜索过程结束。否则，将通过相容检查新产生的搜索向量传回任务队列， 进行下次搜索，直至找到解。