基于不同启发式策略的约束满足问题求解研究

《基于不同启发式策略的约束满足问题求解研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、摘要:约束满足问题是人工智能的重要研究方向。约束传播技术和卅发式策略是影响约束求解算法效率的关键。对于大规模和人型具有结构化特征的问题，设计并运用侑效的值序、变量序启发式策略将大大缩减搜索空间，极大提高问题求解效率。文中对•现在流行的静态启发式、动态启发式和冲突驱动的启发式等不同类别的启发式采用标准库问题实例进行适应性求解测试，并对各种启发式策略进行性能评估。中国论文网关键词:人工智能;约束满足问题;弧相容;启发式策略中图分类号:TP18文献标识码:A文章编号:1674-7712(2012)12-0123-

2、03一、引言近年来，作为人匚智能领域最活跃的研究分支之一，约束程序(ConstraintProgramming,CP)研究方向得到蓬勃发展。约束程序研究的核心问题是约束满足问题(ConstraintSatisfactionProblem,CSP)oFl前,该领域出现了以约束传播技术和针对大规模应用问题的启发式策略为代表的研究新热点。相容性技术是约束传播的代表技术，它在加速求解效率和压缩求解空间上发挥着不可佔量的巨大作用0。目询主流技术是弧相容性和路径相容性技术。弧相容技术是相容性技术中应用最为广泛的。197

3、7年,Mackworth提出了著名的实现弧相容性的算法AC30。为得到蝕优的时间复杂度,Mohr和Henderson提出AC40,但以较人的空间复杂度为代价。此后Bessiere相继提出算法AC60,AC70和AC20010o对于变量启发式,早期主耍是静态变量启发式(SV0),代表是最小宽度(minwidth)和最大度(maxdegree)启发式0;2001年Bessiere提岀带选择函数的动态变眾启发式的一般框架0;2004年Boussemart等提出了冲突驱动的变量启发式策略0;2007年,2008年G

4、rims和Wallace共同提出了将值删除作为基本传播事件及•加权约束相结合冲突驱动的变量启发式00。但対于多种启发式策略的全血性能评估和对于问题的适应性研究，以及各种启发式策略混合应用方面述有很大的研究空间。二、约束满足问题约束满足问题(ConstraintSatisfactionProblem)常表示成一个三元组。其中X是变虽:的有限集合,表示成；=是变量值域的集合，其屮是变量的值域；是一个有限约束集合。约束满足问题的求解是为变量集中的每个变量从:其冇限论域中寻找一个值，使得约束集中的所有约束被满足。通

5、常可将约束满足问题用约束图的形式表示。图1为地图着色问题实例的约束图。其中，数字表示二元约束满足问题的变虽;字母表示变量的论域;变虽Z间的直线代表二元约束关系,含义为这两个变量不能取相同的值。三、弧和容技术为了提高效率，常在约束满足问题的求解过程屮应川约束传播技术或相容性技术。弧相容技术是相容性技术中最为苦名的。对于二元约束图中的弧，称它是弧相容的(ArcConsistency),当且仅当对于变虽的论域中的每一个值，在变虽的论域中都存在一个值，使得满足上的一元约束，并且满足和上的二元约束。一个CSP是弧相容

6、的，当且仅当它的约束图中每一条弧都是弧相容的0。1977Mackworth提出了著名的弧相容算法AC-30。AC-3长久以来被广泛应用。下而我们给出AC-3的算法框架：Algorithm3.1AC-3()whiledoifrevise()thenifthenreturnfalseelsereturntrueAlgorithm3.2revise（）:booleanflag=falseforeachadoifnotsuchthatthendeletefromfla沪trueendifendforreturnfl

7、agAC-3算法的时间复杂度下界为，最坏情况下的吋间复杂度为，其空间复杂度为。其中是约束的个数，是变量域的规模，是变量的个数。四、启发式策略启发式策略作为一刊展望策略，引导或者决定接下来要实例化哪个变量或将论域中的哪个值赋给变虽。对于大规模的约束满足问题的求解，启发式的应用能够冇效压缩求解空间，快速得到问题的解或者指出问题无解。我们研究了当前流行的各种变最启发式策略,将其分类为:静态变量启发式、动态变量启发式和冲突驱动的变量启发式。（一）静态变量启发式静态变量启发式策略（SVOs）屮，变量在搜索的整个过程屮

8、保持不变的排序，仅仅使用问题初始状态的结构化信息。敲简单的静态启发式策略是字典序（lexico）,即将变屋按字典序排序。在约束图屮，相互间有约束关系的变量称为彼此的邻居。变量的度定义为邻居的个数。）；发式策略deg（maxdegree）根据度的降序将变量排序。其他的静态变量启发式策略有minwidth启发式策略和minbandwidth启发式策略等。（二）动态变罐启发式动态变量启发式策略（DVOs）是非常高效的