Optimizing eSTR Algorithm for Solving Constraint Satisfaction Problems
-
摘要: 表约束方法是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
Abstract: Table constraints, i.e., constraints given in extension by listing all allowed (or forbidden) tuples, are very straight forward and easy to understand, which are intensively studied in constraint programming (CP). Because such constraints are presented in many real world applications from areas such as design, databases, configuration and preferences modeling. However, With the growth of number of constraints and number of tuples, the space cost for table constraints and time cost of consistency checking have become key topics. eSTR is an algorithm which extends simple tabular reduction (STR) to higher-order consistency. After in-depth analysis of eSTR algorithm, this paper proposes two kinds of optimized methods for eSTR: PW\+{sup} data structure and minimal constraint scope, and then we prove that the constraint network enforce Pair-Wise Consistency and Generalized Arc-Consistency (PWC+GAC) with minimal constraint scope is equivalent to original constraint scope. At the same time, minimal constraint scope can reduce further space cost of eSTR2 algorithm by deleting columns of the tables in constraints, and PW\+{sup} data structure can reduce the CPU running time by avoiding some unnecessary checking of Pair-Wise-support (PW-support), since tuples in table of the constraint may not lose any PW-supports on the tables of other neighbour constraints. The experimental results show that combining our methods with eSTR2 algorithm can obviously outperform eSTR2 and eSTR2w on many instances of different problems, since it reduces the space cost and CPU running time of eSTR algorithm. -
计量
- 文章访问数: 1167
- HTML全文浏览量: 0
- PDF下载量: 621
下载:
