资源论文A Reactive Strategy for High-Level Consistency During Search

A Reactive Strategy for High-Level Consistency During Search

2019-11-05 | |  53 |   50 |   0
Abstract Constraint propagation during backtrack search significantly improves the performance of solving a Constraint Satisfaction Problem. While Generalized Arc Consistency (GAC) is the most popular level of propagation, higher-level consistencies (HLC) are needed to solve difficult instances. Deciding to enforce an HLC instead of GAC remains the topic of active research. We propose a simple and effective strategy that reactively triggers an HLC by monitoring search performance: When search starts thrashing, we trigger an HLC, then conservatively revert to GAC. We detect thrashing by counting the number of backtracks at each level of the search tree and geometrically adjust the frequency of triggering an HLC based on its filtering effectiveness. We validate our approach on benchmark problems using Partition-One ArcConsistency as an HLC. However, our strategy is generic and can be used with other higher-level consistency algorithms.

上一篇:Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-sets

下一篇:A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Joint Pose and Ex...

    Facial expression recognition (FER) is a challe...