基于贪心搜索的Singleton弧相容算法的研究

发布时间：2017-11-16 14:06

  本文关键词：基于贪心搜索的Singleton弧相容算法的研究

  更多相关文章： 约束满足问题 Singleton弧相容 启发式方法

【摘要】：约束满足问题是人工智能领域的一个重要分支,其表示形式可以形象的对现实世界中的问题进行建模,从而将问题抽象为约束满足问题的模型进行求解,已经广泛的应用于配置,调度,规划,网络以及生物信息学等诸多领域。求解一个约束满足问题,是指为其找到一个解或者证明其无解。约束满足问题的求解往往结合使用搜索和推理的方法。搜索技术用于遍历问题中所有变量的当前论域来寻找解。推理技术通过变量消元,树分解和相容性技术将问题转化为一个等价问题,使之更易于求解。相容性技术主要有两个作用:在预处理阶段,有效的采用合理的相容性技术可以删除那些必然不属于解的值;在搜索过程中,采用相容性技术来强化网络,有助于判断搜索树的当前节点是否扩展正确。相容性技术一直是约束求解领域的热点问题。常见的相容性技术有:弧相容AC(Arc Consistency),路径相容PC(Path Consistency),最大限定路径相容max RPC(max-Restricted Path Consistency)和单弧相容SAC(Singleton Arc Consistency)等。如何利用网络当前的信息指导变量和值的实例化顺序,是启发式方法所要解决的主要问题。在约束传播的过程中如何选取后续执行相容性检查的变量值直接影响着算法的求解效率。尽早的删除不满足相容性的值化简网络,就可以在随后的约束传播过程中避免冗余的约束检查,从而提高算法的求解效率。本文首先介绍约束满足问题的相关背景知识包括常见的相容性算法,结合弧相容的回溯搜索算法MAC和在求解过程中指导搜索进程的启发式方法。由于相容性技术和启发式方法是影响约束满足问题求解效率的关键因素。本文对相容性技术中单弧相容算法进行了研究,在已有SAC3算法的基础上加入启发式的赋值策略提出改进的SAC3_avg Sup算法,具体工作如下:SAC3_avg Sup算法的主要思想为:在采用深度优先的搜索策略对约束网络进行SAC检查的过程中,采取动态启发式的策略,随着求解的不断进行,对待传播队列Qsac中的值按照变量的平均支持数(即变量的支持数/变量的论域大小)升序排序,优先赋值变量的平均支持数小的值。某一变量的平均支持数越小,其被扩充为解的可能性就越低,成为死节点的可能性就越高,故优先对其赋值,目的是提前确定死节点,从而降低算法的检查次数和执行时间。实验通过SAC3算法和本文提出的SAC3_avg Sup算法分别对标准库测试用例和随机问题测试用例进行求解,以求解所需的CPU时间,实例化过程所生成的扩展节点数和约束检查的次数作为评价标准。实验结果表明,在大多数问题中,SAC3_avg Sup算法的时间性能比SAC3算法有了显著提升,扩展节点数和约束检查的次数也有明显减少。从整体上讲,SAC3_avg Sup算法有着更出色的求解性能。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】

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

1 杜会盈;李占山;李宏博;沈海娇;;图分割在Singleton弧相容算法中的应用[J];吉林大学学报(理学版);2010年06期

2 刘春晖;朱兴军;孙吉贵;姜珊珊;;一种改进的双向singleton弧相容算法[J];吉林大学学报(工学版);2008年03期

3 ;[J];;年期

中国硕士学位论文全文数据库 前1条

1 刘明慧;基于贪心搜索的Singleton弧相容算法的研究[D];吉林大学;2016年

，

本文编号：1192579