约束问题求解

《约束问题求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第33卷第2期自动化学报Vol.33,No.22007年2月ACTAAUTOMATICASINICAFebruary,2007约束问题求解季晓慧1张健1摘要约束问题的求解涉及到人工智能、运筹学、计算机科学等领域.它的应用范围也极为广泛，包括计算机科学、控制科学、生物学等方面.本文对其发展历史、所要求解的问题以及它的基本方法等问题进行了综述.关键词约束求解，优化问题中图分类号TP301.6ConstraintProcessingJIXiao-Hui1ZHANGJian1AbstractConstraintprocessinginvol

2、vesthetechniquesofarti¯cialintelligence,operationsresearch,computerscienceandsoon.Ithasfoundmanyapplicationsincomputerscience,controltheory,biologyandsoon.Thispaperisasurveyofitshistory,methodsandtheproblemsitencounters.KeywordsConstraintprocessing,optimization1约束问题求解的

3、发展开始出现[3].现在用于求解约束问题的工具大多都是基于约束逻辑程序框架的[3].但这并不意味着约束问题的求解研究始于上个世纪70年约束求解仅限于此框架，约束问题也可以在类似于代的SceneLabeling以及60年代的InteractiveC++，Java的命令式语言框架下进行求解[3].在此Graphics[1»3].SceneLabeling试图用二维的线条之后，随着约束求解技术的不断发展，求解混合约描绘三维的物体，它的成果在于产生了各种一致束问题的研究也开始发展起来.(Consistent)算法[1,3].Interact

4、iveGraphics[4»6]的目的是允许用户在计算机的显示屏上绘制和处2约束问题理各种几何图形，它发展了约束求解技术中的局部推演(Localpropagation)及约束编译(Constraint形式化地讲，约束问题由以下三个基本元素组compiling)技术[3,6].约束求解的早期工作还包括成：变量V，变量的域D以及约束C.变量的域DMIT的电路分析与综合[7]，这些工作开创了设计能是变量可能取值的集合，变量Vi只能在它的域Di够求解通用约束问题的语言的研究[3,7].中进行取值；约束C描述了变量V之间必须满足的约束求解的重

5、要进展在于Gallaire[8]及关系.求解约束问题就是在各变量的域D中找到一Ja®ar[9]分别在1985年及1987年发现，逻辑程序设[1]个(或所有的)值S使得各变量之间满足约束C.计(Logicprogramming)实质上是一种特殊的约束约束问题也可以表示为三元组[2].求解问题[1»3].首先，逻辑程序设计语言的描述式根据约束问题中变量的域D的不同，约束问题(Declarative)特性与约束求解的描述问题而不是可以分为：布尔约束问题、有限约束问题、数值约束解决问题"的思想很接近；其次，二者所

6、使用的求解问题及混合约束问题等.问题的回溯法也十分的接近.更重要的是，逻辑程序2.1布尔约束问题设计中的等式项实质上是一种特殊的约束，而用于布尔约束问题要求V中的各变量只能在0或求解等式项的消解法也只是一种特殊的约束求解方1上取值，即布尔约束问题的域D为f0，1g.它的法.基于这种发现，约束逻辑程序设计(Constraint约束C实际上就是一组命题逻辑公式.所谓命题逻logicprogramming)[9]作为求解约束问题的新框架辑公式是布尔变量与逻辑连接符按照如下的规则形收稿日期2005-4-18收修改稿日期2006-6-9成的组

7、合体[10]：1)布尔变量是公式；2)如果'是ReceivedApril18,2005;inrevisedformJune9,2006国家自然科学基金(60125207,60421001)资助公式，则:'也是公式；3)如果Á和'是公式，则SupportedbyNationalNaturalScienceFoundationofÁ¤'也是公式；4)只有上面三条规则生成的表达式P.R.China(60125207,60421001)1.中国科学院软件研究所计算机科学国家重点实验室北京100080是公式.这里:是一元连接符非"，¤可以是

8、任何1.StateKeyLaboratoryofComputerScience,Instituteof一个二元连接符，如^(与)、_(或)、!(蕴含)等.Software,ChineseAcademyofSciences,Beijin