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

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

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

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

3、th提出了著名的实现弧相容性的算法AC30o为得到最优的时间复杂度,Mohr和Henderson提出AC40,但以较大的空间复杂度为代价。此后Bessiere相继提出算法AC60,AC70和AC20010o对于变量启发式，早期主要是静态变量启发式(SVO),代表是最小宽度(minwidth)和最大度(maxdegree)启发式0；2001年Bessiere提出带选择函数的动态变量启发式的一般框架0；2004年Boussemart等提出了冲突驱动的变量启发式策略0；2007年,2008年Grims和Wallace共同提出了将值删除

4、作为基本传播事件及与加权约束相结合冲突驱动的变量启发式00。但对于多种启发式策略的全面性能评估和对于问题的适应性研究，以及各种启发式策略混合应用方面还有很大的研究空间。二、约束满足问题约束满足问题(ConstraintSatisfactionProblem)常表示成一个三元组。其中X是变量的有限集合,表示成；=是变量值域的集合，其中是变量的值域；是一个有限约束集合。约束满足问题的求解是为变量集中的每个变量从其有限论域中寻找一个值，使得约束集中的所有约束被满足。通常可将约束满足问题用约束图的形式表示。图1为地图着色问题实例的约束图

5、。其中，数字表示二元约束满足问题的变量；字母表示变量的论域；变量之间的直线代表二元约束关系，含义为这两个变量不能取相同的值。三、弧相容技术为了提高效率，常在约束满足问题的求解过程中应用约束传播技术或相容性技术。弧相容技术是相容性技术中最为著名的。对于二元约束图中的弧，称它是弧相容的(ArcConsistency)，当且仅当对于变量的论域中的每一个值，在变量的论域中都存在一个值，使得满足上的一元约束,并且满足和上的二元约束。一个CSP是弧相容的，当且仅当它的约束图中每一条弧都是弧相容的Oo1977年Mackworth提出了著名的弧

6、相容算法AC-30。AC-3长久以来被广泛应用。下面我们给出AC-3的算法框架:Algorithm3.1AC~3()whiledoifrevise()thenifthenreturnfalseelsereturntrueAlgorithm3.2revise():booleanflag=falseforeachadoifnotsuchthatthendeletefromflag二trueendifendforreturnflagAC-3算法的时间复杂度下界为，最坏情况下的时间复杂度为，其空间复杂度为。其中是约束的个数，是变量域的规

7、模，是变量的个数。四、启发式策略启发式策略作为一种展望策略，引导或者决定接下来要实例化哪个变量或将论域中的哪个值赋给变量。对于大规模的约束满足问题的求解，启发式的应用能够有效压缩求解空间，快速得到问题的解或者指出问题无解。我们研究了当前流行的各种变量启发式策略，将其分类为：静态变量启发式、动态变量启发式和冲突驱动的变量启发式。(%1)静态变量启发式静态变量启发式策略(SVOs)中，变量在搜索的整个过程中保持不变的排序，仅仅使用问题初始状态的结构化信息。最简单的静态启发式策略是字典序(lexico)，即将变量按字典序排序。在约束图

8、中，相互间有约束关系的变量称为彼此的邻居。变量的度定义为邻居的个数。启发式策略deg(maxdegree)根据度的降序将变量排序。其他的静态变量启发式策略有minwidth启发式策略和minbandwidth启发式策略等。（二）动态变量启发式动态变量启发式策略（