基于问题结构的边界启发式方法

李占山，张 良，郭劲松，张 乾

（1.吉林大学 符号计算与知识工程教育部重点实验室，长春 130012；2.吉林大学 计算机科学与技术学院，长春 130012）

0 引 言

约束满足问题（Constraint satisfaction problems，CSP）是人工智能方向的一个重要分支，相关技术被广泛应用于组合问题求解，如配置器设计、调度、符号推理和路由等。相容性算法和求解技术的研究一直是CSP领域的研究热点，国内研究人员已有工作主要集中于前者［1－4］，而随着约束满足问题应用领域的不断扩大，约束求解技术得到了越来越多的关注。已有求解算法主要包括三类:回溯算法、局部搜索和动态规划［5］。作为一种完全求解算法，回溯算法的主要任务包括为可解问题找到解以及证明不可满足问题的不可解性，但在应用过程中，由于问题解空间规模较大，经常会出现“组合爆炸”现象，朴素回溯过程在人们期望的时间内难以给出一个有效解，如何提高求解效率成为研究回溯算法面临的首要问题。

求解过程中，回溯算法进行深度优先检索，需要不断选择变量来进行实例化，对众多问题的实验研究表明，变量被实例化的顺序对于能否高效地求解起着至关重要的作用。为了得到好的搜索变量排序，研究人员提出了多种变量启发式方法，对于已有启发式的讨论可参见文献［5］。通过实验对比研究人员发现，没有一种现有启发式能在所有问题上的求解效率明显优于其他方法。因此，根据问题自身特性，寻找基于问题结构的启发式方法被认为是提升求解效率的有效途径。

Composed问题为一类随机问题，众多实际应用问题具有类似于Composed问题的结构特性，但受限于问题的特殊结构，现有启发式方法在处理该类问题时总是生成过多节点，造成求解效率下降。本文从Composed问题结构出发，提出边界变量集的概念，并给出了Composed问题中边界变量的筛选方法，在此基础之上设计实现了边界启发式方法。

1 问题背景

定义1 二元约束网络G＝ （X，D，C），其中，X 为有限变量集｛X1，X2，…，Xn｝，D 为论域集｛D1，D2，…，Dn｝，对于任意变量Xi∈ X，Di为其所有可能取值构成的有限论域，即Di＝dom（Xi），C 为有限约束集｛C1，C2，…，Ce｝，任意Ci∈C均为作用在X上的二元关系。

变量Xi和Xj之间的约束记为Rij，则Rij⊂dom（Xi）×dom（Xj），值对（（Xi，a），（Xj，b））满足Rij，当且仅当（（Xi，a）（Xj，b））∈Rij。约束网络中，若变量Xi和Xj之间存在约束，则变量节点Xi和Xj之间存在弧（i，j），变量的度为与其相连约束弧的个数。

对集合X中所有变量进行赋值，令Xi＝ai，且ai∈Di，若元组T ＝ （a1，a2，…，an）满足C中所有约束，则T为问题的一个解，如果T不存在，该问题是不可满足的。对变量集X中任意k（1≤k＜n）个变量进行赋值，得到元组T1＝ （a1，a2，…，ak），若T1满足C中所有约束，则称T1为该问题的部分解。

约束网络结构特征描述还需要使用到如下定义，详细介绍可参考文献［6］。

定义2 （松紧度Tightness）

约束弧 （i，j）的松紧度记为Tij，则

定义3 （网络密度Density）

回溯求解过程中，为了压缩搜索空间，基于约束传播思想，每次变量赋值以后都要进行相容性检查，如果检查失败，则需进行回溯，检查成功则在当前未赋值变量中选择变量进行实例化，变量启发式则作用于该过程指导变量的选取。根据不同的相容性强度，研究人员提出多种求解算法，Maintain arc consistency（MAC）［7］算法是应用最为广泛、被认为是效率较高的求解算法之一。下面给出弧相容定义以及MAC算法实现框架［8］:

