• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Wang Ruiwei, Li Zhanshan, Li Hongbo. Optimizing eSTR Algorithm for Solving Constraint Satisfaction Problems[J]. Journal of Computer Research and Development, 2016, 53(7): 1586-1595. DOI: 10.7544/issn1000-1239.2016.20150284
Citation: Wang Ruiwei, Li Zhanshan, Li Hongbo. Optimizing eSTR Algorithm for Solving Constraint Satisfaction Problems[J]. Journal of Computer Research and Development, 2016, 53(7): 1586-1595. DOI: 10.7544/issn1000-1239.2016.20150284

Optimizing eSTR Algorithm for Solving Constraint Satisfaction Problems

More Information
  • Published Date: June 30, 2016
  • 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.
  • Cited by

    Periodical cited type(2)

    1. 王杨民,胡成玉,颜雪松,曾德泽. 面向能源感知的虚拟机深度强化学习调度算法研究. 计算机科学. 2024(02): 293-299 .
    2. 李洪刚,杜庆东,李付学. 光纤布拉格光栅传感器网络映射算法研究. 激光杂志. 2023(05): 96-101 .

    Other cited types(1)

Catalog

    Article views (1168) PDF downloads (621) Cited by(3)
    Turn off MathJax
    Article Contents

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return