表约束的相容性技术研究

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

1、分类号：TP181单位代码：10183研究生学号：2013544079密级：公开研吉林大学硕士学位论文表约束的相容性技术研究TheResearchofConsistencyAlgorithmsforTableConstraint作者姓名：王瑞伟专业：软件工程研究方向：约束处理指导教师：李占山教授培养单位：软件学院2016年4月未经本论文作者的书面授权，化法收存和保管本论女书面版本、电子械本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编等有碍作者著作权的商业性使用（但纯

2、学术性使用不在此限）。否则，应承担侵权的法律责任。吉林大学硕±学位论文原创性声明本人郑重声明，是本人在指导教师的指导下，：所呈交的硕±学位论文独立进行研究工作所取得的成果。除文中己经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体。，均已在文中臥明确方式标明本人完全意识到本声明的法律结果由本人承担。学位论文作者签名＜；王是揉１＾曰期；＾ｏ年＾月曰／（？０摘要摘要表约束的相容性技术研究对于约束可满足问题，在回溯搜索的过程中

3、应用相容性进行剪枝是最高效的完备求解算法之一。在非二元约束上，广义弧相容是目前被应用最广的相容性，同时简单表缩减算法（STR）及其优化的算法（STR2）是在表约束上维持广义弧相容最高效的算法之一。最近，新的约束表示形式dual表被提出，同时学者们给出了在dual表上维持广义弧相容的路径最优算法STR3，在不同类型的约束可满足问题实例上，STR3和STR2各有优势。在本文中，我们提出了更加高效的比特表，比特表采用比特向量来表示约束的dual表，同时我们给出在比特表上维持广义弧相容的高效算法STRbit。然后，我们通过结合比特

4、表和笛卡尔积压缩表提出比特笛卡尔积压缩表，在许多实例上，比特笛卡尔积压缩表具有很高的压缩效率，甚至能够达到1000倍的压缩效果。接着我们给出在比特笛卡尔积压缩表上维持广义弧相容的高效算法STRbit-C。在许多问题实例上，我们的算法（STRbit和STRbit-C）要比当前主流的广义弧相容算法快，主流的算法是指STR2，STR3，MDDc及其它们的压缩表版本STR2-C和STR3-C，甚至在一些问题上能够快70多倍。最近，许多关于完全成对相容（fullpair-wiseconsistency）的算法被提出，其中eSTR算法

5、是在表约束上维持的完全成对相容的高效算法之一，eSTR算法通过扩展利用STR的算法框架和维护ctr计数器使得检测约束元组的pair-wise支持的时间复杂度为O(1)，在许多问题实例上，eSTR算法要比STR算法快。eSTR算法中存在许多冗余的检测，约束的元组只需要检测可能失去pair-wise支持的相邻约束，我们维护数据结构PWsup来记录可能失去pair-wise支持的相邻约束，相应在算法中我们只需要检测在PWsup中的相邻约束。此外，约束元组检测PW支持以后，约束范围中一些变量的有效性便不需要再次检测，相应我们利用极

6、小约束范围来记录需要被检测的变量。通过利用这两种数据结构，我们能够避免许多冗余的检测，在许多问题实例上，优化后的算法比原始的eSTR算法具有更好的空间和时间效率。关键词：约束可满足问题，广义弧相容，成对相容，简单表缩减，比特向量IAbstractAbstractTheResearchofConsistencyAlgorithmsforTableConstraintOneofthemostefficientcomplementalgorithmsforsolvingconstraintsatisfactionproblemi

7、sthatusingconsistenciestoreducethesearchspaceduringbacktracksearch.Fornon-binaryconstraint,generalizedarcconsistency(GAC)isthemostcommonconsistency,andsimpletabularreduction(STR)algorithmanditsoptimizedversionSTR2arethestate-of-the-artalgorithmstomaintainGAContabl

8、econstraint.Recently,Anewconstraintrepresentation,calleddualtable,isproposed,andapath-optimalalgorithmSTR3isgiventomaintainGACondualtable,STR3isacomplem