定义4 （弧相容Arc Consistency）AC

（1）弧 （i，j）是相容的，当且仅当对任意（Xi，a）∈ dom（Xi），存在（Xj，b）∈dom（Xj），使得（（Xi，a），（Xj，b））∈Rij。

（2）约束网络是弧相容的，当且仅当对任意弧（i，j）∈G，（i，j）是相容的。

MAC算法实现框架如下所示:

2 Composed问题

Composed问题在文献［9］中首先被描述，结构上Composed问题具有多个局部区域，一般Composed问题结构如图1［6］所示。

图1 典型Composed问题结构图Fig.1 Typical tructure of Composed problems

图1为同一问题的两个结构图，左边约束网络任意约束弧灰度相同，而右侧网络中，约束弧灰度正比于其松紧度大小。一个Composed问题可表示成如下形式元组:

n1为中心区域变量个数，d1为中心区域变量论域的大小，m1为中心区域约束网络密度，t1为中心区域内约束弧松紧度；s为伴随区域个数；参数n2、d2、m2和t2表示伴随区域局部网络特性，所表示内容与中心区域相对应；L表示将一个伴随区域连接到中心区域的约束个数，t3为约束松紧度。实验部分所用测试样例中，变量论域大小都为10，且每个伴随区域都由8个变量构成，为了表示起来更加简洁，略去某些特性，记为如下元组:

Composed问题中，伴随区域局部网络密度以及变量间约束弧的松紧度都要高于中心区域，直观上来看，在伴随区域找到一个满足所有约束的部分解会更加困难，按照设计现有启发式方法所依赖的失败优先原则［10］，应该利用启发式方法将求解过程引导到这些区域，但受限于问题结构，现有启发式方法无法实现该目标。

常用启发式方法中，deg和ddeg为静态启发式，dom／deg、dom／ddeg和dom／wdeg为动态启发式，初始阶段，两类启发式受到变量度的影响，选取变量都会落到中心区域。不同于其他启发式，dom／wdeg方法为每个约束弧绑定动态weight值，变量Xi的wdeg值计算公式如下:

式中:FutVars为当前未实例化变量集。

当发生回溯时，导致死节点生成的约束弧weight值增加，当检索过程进行到一定程度时，较大的weight值能帮助检索过程跳转到更加合理的区域进行。因此dom／wdeg启发式具有一定学习能力，但该过程仍会生成过多节点，使得问题求解效率受到影响。

3 边界启发式方法

Composed问题在结构上可划分为多个局部区域，当位于某个局部区域内部的变量被实例化并进行相容性检查时，约束传播沿着约束弧进行，而与该变量直接相连的变量大都位于该局部区域，这也使得整个约束传播过程通常会被局限于该区域，dom／wdeg启发式只能在该区域内收集启发式信息，文献［11］的分析表明，在更全面的解空间内收集启发式信息有助于选择更加合理的变量。

结合以上分析发现，Composed问题的求解关键为位于中心区域与伴随区域相邻边界上的变量，即位于伴随区域且通过弱约束与中心区域相连的变量，符合这样条件的变量称为边界变量，由这些变量构成的集合称为边界变量集。当边界变量被实例化并进行相容性检查时，约束传播会沿着约束弧同时影响到中心区域和伴随区域，避免了被局限于某个区域。

边界启发式方法主要设计思想为从约束网络中筛选出所有边界变量构成边界变量集，检索过程中，边界变量集中的变量应当具有高于其他变量的实例化优先级。为了找出边界变量，在Composed问题约束网络上首先给出如下定义:

定义5 （平均松紧度Average tightness）

定义6 （强约束，弱约束）

约束Rij为强约束，当且仅当Tij≥avg＿t；反之，若Tij＜avg＿t则Rij为弱约束。

边界启发式方法在实现时分为两个阶段，一是预处理阶段，对变量进行筛选得到边界变量集；二是在检索过程中利用已有信息来选择变量。

