Live briefing
Everything about Backtracking
Algorithmic paradigm for constraint satisfaction or enumeration problems
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction or enumeration problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: BacktrackingA 5-minute orientation
- Skim a recent paper: Priority inheritance with backtracking for iterative multi-agent path findingInfluential work since 2022
- Pick up a classic book: Use of macros in backtrack programmingThe most-reprinted book on the subject
- Read the landmark paper: Backtracking Search Optimization Algorithm for numerical optimization problemsCited 581 times
- Go sideways: Brute-force searchA closely related topic
- Go sideways: Sudoku solving algorithmsA closely related topic
📖 Definitions
Noun The act of one who, or that which, backtracks; a retracing of one's steps.
Noun The usage of a runway as a taxiway, especially at private strips and smaller airports.
Noun The act of building all possible solutions to a problem incrementally, abandoning any candidate solution if it cannot lead to a valid solution.
Verb present participle and gerund of backtrack
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Backtracking Search Optimization Algorithm for numerical optimization problems
Backtracking leukemia to birth: Identification of clonotypic gene fusion sequences in neonatal blood spots
The RNA–DNA Hybrid Maintains the Register of Transcription by Preventing Backtracking of RNA Polymerase
Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
Structural basis of RNA polymerase II backtracking, arrest and reactivation
Optimal allocation of multi-type distributed generators using backtracking search optimization algorithm
Multiple learning backtracking search algorithm for estimating parameters of photovoltaic models
Backtracking by single RNA polymerase molecules observed at near-base-pair resolution
🆕 Influential since 2022
Priority inheritance with backtracking for iterative multi-agent path finding
Occurrence and backtracking of microplastic mass loads including tire wear particles in northern Atlantic air
Boosting particle swarm optimization by backtracking search algorithm for optimization problems
Deep Learning with Backtracking Search Optimization Based Skin Lesion Diagnosis Model
Design and analysis of a tracking / backtracking strategy for PV plants with horizontal trackers after their conversion to agrivoltaic plants
📚 Books worth reading
Use of macros in backtrack programmingJames Richard Bitner · 1974
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic…
- Sudoku solving algorithms A standard sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first…
- Backjumping In constraint programming and SAT solving, backjumping (also known as non-chronological backtracking or intelligent backtracking) is an enhancement for…
- Hybrid algorithm (constraint satisfaction) Within artificial intelligence and operations research for constraint satisfaction a hybrid algorithm solves a constraint satisfaction problem by the combinatio…
- Constraint programming Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer…
- Branch and bound Branch-and-bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller subproblems and using a bounding function…
- Dancing links In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for…
- Decomposition method (constraint satisfaction) In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary…