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

《约束满足问题中基于mdd的相容性算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP181单位代码：10183研究生学号：2013532037密级：公开吉林大学硕士学位论文(学术学位)约束满足问题中基于MDD的相容性算法研究ResearchonConsistencyAlgorithmBasedonMDDinConstraintSatisfactionProblems作者姓名：李贺专业：计算机软件与理论研究方向：约束满足问题求解指导教师：李占山教授培养单位：计算机科学与技术学院2016年5月约束满足问题中基于MDD的相容性算法研究ResearchonConsistencyAlgorithmBasedonMDDinConstr

2、aintSatisfactionProblems作者姓名：李贺专业名称：计算机软件与理论指导教师：李占山教授学位类别：学术硕士答辩日期：2016年5月25日未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子版本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编等有碍作者著作权的商业性使用（但纯学术性使用不在此限）。否则，应承担侵权的法律责任。吉林大学硕±学位论文原创性声明本人郑重声明：所呈交的硕±学位论文，是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中己经注明

3、引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中明确方式标明。本人完全意识到本声明的法律结果由本人承担。力论文作者签名：沫Ｉ日期：２０．１６年＾月父日摘要摘要约束满足问题中基于MDD的相容性算法研究约束满足问题（CSP）是人工智能领域的一个重要分支，其核心是约束求解，探索高效的求解算法来提高求解效率是当前研究的主要问题。相容性技术在约束满足问题求解过程中起着举足轻重的作用，它可以在预处理阶段和搜索过程中将那些一定不能扩展成解的变量值删掉，从而减少了一些不必

4、要的搜索，并减小了搜索空间。回溯搜索是目前比较通用的一种求解技术，在对变量选择和值的选择时还可加入合适的启发式策略，在回溯过程中与相容性技术相结合，使得约束满足问题的求解变得快速、高效。目前对于约束满足问题的求解多数是针对二元约束的，而很多实际问题都涉及多个变量，因此，多元约束的求解问题受到人们日益重视。对于多元约束的求解有两种处理办法：一是将多元约束满足问题转化为二元约束满足问题，然后再利用其高效的求解算法进行求解；二是直接利用多元约束的相容性算法来进行求解，本文主要研究的是后者。多元约束的表示形式有很多种，目前常用的是将解的元组放到一个表中，而表约

5、束的压缩表示方法有多种，例如：结，多值决策图（MDD），压缩表，确定型有限自动机。当用这些复杂的数据结构表示表时，成功最关键的因素是实现的压缩率，它决定了需要空间的大小。利用多值决策图来表示多元约束可在空间上达到压缩的效果，本文就是在MDD这种结构下，根据已有的算法进行分析以及优化，具体所做工作如下：（1）对于多元约束求解算法进行介绍，针对原有的基于MDD的GAC算法进行改进，提出了mddc+算法，通过加入提前终止策略，在每一次遍历MDD以及子MDD节点过程中记录下每个变量的论域中当前已找到支持的值，若某个变量及其MDD图中下面的所有变量论域中的所有值

6、都能够找到支持，那么当前节点的子MDD就无需遍历，而是只需找到一条当前节点到终端节点的路径，这样减少了一些不必要的寻找支持的过程，并通过实验验证了其高效性。（2）在搜索图中，对于每层待扩展结点的选择，即选择变量实例化过程中加入了I摘要启发式，经过比较，本文选用的是目前应用广泛的dom/wdeg启发式，可减少整体求解所用的时间，在一定程度上提升了求解效率。本文给出了（1）、（2）两点改进的伪代码，并与原有的mddc算法和STR算法进行对比试验，比较了求解所用CPU时间和扩展节点数，通过对比试验验证了本文所做的改进在很多问题上可以提高求解效率。关键词：人工

7、智能，约束满足问题，多元约束，多值决策图IIAbstractAbstractResearchonConsistencyAlgorithmBasedonMDDinConstraintSatisfactionProblemsConstraintSatisfactionProblem(CSP)isanimportantpartoftheartificialintelligence,anditscoreistheconstraintsolving.Toexplorethemostefficientalgorithmisoneofthemajorproblems

8、ofcurrentresearchwhichisaimtoimprovethesolvinge