Talk:Backtracking
From Wikipedia, the free encyclopedia
| WikiProject Systems (Rated Start-Class) | |||||
|---|---|---|---|---|---|
 |
|||||
| Systems rating: | Start Class | Mid importance | Field: Operations research | ||
| Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article. | |||||
[edit] Plagiarism?
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 134.147.19.211
- 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)
[edit] Muddle Rationale
The rationale expressed in this article is often muddled, internally inconsistent and possibly inconsistent with related material, e.g.
- finite domain constraint programming as explained in Sudoku
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)
[edit] 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)