预处理阶段，首先计算出网络平均松紧度avg＿t，然后为变量设置标识数组strong［n］和weak［n］（n为变量个数），对任意i∈（0…n－1），如果strong［i］为真，则变量Xi有强约束连接，为假则不受强约束限制，如果weak［i］为真，则变量Xi有弱约束连接，为假则不受弱约束限制。遍历C中元素，对任意t∈（0…e－1），若Ct为强约束，则将其所约束变量i和j的strong标识设为真，如果为弱约束，则将weak标识设为真。对strong和weak初始化结束之后，对任意变量Xi∈X，若其对应的标识strong［i］与weak［i］合取为真，则变量Xi为边界变量，否则不是。这样在预处理阶段结束后就可以得到边界变量集mid＿var＿set。

求解阶段:给出边界启发式的两种实现策略，记为H1、H2。H1:选择变量时先要判断 mid＿var＿set是否为空，不为空，按照dom／wdeg启发式从mid＿var＿set中选择一个变量；若为空，则在所有未赋值变量中按照dom／wdeg启发式选择变量进行实例化。H2:将mid＿var＿set内所有边界变量的初始wdeg值设定为一个大于0的定值，以此来提高边界变量在dom／wdeg启发式下的实例化优先级，检索过程按照dom／wdeg启发式进行。两种策略主要区别在于:前者只有在所有边界变量被实例化以后才会选择非边界变量进行赋值，后者则是将dom／wdeg启发式下的求解过程向边界变量集靠拢，不保证边界变量总是先于非边界变量被选择。

4 实验结果及分析

实验部分采用 MAC3rm［12］作为求解算法，MAC3rm为MAC算法中的一种，已有实验结果表明，MAC3rm的实际求解效率要优于其他MAC算法。现有启发式中，dom／wdeg［13］方法在一系列问题上有较好的表现，而且通过应用该启发式，MAC算法可以有效地代替基于回跳的求解技术，成为较为稳定高效的通用求解算法，因此采用dom／wdeg启发式与新启发式方法进行对比，以求解所消耗CPU时间、检索过程生成节点数以及约束检查数作为参考标准，其中CPU时间t以ms为单位，生成节点数和约束检查次数分别记为num和cc，这里一次约束检查是指判断一个值对 （（Xi，a），（Xj，b））是否满足Rij所需要进行的操作。为了提高实验本身的效率，预处理阶段，首先在约束网络上进行一次弧相容检查，删除变量论域中的不满足值，该过程所进行的约束检查次数不会被计入对比实验数据。H2启发式需要为每个变量对应wdeg设定初值，如果wdeg初值设为正无穷，则H2启发式等同于H1，如果为0，则为dom／wdeg启发式，为了避免该初值过大或者过小，并且能够一定程度上反映问题规模，这里设定为n／2（n为变量个数）。

实验中部分测试样例的XML描述文档可在线下载［14］，其他样例则按照参数要求随机生成，测试样例包括了22组可满足问题，每组问题都包括10个随机生成的具体问题，其中14组为可满足，8组为不可满足样例。为了避免单个问题本身特性对启发式方法效果的影响，对每一类问题的10个样例测试结果取其平均值进行比较。实验结果如表1和表2所示。

实验结果显示H1启发式在某些样例上求解效率急剧下降，消耗时间和生成节点数都有数量级上的增加，表3给出其中一个样例的结果对比。

