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

来源：计算机研究与发展杂志2016年第7期北京时间：

作者：王瑞伟,李占山,李宏博,

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

关键词：高阶相容, 极小约束范围, 约束网络, PW\+{sup}数据结构, PWC+GAC,