基于等价类划分的配置求解与解释计算

摘要：

基于约束的配置模型中会有一些变量之间不存在任何直接或间接的约束关系,这样的变量之间进行约束传播不会互相影响取值.基于配置问题的这一特点,提出了一种等价类划分的思想,用于构造产品模型时的预处理技术,可以有效地将原问题划分为若干子问题,证明了这些子问题可以分别处理.分别采用两种回溯策略对求解效率进行了测试,结果表明能够有效地提高求解效率.最后,等价类划分方法与计算解释的QUICKXPLAIN算法集成计算冲突解释,测试结果表明,经过等价类划分后,同样可以有效地提高计算解释的效率.

关键词：约束满足、配置、等价类、回溯、冲突解释

所属期刊栏目：22

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金60773097,60873148,60973089;吉林省科技发展计划20071106,20080107

在线出版日期：2011-08-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：929-937