对检索过程中变量被实例化的顺序和次数进行分析，可以发现产生这种现象的原因在于启发式H1限制了dom／wdeg启发式执行，使得即使收集到足够多的启发式信息，也不能正确跳离当前检索区域。边界变量位于不同伴随区域内，在某个边界变量被实例化且进行约束传播之后，受dom／wdeg启发式的影响，通常与该变量位于同一伴随区域内的其他边界变量会被选择进行实例化。当该伴随区域内所有边界变量均被实例化后，受H1启发式限制，检索过程会跳转到另外一个伴随区域，并从中选择边界变量进行实例化。在Composed问题中，任意两个伴随区域之间没有约束直接相连，因此在起始阶段，各个伴随区域内边界变量较容易被实例化，但随着被实例化边界变量的增多，在相容性检查时，中心区域内变量论域会被不断删减，此时可能出现论域为空的现象而产生回溯。对于某些样例，只有当边界变量集内大部分变量被实例化后才会发生回溯，这时H1启发式会不断调整边界变量的取值，直到找到一个可拓展为最终解的部分解，由于边界变量集本身检索空间也很庞大，该过程会耗费大量时间。从实验结果可以看到H1启发式求解效率的这种波动现象只出现在了具有10个伴随区域的问题类中，伴随区域个数为5的样例中没有出现该现象，由于伴随区域个数的减少，边界变量集中变量数也相应减小，其自身搜索空间也不会过于庞大，因此规模较小的边界变量集可以有效地避免出现这种情况。统计实验数据时，为了能对三种启发式方法在普遍问题上的求解效率进行对比，出现

这种现象的特殊样例并没有包括在内，表中对于包含这些样例的每一类问题均注明了实际统计样例的个数。

表1 可满足问题Table 1 Satisfiable problems

表2 不可满足问题Table 2 Unsatisfiable problems

表3 特殊样例Table 3 Abnormal instance

在所有可满足问题中，25＋10＋〈5，0.05〉、75＋5＋〈10，0.05〉和75＋5＋〈15，0.05〉三类问题难度较小，三种启发式方法在所有样例上都接近于无回溯求解。而在其他可满足问题上，H1和H2启发式的求解效率均要明显优于dom／wdeg启发式。结合前面的分析，H1启发式求解效率在某些问题上存在较大波动，不能够实现稳定求解，而H2启发式则在所有问题上都可以实现稳定高效的求解。H1和H2启发式在一般问题上的求解效率相近，但由于稳定性差异，H2启发式要比H1更适用于可满足问题的求解。

在不可满足问题上，H1和H2启发式的求解效率都要远高于dom／wdeg启发式，启发式生效的主要原因在于两者为检索过程寻找到了合适的起始点。在所有不可满足样例中，伴随区域都是不可满足的，通过对检索过程中生成节点对应的实例化变量进行分析，发现dom／wdeg启发式生成的多余节点大都对应中心区域内变量，只有在dom／wdeg启发式收集到足够信息时，检索过程才能跳转到边界区域内变量，从而快速得出问题的不可满足性。

通过对三种启发式方法在可满足问题和不可满足问题上的求解效率进行对比，H1和H2启发式要明显优于dom／wdeg启发式，其中H2启发式方法在求解的稳定性上要好于H1启发式。而边界启发式方法生效的原因主要有以下两点:①启发式筛选出的边界变量位于问题求解困难的部分，满足失败优先原则，为检索过程选择了合适的起始点；②可以更好地发挥相容性技术在检索过程中所能起到的作用，边界变量赋值之后进行相容性检查时，约束传播会同时朝着伴随区域和中心区域两个方向进行，避免了被局限于某个局部，不仅可以压缩问题规模，还可以较早地发现指向死节点的无用分支。基于第二点原因，dom／wdeg启发式还可以在更加全面的解空间内收集启发式信息，从而给出更为合理的变量选择。

5 结束语

基于Composed问题结构，提出了边界变量的概念，并给出了在该类问题上筛选边界变量的方法，以此为基础设计实现了边界启发式方法。通过实验分析，新启发式求解效率要明显高于原有启发式方法。实验结果也表明边界变量在该类问题的求解过程中起着关键的作用。对于边界变量，本文并没有给出严格定义，直观上边界变量为位于问题不同求解区域相邻边界上的变量。Composed问题具有明显的边界区域，而且通过运用约束弧的松紧度特性可以快速筛选出边界变量，因此在该类问题上进行了关于边界变量集有效性的分析与讨论。但是文中边界变量集的筛选方法过度依赖于Composed问题结构，而不具有普遍适用性，如何在具有类似结构的众多实际问题中筛选出边界变量集将是接下来工作的重点。文中讨论只涉及到了约束弧的松紧度，显然网络密度在各局部区域的变化也是问题结构的重要特性，如何将二者结合给出更为通用的边界变量集筛选方法，是改进已有启发式方法的重要方向。

