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

《基于贪心搜索的singleton弧相容算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP181单位代码：10183研究生学号：2013532042密级：公开吉林大学硕士学位论文(学术学位)基于贪心搜索的Singleton弧相容算法的研究ResearchontheSingletonArcConsistencyBasedonGreedyApproach作者姓名：刘明慧专业：计算机软件与理论研究方向：约束求解指导教师：李占山教授培养单位：计算机科学与技术学院2016年5月未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子版本的任何革位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编等有碍作者著作权的商业性使用（但纯学

2、术性使用不在此限）。否则应承担侵权的法律责任。，吉林大学硕±学位论文原创性声明本人郑重声明：所呈交的硕±学位论文，是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中己经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成。果对本文的研巧做出重要贡献的个人和集体，均己在文中Ｗ明确方。本人完全意识到本声明的法律结果由本人承担式标明。学位论文作者签名：别崎您＂日期：２０１６年５月巧日基于贪心搜索的Singleton弧相容算法的研究ResearchontheSingletonArcConsistencyBasedonGree

3、dyApproach作者姓名：刘明慧专业名称：计算机软件与理论指导教师：李占山教授学位类别：学术硕士答辩日期：2016年5月25日摘要摘要基于贪心搜索的Singleton弧相容算法的研究约束满足问题是人工智能领域的一个重要分支，其表示形式可以形象的对现实世界中的问题进行建模，从而将问题抽象为约束满足问题的模型进行求解，已经广泛的应用于配置，调度，规划，网络以及生物信息学等诸多领域。求解一个约束满足问题，是指为其找到一个解或者证明其无解。约束满足问题的求解往往结合使用搜索和推理的方法。搜索技术用于遍历问题中所有变量的当前论域来寻找解。推理技术通过变量消元，树分解和相容性技术将问题转化为一个等

4、价问题，使之更易于求解。相容性技术主要有两个作用：在预处理阶段，有效的采用合理的相容性技术可以删除那些必然不属于解的值；在搜索过程中，采用相容性技术来强化网络，有助于判断搜索树的当前节点是否扩展正确。相容性技术一直是约束求解领域的热点问题。常见的相容性技术有：弧相容AC(ArcConsistency)，路径相容PC(PathConsistency)，最大限定路径相容maxRPC(max-RestrictedPathConsistency)和单弧相容SAC(SingletonArcConsistency)等。如何利用网络当前的信息指导变量和值的实例化顺序，是启发式方法所要解决的主要问题。在约

5、束传播的过程中如何选取后续执行相容性检查的变量值直接影响着算法的求解效率。尽早的删除不满足相容性的值化简网络，就可以在随后的约束传播过程中避免冗余的约束检查，从而提高算法的求解效率。本文首先介绍约束满足问题的相关背景知识包括常见的相容性算法，结合弧相容的回溯搜索算法MAC和在求解过程中指导搜索进程的启发式方法。由于相容性技术和启发式方法是影响约束满足问题求解效率的关键因素。本文对相容性技术中单弧相容算法进行了研究，在已有SAC3算法的基础上加入启发式的赋值策略提出改进的SAC3_avgSup算法，具体工作如下：SAC3_avgSup算法的主要思想为：在采用深度优先的搜索策略对约束网络进行S

6、AC检查的过程中，采取动态启发式的策略，随着求解的不断进行，对待传播队列Qsac中的值按照变量的平均支持数（即变量的支持数/变量的论域大小）升序排序，优先赋值变量的平均支持数小的值。某一变量的平均支持数越小，其I摘要被扩充为解的可能性就越低，成为死节点的可能性就越高，故优先对其赋值，目的是提前确定死节点，从而降低算法的检查次数和执行时间。实验通过SAC3算法和本文提出的SAC3_avgSup算法分别对标准库测试用例和随机问题测试用例进行求解，以求解所需的CPU时间，实例化过程所生成的扩展节点数和约束检查的次数作为评价标准。实验结果表明，在大多数问题中，SAC3_avgSup算法的时间性能比

7、SAC3算法有了显著提升，扩展节点数和约束检查的次数也有明显减少。从整体上讲，SAC3_avgSup算法有着更出色的求解性能。关键词：约束满足问题，Singleton弧相容，启发式方法IIAbstractAbstractResearchontheSingletonArcConsistencyBasedonGreedyApproachConstraintsatisfactionproblemisanimportantbra