Accelerating backtrack search with a best-first-search strategy

DOI10.2478/amcs-2014-0066zbMath1309.68172OpenAlexW2149352721MaRDI QIDQ2018417

Zoltán Ádám Mann, Tamás Szép

Publication date: 14 April 2015

Published in: International Journal of Applied Mathematics and Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2478/amcs-2014-0066

zbMATH Keywords

branch-and-boundconstraint satisfaction problemNP-hard problemsbacktrackbest-first searchfrequent restarting

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Uses Software

• MiniSat
• Chaff

Cites Work

• Unnamed Item
• Unnamed Item
• An agent-based model of hierarchic genetic search
• Optimal speedup of Las Vegas algorithms
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• The hardest constraint problems: A double phase transition
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Backjump-based backtracking for constraint satisfaction problems
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• Adaptive Restart Strategies for Conflict Driven SAT Solvers
• Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms
• A theoretical analysis of backtracking in the graph coloring problem
• Estimating the Efficiency of Backtrack Programs
• New methods to color the vertices of a graph
• Theory and Applications of Satisfiability Testing
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Chromatic Scheduling and the Chromatic Number Problem
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Accelerating backtrack search with a best-first-search strategy