［1］朱兴军，张永刚，李莹，等.多值传播的相容性技术［J］.自动化学报，2009，35（10）:1296－1301.Zhu Xing－jun，Zhang Yong－gang，Li Ying，et al.Consistency technique of multi－value propagation［J］.Acta Automatica Sinica，2009，35（10）:1296－1301.

［2］刘春晖，朱兴军，孙吉贵，等.一种改进的双向Singleton弧相容算法［J］.吉林大学学报:工学版，2008，38（3）:666－670.Liu Chun－hui，Zhu Xing－jun，Sun Ji－gui，et al.Improved bidirectional Singleton arc consistency algorithm［J］.Journal of Jilin University（Engineering and Technology Edition），2008，38（3）:666－670.

［3］杜会盈，李占山，李宏博，等.图分割在Singleton弧相容算法中的应用［J］.吉林大学学报:理学版，2010，48（6）:981－986.Dui Hui－ying，Li Zhan－shan，Li Hong－bo，et al.Graph partitioning applied in Singleton algorithm［J］.Journal of Jilin University（Science Edition），2010，48（6）:981－986.

［4］高健，孙吉贵，张永刚，等.参数化弧相容约束传播［J］.吉林大学学报:信息科学版，2007，25（2）:183－187.Gao Jian，Sun Ji－gui，Zhang Yong－gang，et al.Parameterized arc consistency constraint propagation［J］.Journal of Jilin University（Information Science Edition），2007，25（2）:183－187.

［5］van Beek Peter.Backtracking search algorithms［C］∥Handbook of Constraint Programming.Francesca Rossi，Peter van Beek，Toby Walsh（eds），New York:Elsevier，2006:85－126.

［6］Li Xing－jian，Epstein Susan L.Learning clusterbased structure to solve constraint satisfaction problems［J］.Annals of Mathematics and Artificial Intelligence，2010，60:91－117.

［7］Sabin Daniel，Freuder Eugene C.Contradicting conventional wisdom in constraint satisfaction［C］∥Proceedings of CP，Rosario，Orcas Island，Washington，1994:10－20.

［8］Likitvivatanavong Chavalit，Zhang Yuan－lin，Bowen James，et al.Arc consistency during search［C］∥Veloso Manuela M （eds.）.Proceedings of IJCAI，Hyderabad，India:Morgan Kaufmann，2007:137－142.

［9］Christophe Lecoutre，Frederic Boussemart，Fred Hemery.Backjump－based techniques versus confict—directed heuristics［C］∥Proceedings of ICTAI，Boca Raton，Florida，USA:IEEE Press，2004:549－557.

［10］Haralick Robert M，Elliott Gordon L.Increasing tree search efficiency for constraint satisfaction problems［J］.Artificial Intelligence，1980，14:263－313.

［11］Grimes Diarmuid，Wallace Richard J.Learning from failures in constraint satisfaction search［C］∥Wheeler Ruml，Frank Hutter，AAAI Workshop on Learning for Search，Boston， Massachusetts，USA:AAAI Press，2006.

［12］Christophe Lecoutre，Fred Hemery.A study of residual supports in arc consistency［C］∥Veloso Manuela M（eds），Proceedings of IJCAI，Hyderabad，India，2007:125－130.

［13］Frederic Boussemart，Fred Hemery，Christophe Lecoutre，et al.Boosting systematic search by weighting constraints［C］∥R.López De Mántaras，L.Saitta，Proceedings of ECAI，Valencia，Spain:IOS Press，2004:146－150.

［14］http:／／www.cril.univ－artois.fr／～lecoutre／benchm arks.html＃