求解约束可满足问题的eSTR算法优化

摘要：

表约束方法是1种外延式知识表示方法，每个约束通过元组集直接枚举出其在1个变量集上允许或禁止的所有元组，直观易于理解，在约束程序中得到了深入的研究，这是因为表约束出现在如设计、数据库、配置以及偏好建模等许多现实世界的应用中．但随着约束的增多及其元组集增大，占有的空间与相容性检测效率成了关键问题．eSTR是1个将STR扩展到高阶相容的算法，通过深入分析eSTR算法后发现有2种优化方式：PWsup数据结构和极小约束范围，同时证明了在极小约束范围上，约束网络仍然能够维持PWC＋GAC ，其中极小约束范围可以通过删除约束元组集中相应的列来降低eSTR2算法的空间消耗，而 PWsup数据结构能够通过避免不必要的PW 支持检测来减少eSTR2的CPU 运行时间，实验结果表明：2种优化方式和eSTR2相结合后能够同时减少算法的空间消耗和CPU 运行时间，在许多类实例上明显优于eS T R2和eS T R2w ．

关键词：高阶相容、极小约束范围、约束网络、PWsup数据结构、PWC+GAC

所属期刊栏目：53

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目61170314，61272208；吉林省自然科学基金项目20140101200JC This work was supported by the National Natural Science Foundation of China61170314，61272208;the Natural Science Foundation of Jilin Province of China 20140101200JC．

在线出版日期：2016-08-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1586-1595