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

《交互约束满足问题的冲突解释算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP311.5单位代码：10183研究生学号：2013544083密级：公开吉林大学硕士学位论文（专业学位）交互约束满足问题的冲突解释算法研究ResearchonConflictExplanationAlgorithminInteractiveConstraintSatisfactionProblem作者姓名：王旭类别：工程硕士领域（方向）：软件工程指导教师：杨凤杰副教授培养单位：软件学院2016年4月交互约束满足问题的冲突解释算法研究ResearchonConflictExplanationAlgor

2、ithminInteractiveConstraintSatisfactionProblem作者姓名：王旭领域（方向）：软件工程指导教师：杨凤杰副教授类别：工程硕士答辩日期：2016年5月28日未经本论文作者的书面授权依法收存和保管本论文书面，版本、电子版本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编等有碍作者著作权的商业性使用（但纯学术性使用不在此限）。否则，应承担侵权的法律责任。吉林大学硕±学位论文原创性声明本人郑重声明：所呈交的硕±学位

3、论文，是本人在指导教师的指导下，独立进行研巧工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研巧做出重要贡献的个人和集体，均己在文中明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：３日期：２０１６年５月２８日摘要交互约束满足问题的冲突解释算法研究约束满足问题是人工智能领域的一个重要分支，其表示形式是一个很好的框架，可以用来表示一系列现实问题，例如：配置问题，航班调度，资源分配等。约束传播和回溯搜

4、索是约束满足问题的两个主要技术。交互约束满足是一种特殊的约束满足问题，交互约束满足问题是指在计算开始时问题模型还没有被完整定义，但是可以在计算过程中交互的传递信息。在交互约束满足问题求解过程中用户指定一些约束，这些用户约束代表着用户的需求。求解解释是交互约束满足问题中的一个研究热点。解释可以用于恢复相容性、避免不受欢迎的特性或者恢复一个已经排除的特性。目前的求解解释算法主要分两类：基于解的解释算法和基于冲突的解释算法。基于解的解释算法是修正用户约束集合的一个子集，使约束网络能够得到一个解；基于冲突的解释算法是给

5、出导致约束网络不相容的一个子集，说明冲突产生的原因，通常来说我们要求该子集是一个极小集合。BarryO'Callaghan的CorrectiveExp和Junker的QUICKXPLAIN是两类算法的代表。QUICKXPLAIN算法将问题域划分为两部分，运用递归的方式分别求解两个部分的冲突元素。QUICKXPLAIN算法的时间开销主要是在约束传播上，若能减少约束传播的次数和每次约束传播的时间，即可提高算法的运行效率。本文基于QUICKPLAIN算法提出了基于捆绑的冲突解释算法，即将m个约束捆绑为一个约束进行约束

6、传播，m的取值范围是1-n，其中n为用户约束的个数；m取值为1时，即是QUICKXPLAIN算法本身。本文对m=2和m=n/2两种情况进行了研究：（1）当m=2时，我们采用将两个约束捆绑为一个的方式进行约束传播，我们将该算法称为基于双值捆绑的冲突解释算法。该算法可以使两个用户约束共用一次约束传播的过程，这样使得约束传播的次数可变为原来的二分之一；但是当一次约束传播导致冲突时，需要做额外的工作来判断两个被捆绑的约束中到底哪个是冲突元素（有可能是其中之一，也有可能两者均是）。（2）当m=n/2时，我们采用将用户约束

7、集合的二分之一捆绑为一个的方式进行约束传播，我们将该算法称为基于折半捆绑的冲突解释算法。该算法将用户约束分成两部分，按照两个约束的方式来判断冲突集合所在的位置；然后运用递归的方式分别在两个子问题中求解冲突集合，直到子问题中只包含一个约束时即I为冲突集合中的元素。通过这种方式可以将问题域减小为原来的二分之一，并且多个约束同时传播，可在一定程度上减少每次约束传播的时间。理论上，根据用户约束集合和冲突约束集合的大小不同，我们不能保证哪一算法在所有情况下都是最优的。但是实验结果显示，在实际问题中，我们提出的两种算法效率

8、均高于QUICKXPLAIN算法，其中大多数情况下基于折半捆绑的冲突解释算法的效率高于基于双值捆绑的冲突解释算法。关键词：交互约束满足问题，冲突解释算法，捆绑IIAbstractResearchonConflictExplanationAlgorithminInteractiveConstraintSatisfactionProblemConstraintSatisfactionPro