|This is the talk page for discussing improvements to the Backtracking article.
This is not a forum for general discussion of the article's subject.
|WikiProject Systems||(Rated Start-class, Mid-importance)|
I don't know who copied from whom, maybe both from a third party even. But this article is almost identical to the Wikipedia article: http://computer-engineering.science-tips.org/algorithms/fundamentals/backtracking.html Marcus 22.214.171.124
- It looks to me like this version existed only after the Wikipedia version of similar wording. I'd bet dollars to donuts they copied the Wikipedia article. --Cheeser1 (talk) 05:20, 12 January 2008 (UTC)
The rationale expressed in this article is often muddled, internally inconsistent and possibly inconsistent with related material, e.g.
Consider the original text, before my paltry cleanup:
-- When backtracking is used in a constraint programming language, it has an added complication that the information stored about the constraints needs to be updated as well. In these languages, a simple depth first search is an adequate implementation technique, as it is in Planner and Prolog. In implementing backtracking, it is common to keep a variable trail, to record the changes in the values of a particular variable. A smart implementor will avoid creating a variable trail between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation. --
Re: The phrase 'has an added complication that the information stored' is clueless about what 'the information' is or who stores it or why it is being stored.
Similaryly, re: 'variable trail to record the changes' is totally unclear about the relationship of the 'variable trail' to the obvious state history that MUST be maintained in order to recover state when backing up.
I've cleaned up what I could, but this article needs work. Sorry, if this sounds harsh. Just trying to be specific about the confusion here. LarryLACa 11:49, 12 December 2005 (UTC)
One solution or all of them?
This article is not clear about the goal of searching, but implicitly it seems that it assumes finding one solution to the search problem (without proving its uniqueness, even if it should be) suffices (or alternatively proving that none exist). This can be seen for instance in the pseudo-code. However, there are many cases where one wants to count the number of solutions, and this is when backtracking will be used inevitably, if only to show that a solution found is unique. Think of the n queens problem. I believe the term backtracking is also used for such problems, and think the wording should be adapted to allow for this case. Marc van Leeuwen (talk) 09:31, 27 May 2008 (UTC)
Is dependency-directed backtracking (see Stallman, Richard M (1977). "Forward Reasoning and Dependency-Directed Backtracking In a System for Computer-Aided Circuit analysis". Artificial Intelligence 9. pp. 135–196. Unknown parameter
|coauthors= ignored (
|author= suggested) (help)) worth mentioning in this article and redirecting here? -- Beland (talk) 17:49, 17 August 2008 (UTC)
- Someone is also asking if this is the same as backjumping on that article's talk page. -- Beland (talk) 17:51, 17 August 2008 (UTC)
possible new technique : turbobacktracking
an algo that might "capture" the "profile" of the part of bactracking type solution might count more than one solution at a time... — Preceding unsigned comment added by 126.96.36.199 (talk) 17:59, 24 July 2011 (UTC)
Knuth and Cormen References
Although both the Knuth and Cormen references are classic books in the field of algorithms, neither deal with backtracking. On Knuth's page about The Art of Computer Programming (http://www-cs-faculty.stanford.edu/~uno/taocp.html) Backtracking is set to be talked about in Volume 4, which has not yet been released. In Cormen et al. there is no index reference to backtracking. — Preceding unsigned comment added by Sness (talk • contribs) 04:25, 7 April 2014 (UTC)
confusing and unnecessary distinction
I suggest a modification on your algorithm with four reasons:
1. I am afraid You make an unnecessary distinction between the first child and the others. Father creates the first and elder brother makes the next. The knowledge in reject(), accept() and first() is inherited from different creators. It is confusing.
2. Your interface of nodes makes possible to rewind the iteration of children. Backtrack definitely don't want that.
3. Your code can be shorter. Your interface of node can be simpler.
4. The domain of your backtrack search is restricted to tree but it could be a directed graph.
Please, check this out:
procedure bt(c) if reject(P,c) then return if accept(P,c) then output(P,c) while s ← next(P,c), s ≠ Λ do bt(s)
Your algorithm is very clear. And I think constraints should appear in your algorithm. In many case, you need adapting your data at different level, this is where backtracking happened. So need add 'changeData/restoreData' to keep track or backtrack.
if reject(P,c) then return if accept(P,c) then output(P,c) // change some data struct for next level changeData(P,c) s ← first(P,c) while s ≠ Λ do bt(s) s ← next(P,s) // restore data struct for sibling restoreData(P,c) — Preceding unsigned comment added by Moan1223 (talk • contribs) 13:35, 30 August 2016 (UTC)