约束满足问题中基于MDD的相容性算法研究

发布时间：2017-11-09 07:27

  本文关键词：约束满足问题中基于MDD的相容性算法研究

  更多相关文章： 人工智能 约束满足问题 多元约束 多值决策图

【摘要】：约束满足问题(CSP)是人工智能领域的一个重要分支,其核心是约束求解,探索高效的求解算法来提高求解效率是当前研究的主要问题。相容性技术在约束满足问题求解过程中起着举足轻重的作用,它可以在预处理阶段和搜索过程中将那些一定不能扩展成解的变量值删掉,从而减少了一些不必要的搜索,并减小了搜索空间。回溯搜索是目前比较通用的一种求解技术,在对变量选择和值的选择时还可加入合适的启发式策略,在回溯过程中与相容性技术相结合,使得约束满足问题的求解变得快速、高效。目前对于约束满足问题的求解多数是针对二元约束的,而很多实际问题都涉及多个变量,因此,多元约束的求解问题受到人们日益重视。对于多元约束的求解有两种处理办法:一是将多元约束满足问题转化为二元约束满足问题,然后再利用其高效的求解算法进行求解;二是直接利用多元约束的相容性算法来进行求解,本文主要研究的是后者。多元约束的表示形式有很多种,目前常用的是将解的元组放到一个表中,而表约束的压缩表示方法有多种,例如:结,多值决策图(MDD),压缩表,确定型有限自动机。当用这些复杂的数据结构表示表时,成功最关键的因素是实现的压缩率,它决定了需要空间的大小。利用多值决策图来表示多元约束可在空间上达到压缩的效果,本文就是在MDD这种结构下,根据已有的算法进行分析以及优化,具体所做工作如下:(1)对于多元约束求解算法进行介绍,针对原有的基于MDD的GAC算法进行改进,提出了mddc+算法,通过加入提前终止策略,在每一次遍历MDD以及子MDD节点过程中记录下每个变量的论域中当前已找到支持的值,若某个变量及其MDD图中下面的所有变量论域中的所有值都能够找到支持,那么当前节点的子MDD就无需遍历,而是只需找到一条当前节点到终端节点的路径,这样减少了一些不必要的寻找支持的过程,并通过实验验证了其高效性。(2)在搜索图中,对于每层待扩展结点的选择,即选择变量实例化过程中加入了启发式,经过比较,本文选用的是目前应用广泛的dom/wdeg启发式,可减少整体求解所用的时间,在一定程度上提升了求解效率。本文给出了(1)、(2)两点改进的伪代码,并与原有的mddc算法和STR算法进行对比试验,比较了求解所用CPU时间和扩展节点数,通过对比试验验证了本文所做的改进在很多问题上可以提高求解效率。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】

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

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

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

3 谷学强;陈t，

本文编号：1160885