交互约束满足问题的冲突解释算法研究

发布时间：2017-09-21 06:10

  本文关键词：交互约束满足问题的冲突解释算法研究

  更多相关文章： 交互约束满足问题 冲突解释算法 捆绑

【摘要】：约束满足问题是人工智能领域的一个重要分支,其表示形式是一个很好的框架,可以用来表示一系列现实问题,例如:配置问题,航班调度,资源分配等。约束传播和回溯搜索是约束满足问题的两个主要技术。交互约束满足是一种特殊的约束满足问题,交互约束满足问题是指在计算开始时问题模型还没有被完整定义,但是可以在计算过程中交互的传递信息。在交互约束满足问题求解过程中用户指定一些约束,这些用户约束代表着用户的需求。求解解释是交互约束满足问题中的一个研究热点。解释可以用于恢复相容性、避免不受欢迎的特性或者恢复一个已经排除的特性。目前的求解解释算法主要分两类:基于解的解释算法和基于冲突的解释算法。基于解的解释算法是修正用户约束集合的一个子集,使约束网络能够得到一个解;基于冲突的解释算法是给出导致约束网络不相容的一个子集,说明冲突产生的原因,通常来说我们要求该子集是一个极小集合。Barry O'Callaghan的Corrective Exp和Junker的QUICKXPLAIN是两类算法的代表。QUICKXPLAIN算法将问题域划分为两部分,运用递归的方式分别求解两个部分的冲突元素。QUICKXPLAIN算法的时间开销主要是在约束传播上,若能减少约束传播的次数和每次约束传播的时间,即可提高算法的运行效率。本文基于QUICKPLAIN算法提出了基于捆绑的冲突解释算法,即将m个约束捆绑为一个约束进行约束传播,m的取值范围是1-n,其中n为用户约束的个数;m取值为1时,即是QUICKXPLAIN算法本身。本文对m=2和m=n/2两种情况进行了研究:(1)当m=2时,我们采用将两个约束捆绑为一个的方式进行约束传播,我们将该算法称为基于双值捆绑的冲突解释算法。该算法可以使两个用户约束共用一次约束传播的过程,这样使得约束传播的次数可变为原来的二分之一;但是当一次约束传播导致冲突时,需要做额外的工作来判断两个被捆绑的约束中到底哪个是冲突元素(有可能是其中之一,也有可能两者均是)。(2)当m=n/2时,我们采用将用户约束集合的二分之一捆绑为一个的方式进行约束传播,我们将该算法称为基于折半捆绑的冲突解释算法。该算法将用户约束分成两部分,按照两个约束的方式来判断冲突集合所在的位置;然后运用递归的方式分别在两个子问题中求解冲突集合,直到子问题中只包含一个约束时即为冲突集合中的元素。通过这种方式可以将问题域减小为原来的二分之一,并且多个约束同时传播,可在一定程度上减少每次约束传播的时间。理论上,根据用户约束集合和冲突约束集合的大小不同,我们不能保证哪一算法在所有情况下都是最优的。但是实验结果显示,在实际问题中,我们提出的两种算法效率均高于QUICKXPLAIN算法,其中大多数情况下基于折半捆绑的冲突解释算法的效率高于基于双值捆绑的冲突解释算法。
【关键词】：交互约束满足问题 冲突解释算法 捆绑
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要4-6
• Abstract6-10
• 第1章 绪论10-13
• 1.1 研究背景与现状10-11
• 1.2 本文工作及结构11-13
• 第2章 约束满足问题及求解技术13-25
• 2.1 约束满足问题13-14
• 2.2 相容性技术14-22
• 2.2.1 弧相容算法15-17
• 2.2.2 路径相容算法17-18
• 2.2.3 限定路径相容算法18-21
• 2.2.4 单弧相容21-22
• 2.3 MAC算法22-25
• 第3章 交互约束满足问题及解释算法25-34
• 3.1 交互约束满足问题及其解释25-28
• 3.2 QUICKXPLAIN算法28-34
• 第4章 基于捆绑的冲突解释算法34-48
• 4.1 基于双值捆绑的冲突解释算法35-40
• 4.2 基于折半捆绑的冲突解释算法40-44
• 4.3 实验结果及分析44-48
• 第5章 总结与展望48-50
• 参考文献50-53
• 作者简介53-54
• 致谢54

【相似文献】

中国期刊全文数据库 前10条

1 郭冬芬;李铁克;;基于约束满足的炼钢批量计划的制定方法[J];微计算机信息;2007年12期

2 汤萍萍;王红兵;;基于层次约束满足的产品选择算法[J];现代计算机(专业版);2007年08期

3 谷学强;陈t，

本文编号：892813