Talk:Look-ahead (backtracking)
![]() | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
To do
- randomness should be expanded; using it only to break ties is quite trivial application - Liberatore(T) 13:48, 7 February 2006 (UTC)
Images
What are the images supposed to show? Someone (possibly the author) should add a description. Is it a "all_distinct" problem? Now it just shows bunch of lines and really nothing understandable. —Preceding unsigned comment added by 147.251.48.140 (talk) 02:14, 7 June 2010 (UTC)
Wording
The phrase "A look-ahead technique that may be more time-consuming but may produce better results is..." has been on this page for over a decade, But...
I don't think that is accurate. One is either trying to find all the consistent answers, or the first one - but in either case there is a mathematically defined result. A result cannot be better or worse. (In case of all results, these are mathematically determined. In case of first result, any ranking is entirely external to the CSP definition and one can't rank algorithms without further discussions of goals.) All algorithms that terminate find elements of the mathematically define result set, only those or else exactly all of those. The computation time CAN be better or worse.
A better choice might be:
A look-ahead technique that may be more time-consuming in each node searched, but may require fewer overall consistency checks is based on arc consistency.
Also here is a link on the missing citation, from Artificial Intelligence, A Modern Approach. Can track a usable cictation from this I am sure: http://aima.cs.berkeley.edu/newchap05.pdf Dechter (2003) Page 137 discusses the existence of "min-conflicts" but does not show efficiency results.
Csp-interest (talk) 17:19, 14 July 2018 (UTC)
- I have changed my stance on my comment above. My technical points are correct about the way the final result set is the same no matter what the look-ahead technique. But the improvement in the search algorithm is correctly described in that the different look-ahead techniques produce "better results" in terms of the efficiency of the calculation, that is "results" refers to the improvement in efficiency. Another meaning of "better results" is a reduction in candidates that is a smaller set (though in the end only fully consistent candidates will remain). Therefore I withdraw my reccomendation. Csp-interest (talk) 12:58, 4 April 2023 (UTC)