4.2.1 背景介绍
1.NP完全问题
在人工智能领域,所有问题可以按照计算复杂度被划分为两类,即计算复杂度为n的多项式(P)的易处理(tractable)问题和计算复杂度为n的非多项式(NP)的难处理(intractable)问题,其中n为问题牵涉的变量数。在tractable问题中,计算复杂度分各种情况,例如,选择(selection)问题的计算复杂度为n的多项式,排序(sorting)问题的计算复杂度为n log n的多项式,矩阵乘法(matrix multiplication)问题的计算复杂度介于n 3到n 2之间,线性编程(linear programming)问题的计算复杂度大于n 3。约束满足问题属于intractable问题,其计算复杂度与n呈指数关系,此外intractable问题还包括其他计算更为复杂的问题,如具有超指数复杂度的布利斯博格算术(Presburger arithmetic),以及无法确定计算复杂度的希尔伯特第十问题(Hilbert’s tenth problem)。这些难以处理的问题均是NP完全问题,因为它们的计算复杂度不能以n的多项式的形式表示,而是与n呈指数关系或其他更复杂的关系。
2.回溯搜索算法
约束满足问题可以使用穷举搜索(exhaustive search)来求解,即变量取值的每一种组合方式被逐一测试是否符合所有的约束,所有组合中第一个满足所有约束的组合就是问题的解。穷举搜索的组合数是所有变量值域的笛卡尔积。
回溯搜索(backtracking search)的效率要明显高于穷举搜索。在回溯搜索中,变量被逐一赋值,对于一个约束,一旦其有关的变量都被赋值了,该约束的判断程序就被激活来判断赋值是否满足约束。如果部分变量的赋值与任何一条约束有冲突,则回溯到最近一个被赋值的变量,改变该变量的值,继续进行约束判断。显然,一旦部分变量的赋值与约束发生冲突,回溯过程就可以从由所有变量构成的笛卡尔积中剪除一部分子空间。回溯搜索实际上是一种深度优先搜索[9]。
尽管回溯搜索从效率上绝对优于穷举搜索,但是根据求解约束满足问题的统计学模型,回溯搜索仍然具有指数相关的计算复杂度,造成这种现象的一个原因是回溯搜索中仍然存在大量的无效搜索(thrashing)[10]。也就是说,对于问题空间中不同部分的搜索往往因为同一原因而失败,造成无效搜索的最简单原因就是节点不一致性:如果一个变量x i的值域D i包含值a,该值不满足关于变量x i的约束,那么在赋值时,x i取a将总是引起搜索失败。另一种原因也可能造成无效搜索,假设所有的变量按照x 1,x 2,…,x i,…,x j,…,x n的顺序进行赋值,再假设x i和x j之间存在二元约束,且对于x i的取值a,x j中没有值可以与其满足约束。在回溯搜索树中,一旦x i被赋值为a,则当与x j的约束关系被考虑时,由于不能在x j中找到可与x i满足约束的值,搜索将失败。这一现象重复的次数将是所有x k(i＜k＜j)取值的可能组合数。造成第二种无效搜索的原因就是没有进行弧一致性的判断。
由节点不一致性造成的无效搜索可以通过将不符合约束的值从值域中删除的办法来消除;由弧不一致性造成的无效搜索可以在搜索开始之前通过对每条弧(x i,x j)应用弧一致性算法来消除。
3.一致性算法概述
节点一致性算法和弧一致性算法都属于一致性算法。一致性算法具有消除无效搜索、提高搜索效率的作用,还可以提高约束满足问题的求解效率。提高约束满足问题的求解效率有两种途径,即减少变量值域d的大小或减少变量数n。对于实际给定的约束满足问题,变量数n是不可变的,因此如果可以降低变量值域的大小d也可以间接达到提高搜索效率的目的。而一致性算法的目的就是减少变量值域的大小d,对变量值域进行删除的过程称为值域剪除(prunning)。
目前使用的一致性算法共有3大类:节点一致性算法、弧一致性算法和路径一致性算法。其中,节点一致性算法由于只涉及一个变量的约束满足,因此只需判断变量中的值是否满足约束即可。对于弧一致性算法,1970年Fikes在文献[11]中提到:“对于两个具有节点一致性的变量x i和x j,分别给定它们的值域Di和D j,如果对于v i∈Di不存在v j∈D j使得约束关系R ij(x,y)成立,则可以将v i从D i中删除。如果对于所有的v i∈Di都经过上述判断过程,则称弧(i,j)是一致性的。”在此基础上,Fikes给出后来被称为AC-1的弧一致性算法(arc-consistency)。由于AC-1的效率极为低下,Waltz在文献[12]和文献[13]中完善了Fikes的理论体系,并第一次引入了约束传播的思想。Waltz在文献中给出了所谓Waltz过滤算法,即后来的AC-2弧一致性算法。1977年,Mackworth总结了Fikes和Waltz的工作,给出了AC-2的一般性算法AC-3,同时还引入了路径一致性(path-consistency)思想,并给出了PC-1及其改进算法PC-2[14]。1985年,Mackworth和Freuder对AC-1、AC-2、AC-3、PC-1、PC-2进行了计算复杂度方面的理论分析[15]。1986年,Mohr和Henderson在文献[16]中提出了对AC-3和PC-2的改进算法AC-4和PC-3,并且在理论上证明AC-4在最差情况时间复杂度上已经达到最优。至此,弧一致性算法的发展告一段落。(https://www.daowen.com)
1992年,Hentenryck等人得出一种在特定约束条件最差情况时间复杂度上优于AC-4的弧一致性算法[17]。同年Mark Perlin也提出在可分解的前提下,有更高效的算法存在[18]。上述两种算法都被称为AC-5。由于AC-5使用了有关约束关系具体内容的信息,因此AC-5不能算是通用的弧一致性算法。
1994年,经过大量实验,Bessiere在文献[19]中指出:AC-4虽然在最差情况时间复杂度这个参数上是最优的,但是在大多数情况下其表现都要逊于AC-3。AC-3至今仍被认为是最经典的弧一致性算法。
4.一致性算法的基本思想
Fikes虽然对弧一致性进行了定义,但是给出的算法AC-1却只具有理论上的意义,AC-1的基本思想就是反复地对整个问题的所有变量之间存在的弧(约束关系)进行一致性判断,直至没有不一致性现象出现为止。Waltz和Mackworth在其各自的算法中都引入了传播队列的概念,将更新的范围限制在受到影响的弧上,这种思想的核心就是将对于某些变量值域的调整通过传播队列扩展到临近的变量直至问题中的所有变量。由于这种影响事实上是通过变量之间的约束进行传播的,因此这种思想被称为约束传播。
为了更清楚地说明约束传播的概念以及一致性算法在约束满足问题求解中的作用,引入了图论中的一些概念将整个约束满足问题表达为约束图,用图中的节点表示各个变量(如图4-10所示)。
图4-10 约束系统与约束图
在此,弧(arc)指的是约束图中两个节点之间的连接,即约束关系。考虑同时满足两个节点之间所有约束的算法就称为弧一致性算法。路径(path)指的是3个节点之间的连接,考虑同时满足3个节点之间所有约束的算法就称为路径一致性算法。路径一致性算法与弧一致性算法的主要区别在于考虑的对象不同。例如,在弧一致性中,如果对于v i∈Di不存在v j∈D j使得约束关系R ij(x,y)成立,则可以将v i从D i中删除;但是在路径一致性算法中,在约束关系Rij(x,y)成立的条件下,如果对于v i∈Di,v j∈D j,不存在v k∈D k使得约束关系R ik(x,z)、Rkj(z,y)成立,则不能从Di和D j中删除v i和v j,而只能确定约束关系Rij(x,y)不再成立。所以,路径一致性算法只对约束关系起作用,至于约束关系的调整是否会引起变量值的删除,还需要再应用弧一致性算法进行判断。因此,弧一致性算法是最重要的一致性判断算法。
判断弧一致性是求解CSP的一个基本技术,但是弧一致性检查算法很少单独起作用。事实上,它们经常从两个方面来对搜索算法进行辅助。一个是在搜索开始前,对搜索空间进行预处理;另一个是在搜索过程中与搜索算法结合来削减CSP问题的求解范围,如前向检查。通常来说,在带有回溯操作的搜索算法内部都会有弧一致性检查方法,如我们所提出的BFS-BB。
