Backjump-based backtracking for constraint satisfaction problems

DOI10.1016/S0004-3702(02)00120-0zbMath0995.68102MaRDI 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

learning; constraint satisfaction; backjumping; backtracking

Mathematics Subject Classification ID

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

Related Items

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

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