王瑞伟　李占山　李宏博

1(符号计算与知识工程教育部重点实验室(吉林大学)　长春　130012)2(吉林大学计算机科学与技术学院　长春　130012)3　　　(吉林大学软件学院　长春　130012)



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

王瑞伟1,3李占山1,2,3李宏博1,2

1(符号计算与知识工程教育部重点实验室(吉林大学)长春130012)2(吉林大学计算机科学与技术学院长春130012)3(吉林大学软件学院长春130012)

(120801104@qq.com)

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

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

作为人工智能一个主要研究分支的约束程序(constraint programming， CP) 兴起于20世纪80年代末期，1996年美国计算机学会(Association for Computing Machinery, ACM) 在庆祝其……