Backjump-based backtracking for constraint satisfaction problems

DOI10.1016/S0004-3702(02)00120-0zbMath0995.68102OpenAlexW2021700650MaRDI QIDQ1605408

Daniel Frost, Rina Dechter

Publication date: 15 July 2002

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(02)00120-0

zbMATH Keywords

learningconstraint satisfactionbackjumpingbacktracking

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Generating effective symmetry-breaking predicates for search problems, Exploiting Past and Future: Pruning by Inconsistent Partial State Dominance, A hybrid soft computing approach for subset problems, State space search nogood learning: online refinement of critical-path dead-end detectors in planning, Accelerating backtrack search with a best-first-search strategy, AND/OR search spaces for graphical models, Implementing Efficient All Solutions SAT Solvers, Efficient solution techniques for disjunctive temporal reasoning problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arc consistency for factorable relations.
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Network-based heuristics for constraint-satisfaction problems
• Tree clustering for constraint networks
• An optimal k-consistency algorithm
• Relational consistency algorithms and their application in finding subgraph and graph isomorphisms
• A generic arc-consistency algorithm and its specializations
• Consistency in networks of relations
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• A language and a program for stating and solving combinatorial problems
• Using constraint metaknowledge to reduce arc consistency computation
• Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
• Local and global relational consistency
• A theoretical evaluation of selected backtracking algorithms.
• Networks of constraints: Fundamental properties and applications to picture processing
• A Sufficient Condition for Backtrack-Free Search
• Backtrack programming techniques
• Synthesizing constraint expressions
• GRASP: a search algorithm for propositional satisfiability
• Backtrack Programming
• A machine program for theorem-proving
• Solution techniques for constraint satisfaction problems: Foundations
• Solution techniques for constraint satisfaction problems: Advanced approaches