MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); function MyAutoRun() {    var topp=$(window).height()/2; if($(window).height()>450){ jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); }  }    window.onload=MyAutoRun; $(window).resize(function(){ var bodyw=$win.width(); var _leftPaneInner_width = jQuery(".rich_html_content #leftPaneInner").width(); var _main_article_body = jQuery(".rich_html_content #main_article_body").width(); var rightw=bodyw-_leftPaneInner_width-_main_article_body-25;   var topp=$(window).height()/2; if(rightw<0||$(window).height()<455){ $("#nav-article-page").hide(); $(".outline_switch_td").hide(); }else{ $("#nav-article-page").show(); $(".outline_switch_td").show(); var topp=$(window).height()/2; jQuery(".outline_switch_td").css({ position : "fixed", top:topp+"px" }); } }); 负表约束的简单表缩减广泛弧相容算法
  软件学报  2016, Vol. 27 Issue (11): 2701-2711   PDF    
负表约束的简单表缩减广泛弧相容算法
李宏博1,2, 梁艳春1,2, 李占山1,2     
1. 吉林大学 计算机科学与技术学院, 吉林 长春 130012 ;
2. 符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012
摘要: 广泛弧相容算法(generalized arc consistency,简称GAC),是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势.
关键词: 约束满足问题     广泛弧相容     简单表缩减     负表约束    
Simple Tabular Reduction for Generalized Arc Consistency on Negative Table Constraints
LI Hong-Bo1,2, LIANG Yan-Chun1,2, LI Zhan-Shan1,2     
1. College of Computer Science and Technology, Jilin University, Changchun 130012, China ;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering for the Ministry of Education(Jilin University, Changchun 130012, China
Foundation item: National Natural Science Foundation of China (61472158, 61272207);Science & Technology Plan of Jilin Province (20140101200JC)
Abstract: Generalized arc consistency (GAC) plays a central role in solving the constraint satisfaction problem. Table constraints can theoretically represent all kinds of constraint relations, and many algorithms have been proposed to establish GAC on table constraints in the past decade. Among these methods, the simple tabular reduction algorithms (STR) are very efficient. However, the existing STR algorithms are suitable for only positive table constraints. They can not directly work on negative table constraints. In this paper, a STR algorithm, called STR-N, is first proposed to directly work on negative table constraints. Then, two improved versions of STR-N, STR-N2 and STR-NIC are presented. Experimental results show that the STR-N algorithms bring improvements over CPU time while solving the instances with negative table constraints.
Key words: constraint satisfaction problem     generalized arc consistency     simple tabular reduction     negative table constraint    

约束满足问题[1]在人工智能领域有着广泛的应用,许多实际问题可以应用约束满足问题建模,如配置问题[2]、路径规划问题、任务调度问题等.一个约束满足问题(constraint satisfaction problem,简称CSP)P由3部分组成:P=<X,D,C>,其中,X={x1,x2,…,xn}是一个有限的变量集合;D={dom(x1),dom(x2),…,dom(xn)},其中,dom(xi)是变量xi的离散有限值域;C={c1,c2,…,ck}是一个有限约束集合,其中,任意cjC表示变量取值之间的制约关系.一个约束c包含两个部分:一个有序的变量集合scp(c)={xi1,xi2,…,xir}和这些变量有限值域的笛卡尔积dom(xi1)x dom(xi2)x…xdom(xir)的一个子集,这个子集中的元组表示满足(或者违反)这条约束的变量取值组合.约束有多种知识表示方式,例如,基于断言(predicate)的约束x1+x2<5,当x1=2,x2=3时不满足约束,而当x1=2,x2=1时满足约束;基于特殊语义的,如表达“全部都不相等”关系的alldifferent(x,y,z)约束[3],只有当x,y,z三者中任意两个都不相等时才满足约束.除了这些隐式定义的约束以外,还有显式定义的约束,即,表约束.表约束[4]是显式地列出所有满足(或者违反)约束的元组,当其列出的元组满足约束时,我们称其为正表约束;当其列出的元组违反约束时,我们称其为负表约束.我们以著名的n-皇后问题为例介绍表约束.用CSP为n-皇后问题建模时,每个皇后是一个变量,每个皇后可放的n个位置是每个变量的值域,任意两个皇后之间不能攻击的条件就是其中的约束关系.对于4皇后问题,表示第1个和第2个皇后之间不能互相攻击的约束c12如果用正表约束表示,则包含6个满足c12的元组{(1,3) ,(1,4) ,(2,4) ,(3,1) ,(4,1) ,(4,2) };如果使用负表约束表示,则包含10个违反c12的元组{(1,1) ,(1,2) ,(2,1) ,(2,2) ,(2,3) ,(3,2) ,(3,3) ,(3,4) ,(4,3) ,(4,4) },类似地,第1个和第4个皇后之间的约束c14如果用正表约束表示,则包含10个元组{(1,2) ,(1,3) ,(2,1) ,(2,3) ,(2,4) ,(3,1) ,(3,2) ,(3,4) ,(4,2) ,(4,3) };负表约束则包含6个元组{(1,1) ,(1,4) ,(2,2) ,(3,3) ,(4,1) ,(4,4) }.显然,出于对空间的考虑,我们应该使用正表约束表示c12、负表约束表示c14.此外,在表约束上对某个元组进行约束检查时,要在所有元组上查找该元组:如果在正表约束中找到该元组,则该元组满足约束;否则不满足约束.在负表约束上结果则恰好相反.显然,元组个数直接影响约束检查的效率,因此,我们应该恰当地选择正表约束和负表约束.

寻找一个约束满足问题的解是NP-难问题[1],一个高效的完备求解策略是在回溯搜索过程中使用局部相容技术[5]进行剪枝.应用于二元约束满足问题的弧相容算法[6]是在求解中应用最广的局部相容技术,在非二元约束满足问题上[4, 7]的弧相容技术称为广泛弧相容.通用的广泛弧相容算法GAC-valid[4]可以利用约束检查在所有类型的约束上实现广泛弧相容.利用了表约束的特殊知识表示形式后,一些正表约束上专用的广泛弧相容算法相继被提出来.GAC-allowed[4]算法遍历所有满足约束的元组,直到找到一个有效的元组.利用这种方式,为变量值寻找支持.为了更快地寻找支持,文献[8, 9]分别提出了两种基于索引的技术加速遍历过程.文献[10]提出了一种方法,在寻找支持时交替访问有效元组和满足元组.基于压缩的方法首先将表约束转化成压缩表[11]或多元决策树[12],然后将专用的算法应用在其各自的数据结构上.除了以上方法以外,2007年提出了一种表缩减算法simple tabular reduction(STR)[13],它通过动态地维持约束表中有效的元组来识别那些有支持的值,在松紧度较紧 的正表约束上使用时,效率明显高于其他算法.由于STR算法执行效率高,近几年一些基于STR算法的改进工作[14-19]也相继发表于高水平国际会议与期刊上.但是由于目前的STR算法是基于正表约束中记录的元组是满足约束的元组这一特征,对于负表约束中记录的违反约束的元组,STR算法无法应用.如前面4-皇后问题例子,正表约束和负表约束可以相互转化,但是STR算法高效是由于其应用于记录的元组个数较少的正表约束,而将负表约束转化为正表约束后,其记录的元组个数通常较多,除了对空间因素的考虑以外,这也将直接影响STR算法的效率.因此,将负表约束转化成正表约束后使用STR算法的做法是不明智的.我国学者近几年在约束程序相关领域的研究工作主要是生成难解问题模型[20, 21]的相关理论研究、快速求解可满足性问题[22, 23]以及最大可满足问题max-CSP[24].

本文首先提出一种表缩减算法,称为STR-Negative[25],简称STR-N.它通过将约束上所有元组进行分类计数的方式,可以直接在负表约束上实现广泛弧相容.接着,我们提出STR-N算法的两种改进版本——STR-N2和STR-NIC.STR-N2可以减少STR-N在进行有效性检查时的一些冗余操作;STR-NIC使用一种遍历条件,可以避免一些冗余的遍历表缩减过程.我们的实验首先将正表约束和负表约束相互转化, 然后分别使用STR算法和STR-N算法进行求解.结果发现,二者求解效率的拐点发生于约束松紧度在0.466附近,而不是预期的0.5.然后,我们比较了STR-N算法和其他可应用于负表约束的广泛弧相容算法,包括通用算法GAC-valid、通用算法在负表约束上的改进版GAC-valid-forbidden以及基于多元决策树压缩的方法在应用于负表约束时的变种mddc.实验结果显示,STR-N在一些随机问题上求解效率比其他方法更高.在一些标准库测试用例上,STR-NIC的效率 最高.

1 背景知识

给定一条约束c,scp(c)={xi1,xi2,…,xir}表示c中包含的变量集合,|scp(c)|称为c的元数.对于c上的一个元组t,t[x]表示变量xt中的取值.我们使用t表示约束c中包含的违反c的元组个数,则t/|dom(xi1)xdom(xi2)x…x dom(xir)|称为约束c的约束松紧度(constraint tightness),即dom(xi1)xdom(xi2)x…xdom(xir)中违反约束c的元组的比例,记为t(c).通常,当t(c)大于0.5时,我们使用正表约束表示c,因为此时满足c的元组个数大于违反c的元组个数;当t(c)小于0.5时,我们使用负表约束表示c,因为此时违反c的元组个数大于满足c的元组个数.我们称一个元组是有效的,当且仅当这个元组中的所有变量值都没有被从对应的变量值域中删除.判断一个元组是否有效的过程称为有效性检查,而判断一个元组是否满足一条约束的过程称为约束检查.给定一个约束满足问题P=<X,D,C>,如果C中所有约束元数都小于等于2,则称P为二元约束满足问题;否则,称为非二元约束满足问题.一个约束满足问题的解是为每个变量在其值域中选择一个值构成集合S,使得S中的所有变量取值满足C中所有约束.在本文中,(xi,a)表示变量xi的取值为a,cij表示变量xixj之间的约束.

定义1(广泛弧相容(generalized arc consistency (GAC))[4]. 给定一个约束满足问题P=<X,D,C>、一个约束c和一个变量xscp(c):

· 一个值(x,a)与约束c是相容的,当且仅当c中存在一个有效的元组t,使得t[x]=a,并且t满足c,此时,t称为(x,a)在约束c上的支持.

· 一条约束c是广泛弧相容的,当且仅当对于任意xscp(c),dom(x)不为空,并且对于任意adom(x),(x,a)与约束c是相容的.

· P是广泛弧相容的,当且仅当C中所有约束都是广泛弧相容的.

从广泛弧相容定义可知,一个元组t称为一个值在一条约束上的支持要满足两个条件:(1) t是有效的;(2) t满足这条约束.为了实现广泛弧相容,广泛弧相容算法通常为每个变量的每个值在包含这个变量的所有约束上寻找一个支持,并将那些没有找到支持的值从对应的值域中删除.如果算法执行过程中某个变量的值域中的所有值都被删除,则广泛弧相容失败,问题无解.维持弧相容算法(maintaining arc consistency,简称MAC)[26]是目前最流行的求解约束满足问题的方法,它在回溯搜索过程中构造一棵搜索树,并使用广泛弧相容算法进行剪枝.在搜索树的每个节点上,一个变量和这个变量值域中的一个值被选中,然后,MAC使用GAC算法进行剪枝,将那些已经不再相容的值删除.如果GAC执行失败,则发生回溯.

2 正表约束上的表缩减算法

表缩减算法STR[13]由Ullmann于2007年提出,其主要思想是:它遍历每条约束表中记录的所有元组,同时检查这些元组是否有效,如果发现一个元组是有效的,那么这个元组中包含的所有变量值在这条约束上就一定有支持.这是由于STR是应用于正表约束的,而正表约束中记录的元组都是满足约束的,因此,这个元组同时满足了成为支持的两个条件.使用STR实现广泛弧相容的算法流程如算法1所示,其中,STR(c)是在单个约束c上实现广泛弧相容的算法,其伪代码如算法2所示,STR(c)返回的是在c上进行表缩减时发现值域有改变的变量,如果STR(c)发现有变量值域为空,则直接返回FAIL.

算法1. GAC-STR算法.

1: initialize the propagation queue Q;

2: while Q is not empty do

3: select and remove a constraint c from Q;

4: reduced(X)←STR(c);

5: if reduced(X)=FAIL then

6: return FAIL;

7: for each xreduced(X) do

8: for each constraint c' involving x do

9: if c'≠c then

10: QQ∪{c'}

11: return success

算法2. 正表约束的STR算法.

Input: A positive table constraint c.

Output: The set of variables whose domain have been reduced.

1: for each xscp(c) and x is not assigned do

2: gacValues(x)←∅;

3: index←1;

4: while indexlastIndex(c) do

5: t table(c)[position(c)[index]];

6: if t is valid then

7: for each (x,a)∈t and x is not assigned do

8: gacValues(x)←gacValues(x)∪{x};

9: indexindex+1;

10: else

11: removeTuple(t,index,c);

12: reduced(X)←∅;

13: for each xscp(c) and x is not assigned do

14: if |gacValues(x)|<|dom(x)| then

15: dom(x)←gacValues(x);

16: if dom(x)=∅ then

17: return FAIL;

18: reduced(X)←reduced(X)∪{x};

19: return reduced(X)

由于STR算法要遍历表中记录的所有元组,为了配合回溯搜索使用,STR算法还给出了一种机制,使得在上一层搜索节点就已经失效的元组在下一层不会被重新检查.当前还未被检查失效的元组称为当前元组,STR在遍历表的过程中只遍历当前元组.请注意,一个当前元组并不一定是有效的,它只是还未被检查是有效的还是无效的.这一机制主要避免了检查那些已经确定失效了的元组.这一机制使用如下数据结构[14]来实现.

· table(c):table(c)一个静态数组,其中,静态记录了满足c的所有元组,数组下标从1到元组个数table(c). length,table(c)生成之后,其中的元组位置不再变化.

· position(c):position(c)是一个长度为table(c).length的整数数组,初始时,其元素取值分别是1到table(c).length.它提供的是对table(c)中元组的间接访问.使用position(c)后,c的表中的第i个元组是table(c)[position(c)[i]].

· lastIndex(c):lastIndex(c)是一个整数,它指向position(c)的某个下标,这个下标是position(c)中最后一个有效的元素.也就是说,position(c)中所有lastIndex(c)之前的元素所对应的table(c)中的元组是当前元组,lastIndex(c)之后所对应的所有元组都是无效的.

这3个数据结构的关系及其如何表示当前元组如图 1所示.

Fig. 1 Example of current tuples 图 1 当前元组举例

图 1中,table(c)总共记录了9个元组,lastIndex(c)为5,则position(c)中第6个元素之前都对应table(c)中一个当前元组,此时的当前元组分别为tuple-1,tuple-2,tuple-5,tuple-7,tuple-8.

算法2中,removeTuple(t,index,c)的作用是将t标示成已经无效,该函数是将position(c)[index]和position(c)[lastindex(c)]互换,然后将lastIndex(c)减1,之后,原本position(c)[index]指向的table(c)中的元组就被标示成已经无效,因为只有lastIndex(c)之前的元组才是当前元组.在回溯搜索过程中,STR要在每层的搜索树节点上为每条约束记录lastIndex(c),当发生回溯时,要根据在对应层的记录恢复lastIndex(c).

3 负表约束上的表缩减算法

在实现广泛弧相容时,我们并不一定要找到每个变量值的支持到底是哪个元组,只需证明每个值都存在一个支持就可以了.给定一条约束c、变量xscp(c)、值adom(x),对于c上包含(x,a)的所有元组(即,除x外,scp(c)中其他所有变量值域的笛卡尔积),我们根据需要,将这些元组分为3类.首先,我们根据有效性将这些元组分为“有效的”和“无效的”;然后,对于所有“有效的”元组,我们可以根据是否满足c将其分为“有效并且满足c的”和“有效但是违反c的”.显然,任意一个“有效并且满足c的”的元组都是(x,a)在c上的支持,因此,我们要做的就是证明“有效并且满足c的”元组个数大于0.我们通过如下3步证明“有效并且满足c的”元组存在.

· 第1步,我们要计算c上包含(x,a)的所有“有效的”元组的个数,记为valid(x,a,c).这个个数就是除x外,scp(c)中其他所有变量当前值域的笛卡尔积结果集的大小,即,除x外,scp(c) 中其他所有变量当前值域大小的乘积.我们可以在O(r)时间内计算得到这个数字,其中,rc的元数.对于dom(x)中的任意值a,valid(x,a,c)都是相同的,因此,我们将valid(x,a,c)记为valid(x,c).

· 第2步,我们要计算c上包含(x,a)的所有“有效但是违反c的”元组的个数,记为valid-forbidden(x,a,c).对于负表约束,其记录的所有元组都是违反c的,因此,valid-forbidden(x,a,c)就是(x,a)出现在table(c)中有效元组的次数.因此,我们可以通过遍历table(c)中当前元组并检查其有效性这一过程来记录(x,a)在table(c)的有效元组中出现的次数.这一遍历过程可以同时得到scp(c)中所有变量的所有值在table(c)的有效元组中出现的次数.

· 第3步,“有效并且满足c的”元组个数valid-allowed(x,a,c)就是“有效的”元组个数减去“有效但是违反c的”元组个数.如果valid-allowed(x,a,c)大于0,那么(x,a)在c上一定存在支持.

基于以上3个步骤,我们在算法3中给出STR-Negative算法的伪代码.

算法3. 负表约束的STR算法.

Input: A negative table constraint c.

Output: The set of variables whose domain have been reduced.

1: iflastIndex(c)=0 then

2: return ∅;

3: for each xscp(c) and x is not assigned do

4: compute valid(x,c) for x;

5: for each value adom(x) do

6: valid-disallowed(x,a,c)←0;

7: index←1;

8: while indexlastIndex(c) do

9: τtable(c)[position(c)[index]];

10: ift is valid then

11: for each (x,a)∈t and xis not assigned do

12: valid-disallowed(x,a,c)←valid-disallowed(x,a,c)+1;

13: indexindex+1;

14: else

15: removeTuple(t,index,c);

16: reduced(X)←∅;

17: for each xscp(c) and x is not assigned do

18: for each value adom(x) do

19: if valid(x,c)-valid-disallowed(x,a,c)=0 then

20: remove (x,a) from dom(x);

21: if dom(x)=∅ then

22: return FAIL;

23: reduced(X)←reduced(X)∪{x};

34: return reduced(X);

算法3中第1行、第2行,当lastIndex(c)为0时,说明约束c中当前有效的元组都是满足c的元组,所以避免了后面的遍历过程.

命题1. 算法STR-Negative(c)的最坏时间复杂度为O(rd+rt),最坏空间复杂度为O(rd+rt),其中,rc的元数,dscp(c)中变量的最大值域,ttable(c)中记录的元组个数.

证明:算法3中,第3行~第6行的循环耗时O(rd);第8行~第15行的循环耗时O(rt),因为这一循环最多可能访问t个元组,检查每个元组是否有效耗时为O(r);第17行~第23行的循环耗时为O(rd).因此,算法STR- Negative(c)的最坏时间复杂度为O(rd+rt).算法STR-Negative(c)使用的数据结构中,table(c)占用rt的空间,因为共有t个元组,每个元组占用空间为r.position(c)占用空间为t.r个变量的d个值的valid(x,c),valid-allowed(x,a,c),valid-forbidden(x,a,c)总共占用空间O(r d).因此,STR-Negative(c)的最坏空间复杂度为O(rd+rt).

4 优化STR-Negative算法

这一节我们将描述STR-N算法的两种改进版本——STR-Negative2(STR-N2) 和STR-N-Iteration-Condition (STR-NIC).

4.1 STR-Negative2:避免冗余的有效性检查操作

给定一条约束c,当前我们要在c上执行STR-N(c),变量xscp(c),如果当前dom(x)和上次在约束c上调用STR-N(c)时的dom(x)相同,那么dom(x)中的所有值在这中间都没有被删除,因此在进行有效性检查时,可以避免检查x的值.基于此,我们提出STR-Negative2算法.下面是STR-N2使用的两种额外的数据结构[14].

· need-check(c):need-check(c)是scp(c)的一个子集,记录那些在进行有效性检查时需要检查的变量.

· lastSize(c):lastSize(c)是一个长度为|scp(c)|的整数数组,lastSize(c)[x]记录了上次调用STR-N2(c)时,变量x的值域大小,如果本次调用开始前x的值域大小和lastSize(c)[x]不相同,那么将x加入need-check(c).所有的lastSize(c)[x]初始时为-1.

与STR-N算法相比,STR-N2算法只需在遍历当前元组前根据上次记录的lastSize(c)计算need-check(c),然后更新lastSize(c),之后,在检查元组有效性时,只检查need-check(c)中变量.在回溯搜索中使用时,STR-N2要在每层的搜索树节点上为每条约束记录lastSize(c),当发生回溯时,要根据在对应层的记录恢复lastSize(c).

4.2 STR-N-Iteration-Condition:避免冗余的遍历元组

显然,对于STR-N算法,最耗时的部分是在第8行~第15行的循环中遍历访问当前元组.我们提出一种遍历条件iteration condition(IC),来避免那些冗余的遍历元组过程.满足IC可以在不遍历访问元组的条件下保证每个变量值都有支持.

性质1(遍历条件(iteration condition(IC)). 给定一个负表约束c,valid-min是scp(c)中所有变量的valid(x,c)的最小值.当valid-min大于lastIndex(c)时,scp(c)中所有变量的所有值在c上一定存在支持.

IC是正确的,因为lastIndex(c)是当前c中所有“有效但是违反c的”元组个数(注意:不是某个值的“有效但是违反c的”,而是所有变量所有值的“有效但是违反c的”),而valid-min是最小的valid(x,c),因此当valid-min大于lastIndex(c)时,所有变量的所有值的valid(x,c)都一定大于它们的valid-forbidden(x,a,c).

IC可以在STR-N算法开始遍历元组前使用(算法3的第7行以前),使用了IC的STR-N算法我们称为STR-NIC算法.如果满足IC,则STR-NIC算法直接返回空集,即,没有变量的值域改变了.

5 实验结果

我们的测试环境为Intel(R) Core(TM) i7-3770 CPU@ 3.40GHz,4.00GB RAM,Windows 7,JDK1.7.本文使用的所有benchmark测试用例以及随机问题模型生成器RBGenerator均可从http://www.cril.univ-artois.fr/~lecoutre/下载.我们测试了在MAC中使用不同的广泛弧相容算法的求解效率,其中,变量启发式使用了著名的Dom/Ddeg[27, 28].

5.1 STR对比STR-N

STR算法和STR-N算法分别应用于正表约束和负表约束,而两种约束可以相互转化,我们选择两种算法的依据通常是根据约束松紧度,只有当约束松紧度为0.5时,正表约束和负表约束记录的元组个数相同.因此,我们需要了解两种算法在不同约束松紧度时求解效率.对于同一条约束,无论约束松紧度是多少,我们强制将其转化成STR或者STR-N可以应用的形式,之后比较二者的求解效率.我们采用了随机问题模型Model RB[20],一个Model RB可以根据以下5个参数<r,n,d,e,t>生成,其中,r是约束元数,n是变量个数,d是变量值域大小,e是约束个数,t是约束松紧度.对于任意一组模型,我们测试了30个随机用例并取其平均值进行比较.我们使用RBGenerator来生成不同约束松紧度的测试用例.对于正表约束,我们分别实现了STR[13],STR2[14],STR3[15]这3种算法;对于负表约束,我们分别实现了STR-N,STR-N2,STR-NIC这3种算法.之后,我们分别选择两组中求解效率最高的进行了对比.图 2展示了在不同的约束松紧度下,最优的STR算法求解耗时除以最优的STR-N算法的求解耗时.我们的原始数据显示,正表约束上效率最高的是STR2算法,而负表约束上效率最高的是STR-N2算法.当y轴值大于1时,使用负表约束的STR-N的效率更高;当y轴值小于1时,使用正表约束的STR算法效率更高.

Fig. 2 Result of STR vs. STR-N 图 2 STR算法与STR-N算法比较结果

图 2中的数据显示,二者效率比较的拐点在约束松紧度为0.466左右时发生,而不是我们预期的0.5左右.这是由于STR-N算法在最后识别那些失去支持的值的时间复杂度为O(rd),而STR算法在这部分时间复杂度为O(r).对于同样约束松紧度的参数,我们还比较了约束元数对求解效率的影响.从图中可以看出,在相同的约束松紧度条件下,随着元数的增长,有优势的一方优势在逐渐增大.例如在约束松紧度0.216时,随着元数从3增到10,STR的耗时从STR-N的1.69倍增长到了2.32倍.

5.2 STR-N对比其他广泛弧相容算法

这里,我们比较了本文提出的3种STR-N算法和其他可应用于负表约束的广泛弧相容算法,包括通用算法GAC-valid[4]、通用算法在负表约束上的变种GAC-valid-forbidden[29](GAC-vf)和基于多元决策树压缩算的方法在负表约束上的变种mddc[12].其中,所有的GAC-valid算法使用了“多向残余支持[30]”技术和避免冗余修正检查技术[31].

图 3是在15组不同参数的随机问题的上的测试结果.为了更为直观,我们将每组数据以GAC-valid的求解耗时为基准,其他算法的耗时分别除以基准耗时,所得比值展示在图 3中.

Fig. 3 Results of STR-N vs. other GAC algorithms on random instances 图 3 STR-N与其他广泛弧相容算法随机问题比较结果

从第12组~第15组可知,当元数较大并且约束个数较少时,STR-N2效率最高;当约束松紧度特别低时,所有的STR-N算法效率都高于其他3种算法,其中,STR-NIC的效率最高.从第1组1、第2组、第5组、第8组可知:当约束松紧度相对较高时,GAC-valid的效率也相对较高.但是从第12组可以看出,当元数较大时,仍然是STR-N算法效率较高.因此,在约束松紧度较低并且元数较大的随机问题上,应用STR-N算法的效果最好.

接着,我们测试了可以使用负表约束的3组标准库测试用例,包括ChessboardColoration(cc),Ramsey和Golomb Ruler.

· ChessboardColoration问题是在一个包含rc列的棋盘上使用n个颜色为每个方格着色,要求任意一个矩形的4个角落的方格颜色不能完全相同,每个用例使用cc-r-c-n表示.

· Ramsey问题是使用k个颜色为一个完全图的边着色,使得图中没有单色的三角形.即,任意一个三角形的3个边颜色不能相同,每个用例使用ramsey-n-k表示.

· Golomb Ruler问题是在长度为m的尺子上放置n个标记,使得任意两个标记之间的距离都不相同,每个用例使用ruler-m-n-a4表示.

图 4中展示了这些测试用例上求解耗时的比较结果.

Fig. 4 Results of time cost on benchmark instances 图 4 标准库测试用例耗时比较结果

这3类标准库测试用例,其中一些测试用例无法在1 200s内求解.由于使用了相同的变量启发式Dom/ Ddeg,所有的求解算法都将构造一颗相同的搜索树,也就是效率较高的算法在相同时间内会访问更多的搜索树节点(node),因此对于这些用例,我们比较了它们在1 200s内的搜索树节点个数,并将结果展示在图 5中.

Fig. 5 Results of search tree nodes on benchmark instances 图 5 标准库测试用例耗时搜索树节点比较结果

图 4图 5中的数据与图 3中的数据类似,都是以GAC-valid的结果为基准,各种算法在图中展示的结果都是和基准结果的比值.由图中可以看出,在ChessboardColoration问题和Ramsey问题上,STR-N算法效率高于其他算法;而在GolombRuler问题上,只有STR-NIC算法的效率高于其他算法.值得一提的是,STR-NIC的效率在所有这3组标准库测试用例上都高于其他3种算法.

6 结论与展望

表缩减算法STR在正表约束上求解效率非常高,但是目前已有的STR算法只能应用于正表约束.本文提出一种可应用于负表约束的STR-N算法,同时给出STR-N算法的两种改进版本——STR-N2和STR-NIC.我们的实验结果显示,当约束松紧度小于0.466时,STR-N算法求解效率高于STR;当约束松紧度大于0.466时,STR的求解效率较高.与其他应用于负表约束的算法相比,在那些约束松紧度较松的约束上,STR-N算法的效率较高.

目前,在正表约束STR算法的基础上,已经有国外研究学者提出了对应的高阶相容算法[16, 17],另外还有基于压缩表的改进工作[19]和基于短支持的改进工作[18].正负表约束上的STR算法是这些改进工作的基础,而在负表约束上的高阶相容技术目前仍是空白.因此,我们下一步的工作打算在负表STR算法基础上,设计对应的高阶相容算法,并使用压缩表和短支持的技术改进负表约束STR算法.

参考文献
[2] Li H, Shen H, Li Z, Guo J. Reducing consistency checks in generating corrective explanations for interactive constraint satisfaction. Knowledge-Based Systems, 2013, 43 (5) :103–111. [doi:10.1016/j.knosys.2013.01.024]
[3] Régin JC. A filtering algorithm for constraints of difference in CSPs. In:Barbara H, Richard E, eds. Proc. of the AAAI'94. Seattle:AAAI Press, 1994. 362-367.
[4] Bessière C, Régin JC. Arc consistency for general constraint networks:Preliminary results. In:Pollack E, ed. Proc. of the IJCAI’97. Nagoya:Morgan Kaufmann Publishers, 1997. 398-404.[doi:10.1109/WI.2007.95]
[5] Bessière C. Constraint Propagation. Rossi F, van Beek P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam:Elsevier, 2006. 29-84.[doi:10.1016/S1574-6526(06)80007-6]
[6] Mackworth AK. Consistency in networks of relations. Artificial Intelligence, 1977, 8 (1) :99–118. [doi:10.1016/0004-3702(77)90007-8]
[7] Sun JG, Jing SY. Solving non-binary constraint satisfaction problem. Chinese Journal of Computers, 2003, 26 (12) :1746–1752(in Chinese with English abstract). [doi:10.3321/j.issn:0254-4164.2003.12.020]
[8] Lhomme O, Régin JC. A fast arc consistency algorithm for n-ary constraints. In:Manuela M, Subbarao K, eds. Proc. of the AAAI 2005. Pittsburgh:AAAI Press, 2005. 405-410.
[9] Gent IP, Jefferson C, Miguel I, Nightingale P. Data structures for generalized arc consistency for extensional constraints. In:Proc. of the AAAI 2007. Vancouver:AAAI Press, 2007. 191-197.
[10] Lecoutre C, Szymanek R. Generalized arc consistency for positive table constraints. In:Benhamou F, ed. Proc. of the CP 2006. Nantes:Springer-Verlag, 2006. 284-298.[doi:10.1007/11889205_22]
[11] Katsirelos G, Walsh T. A compression algorithm for large arity extensional constraints. In:Bessière C, ed. Proc. of the CP 2007. Providence, 2007. 379-393.
[12] Cheng KC, Yap RHC. An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints, 2010, 15 (2) :265–304. [doi:10.1007/s10601-009-9087-y]
[13] Ullmann JR. Partition search for non-binary constraint satisfaction. Information Science, 2007, 177 (18) :3639–3678. [doi:10.1016/j.ins.2007.03.030]
[14] Lecoutre C. STR2:Optimized simple tabular reduction for table constraints. Constraints, 2011, 16 (4) :341–371. [doi:10.1007/s10601-011-9107-6]
[15] Lecoutre C, Likitvivatanavong C, Yap C. A path-optimal GAC algorithm for table constraints. In:De Raedt L, et al., eds. Proc. of the ECAI 2012. Montpellier:IOS Press, 2012. 510-515.[doi:10.3233/978-1-61499-098-7-510]
[16] Paparrizou A, Stergiou K. An efficient higher-order consistency algorithm for table constraints. In:Hoffmann J, Selman B, eds. Proc. of the AAAI 2012. Toronto:AAAI Press, 2012. 535-541.
[17] Lecoutre C, Paparrizou A, Stergiou K. Extending STR to a higher-order consistency. In:Jardins M, Littman M, eds. Proc. of the AAAI 2013. Bellevue:AAAI Press, 2013. 576-582.
[18] Jefferson C, Nightingale P. Extending simple tabular reduction with short supports. In:Rossi F, ed. Proc. of the IJCAI 2013. Beijing:AAAI Press, 2013. 573-579.
[19] Xia W, Yap RHC. Optimizing STR algorithms with tuple compression. In:Schulte C, ed. Proc. of the CP 2013. Uppsala:Springer-Verlag, 2013. 724-732.[doi:10.1007/978-3-642-40627-0_53]
[20] Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 2000, 12 (1) :93–103. http://cn.bing.com/academic/profile?id=2139300273&encoded=0&v=paper_preview&mkt=zh-cn
[21] Gao J, Wang J, Yin M. Experimental analyses on phase transitions in compiling satisfiability problems. Science China Information Sciences, 2014, 58 (3) :1–11. [doi:10.1007/s11432-014-5154-0]
[22] Cai S, Su K. Comprehensive score:Towards efficient local search for SAT with long clauses. In:Proc. of the IJCAI 2013. Beijing:AAAI Press, 2013. 489-495.
[23] Cai S, Su K. Local search for boolean satisfiability with configuration checking and subscore. Artificial Intelligence, 2013, 204 (9) :75–98. [doi:10.1016/j.artint.2013.09.001]
[24] Huang P, Yin M. An upper (lower) bound for max (min) CSP. Science China Information Sciences, 2014, 57 (7) :1–9. [doi:10.1007/s11432-013-5052-x]
[25] Li H, Liang Y, Guo J, Li Z. Making simple tabular reduction works on negative table constraints. In:Jardins M, Littman M, eds. Proc. of the AAAI 2013. Bellevue:AAAI Press, 2013. 1629-1630.
[26] Sabin D, Freuder EC. Contradicting conventional wisdom in constraint satisfaction. In:Cohn AG, ed. Proc. of the ECAI’94. London:John Wiley and Sons, 1994. 125-129.[doi:10.1007/3-540-58601-6_86]
[27] Bessière C, Régin JC. MAC and combined heuristics:Two reasons to forsake FC (and CBJ?) on hard problems. In:Freuder EC, ed. Proc. of the CP’96. Cambridge:Springer-Verlag, 1996. 61-75.[doi:10.1007/3-540-61551-2_66]
[28] Smith BM, Grant SA. Trying harder to fail first. In:Prade H, ed. Proc. of the ECAI'98. Brighton:John Wiley and Sons, 1998. 249-253.
[29] Lecoutre C. Generalized arc consistency for table constraints. In:Constraint Network:Techniques and Algorithms. ISTE/Wiley, 2009.[doi:10.1002/9780470611821.ch5]
[30] Lecoutre C, Hemery F. A study of residual supports in arc consistency. In:Sangal R, Mehta H, Bagga RK, eds. Proc. of the IJCAI 2007. San Francisco:AAAI Press, 2007. 125-130.
[31] Li H, Li Z, Wang T. Improving coarse-grained arc consistency algorithms in solving constraint satisfaction problems. Ruan Jian Xue Bao/Journal of Software, 2012, 23 (7) :1816–1823(in Chinese with English abstract). [doi:10.3724/SP.J.1001.2012.04129] http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4129&journal_id=jos
[1] Freuder EC, Mackworth AK. Constraint satisfaction:An emerging paradigm. In:Rossi F, van Beek P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam:Elsevier, 2006. 13-28.[doi:10.1016/S1574-6526(06)80006-4]
[7] 孙吉贵, 景沈艳. 非二元约束满足问题求解. 计算机学报, 2003,26 (12) :1746–1752. [doi:10.3321/j.issn:0254-4164.2003.12.020]
[31] 李宏博, 李占山, 王涛. 改进求解约束满足问题粗粒度弧相容算法. 软件学报, 2012,23 (7) :1816–1823. [doi:10.3724/SP.J.1001.2012.04129] http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=4129&journal_id=jos