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