backtracking en · NOUN
Pronunciation
- /ˈbæk.tɹækɪŋ/ (General-American)
- (US) audio
Meanings
- (countable, uncountable) The act of one who, or that which, backtracks; a retracing of one's steps.
- (countable, uncountable) The usage of a runway as a taxiway, especially at private strips and smaller airports.
-
(countable, uncountable) The act of building all possible solutions to a problem incrementally, abandoning any candidate solution if it cannot lead to a valid solution.
This grammar only uses tokens and rules, so there is no backtracking involved, and the grammar is a predictive parser. This is fairly typical. Many grammars work fine without backtracking, or with backtracking in just a few places.
2017, Moritz Lenz, Parsing with Perl 6 Regexes and Grammars, Apress, →ISBN, page 112:backtracking algorithm
Backtracking is used to solve problems in which a sequence of objects is chosen from a specific set so that the sequence satisfies some criterion. The classic example of the use of backtracking is the n-Queens problem.
2004, Richard E. Neapolitan, Kumarss Naimipour, Foundations of Algorithms Using C++ Pseudocode, 3rd edition, Jones & Bartlett Learning, →ISBN, page 188:
Forms
| Spelling | Features | Labels | Source |
|---|---|---|---|
| backtrackings | Number=Plur | lexicographic |
Deriveds
runaway backtracking · nonbacktracking · catastrophic backtracking
Translations (3)
pl algorytm z nawrotami (computer science: building all solutions and abandoning any if it cannot lead to a valid one) · eo malavanco (computer science: building all solutions and abandoning any if it cannot lead to a valid one) · es vuelta atrás (computer science: building all solutions and abandoning any if it cannot lead to a valid one)