Accelerating backtrack search with a best-first-search strategy

DOI10.2478/AMCS-2014-0066MaRDI QIDQ2018417zbMATH OpenOpenAlexFDO

Authors 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)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

zbMATH Keywords

backtrackbest-first searchbranch-and-boundconstraint satisfaction problemfrequent restartingNP-hard problems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2102781
• Publication:3489496
• scientific article; zbMATH DE number 5012413
• Efficiency of randomized parallel backtrack search
• On Universal Restart Strategies for Backtracking Search
• Optimal speedup for backtrack search on a butterfly network
• Evaluation of a simple, scalable, parallel best-first search strategy
• Deterministic parallel backtrack search

Cites work

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

Cited in

(6)

• A solution to the GHI problem for best-first search
• scientific article; zbMATH DE number 5012413 (Why is no real title available?)
• On Universal Restart Strategies for Backtracking Search
• How To Be Fickle
• A hybrid graph representation for recursive backtracking algorithms
• PROGRAMMING PEARL: Enhancing a search algorithm to perform intelligent backtracking

Describes a project that uses

Uses Software

• MiniSat
• Chaff

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018417)