相容性方法研究及其在knapsacks约束上的应用

《相容性方法研究及其在knapsacks约束上的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP181单位代码：10183研究生学号：2013544012密级：公开吉林大学硕士学位论文（专业学位）相容性方法研究及其在knapsacks约束上的应用Researchoncompatibilitymethodanditsapplicationonknapsacksconstraints作者姓名：付兴宇类别：工程硕士领域（方向）：软件工程指导教师：李占山教授培养单位：软件学院2016年4月未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子瓶本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编

2、等有碍作者著作权的商业性使用（但纯。否则。学术性使用不在此限），应承担侵权的法律责任吉林大学硕±学位论文原创性声明本人郑重声明：所呈交学位论文，是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体Ｓ经发表或撰写过的作品成果。对本文的研巧做出重要贡献的个人和集体，均已在文中Ｗ明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者整名：日期：２０１６年＾月日摘要相容性方法研究及其在knapsacks约束上的应用约束满足问题，是人工智能领域的一个重

3、要分支。现实世界中的许多问题，如配置问题、时序推理问题、资源分配问题等实际问题，都可以用约束满足问题建模并求解。在众多的求解算法中，基于回溯的BT算法是系统完备的算法，是通过深度搜索的方式在求解空间中找到解的算法。为了加快算法的求解效率，研究人员引入了相容性技术。在目前已有的约束传播技术中，弧相容技术是最成功的。结合弧相容技术的BT算法，被称为MAC算法。弧相容算法的执行效率，严重影响MAC算法的求解效率。目前已有的实验已经表明，MAC算法中变量和值的实例化顺序，是决定MAC算法求解约束满足问题的关键因素。为了加快MAC算法的求解效率，研究人员引入了启发式技术。

4、启发式技术通过收集问题中特征信息来计算更有效的MAC算法变量实例化顺序，加快求解算法的求解效率。启发式技术按照类型分为两种：一种是变量启发式，通过变量的特征信息确定要进行实例化的变量的顺序；一种是值启发式，通过计算各个变量的各个值在解中的可能性，进而确定实例化变量的顺序，并确定实例化变量要进行实例化的值的顺序。变量启发式一般基于失败优先的原则，优先实例化容易失败的变量，进而缩减算法的搜索空间。值启发式一般是基于成功优先原则的，优先选择最可能是解的值进行实例化，期望尽早求得问题的解。目前，变量启发式的研究更加成熟，值启发式的研究更适用于一些全局约束的求解上。本文尝

5、试分析kappa启发式的优点与不足，分析kappa启发式不稳定的原因，并使用dom/wdeg启发式与kappa启发式进行组合来改进启发式的求解效率；改进knapsacks约束弧相容算法的数据结构，提高knapsacks约束弧相容算法的效率，具体工作如下：（1）分析各个启发式的优劣和不足，发现kappa启发式的特点。基于失败优先的kappa启发式能够比dom/wdeg启发式更快找到问题的解，但在问题初始化I后第一次实例化上存在着启发式失效问题。据此，提出了通过dom/wdeg启发式改进kappa启发式的组合启发式，实验结果表明，在多数问题上，组合启发式的效率能够优

6、于kappa启发式和dom/wdeg启发式。（2）通过实验，分析knapsacks约束的弧相容算法，发现算法在检查弧相容和约束传播方面耗时严重，主要原因是维护和使用算法数据结构的成本太高。通过改进算法数据结构，为弧相容算法中约束的点图添加各个变量的值的信息，改进为有向图，能够减少对knapsacks约束数据结构的维护成本，加快对整个约束的遍历速度，加快弧相容算法效率。关键词：约束满足问题，kappa启发式，knapsacks约束，弧相容IIAbstractResearchoncompatibilitymethodanditsapplicationonknapsa

7、cksconstraintsConstraintsatisfactionproblemisanimportantbranchofartificialintelligence.Manyproblemsinrealworldcanbeusedtosolvetheproblem,suchastheproblemoftheconfiguration,thetimesequenceandtheproblemoftheallocationofresources。Inmanyalgorithms,theBTalgorithmbasedonbacktrackingisacomp

8、letealgorith