Content deleted Content added
m moved Talk:Knuths Algorithm x to Talk:Knuth's Algorithm X: WP:RM |
→"Nondeterministic" seems misleading: new section |
||
| (16 intermediate revisions by 15 users not shown) | |||
Line 1:
{{WikiProject banner shell|
{{WikiProject Computer science}}
}}
<div class="boilerplate" style="background-color: #eeffee; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px dotted #AAAAAA;"><!-- Template:polltop -->
:''The following discussion is an archived debate of the proposal. <span style="color:red;">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section. ''
The result of the debate was '''move'''. —[[User:Nightstallion|<span style="font-variant:small-caps">Nightstallion</span>]] [[User talk:Nightstallion|''(?)'']] 08:18, 19 January 2006 (UTC)
==Requested move==
Line 15 ⟶ 21:
*'''Comment:''' This new article is part of the rewrite of the Dancing Links page, which is blatantly incorrect. --[[User:Eneg|Eneg]] 15:39, 5 January 2006 (UTC)
*'''Reply:''' Eneg: Could you please explain your concerns with the Dancing Links page? --[[User:Rob Zako|Rob Zako]] 08:03, 15 January 2006 (UTC)
*'''Reply:''' Rob Zako: That DL article was pretty bad before I rewrote it. If you're interested, just check the history. Perhaps the most notable shortcoming with that article beforehand was that it didn't discuss dancing links. [[User:
:''The above discussion is preserved as an archive of the debate. <span style="color:red;">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.''</div><!-- Template:pollbottom -->
== Reorganize Exact cover, Algorithm X and Dancing Links articles? ==
The [[exact cover]], [[Algorithm X]] and [[Dancing Links]] articles all discuss similar ideas. The exact cover problem is an [[Np_complete|NP-complete]] problem; Algorithm X is a [[brute-force]] [[algorithm]] that finds all solutions to the exact cover problem; and Dancing Links is a computer implementation of Algorithm X. These related topics have received a lot of interest recently because Dancing Links is the preferred technique for solving [[Sudoku]] puzzles quickly by computer. I suggest that all three topics be reoganized so that most of the information about concepts and examples is in the [[exact cover]] articles, with the other two articles focusing just on the particulars of the algorithm or the computer implementation. --[[User:Rob Zako|Rob Zako]] 16:54, 27 June 2006 (UTC)
== Algorithm X is the wrong name ==
Knuth uses "Algorithm X" as a temporary name for algorithms during discussion, not as actual referrable names, much as if you may say "imagine a variable x which represents the (unknown) number of articles in Wikipedia". For example, there's another "Knuth's Algorithm X" in The Art of Computer Science, third edition, page 325.
I propose that this article be renamed "Brute Force Exact Cover Algorithm" or better, just combine it with the DLX article.
:Somewhat agree. Knuth says, '''"Let's call it Algorithm X for lack of a better name"''', which definitely implies to me that he wasn't trying to actually name it. On the other hand, Algorithm X is a generally useful concept, separate from its implementation [[DLX]]. If this is to be merged, it should be merged with [[Exact Cover]]. As Knuth puts it, '''"Solving the exact cover problem: [...] Algorithm X is simply a statement of the obvious trial-and-error approach. (Indeed, I can’t think of any other reasonable way to do the job, in general.)"'''<ref>{{cite journal
| author = [[Donald Knuth|Knuth, Donald]]
| title = Dancing links
| version = P159
| year = 2000
| volume = 187
| journal = Millennial Perspectives in Computer Science
| arxiv = cs/0011047
| url = http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
| accessdate = 2006-07-11 }}</ref> [[User:Hackerb9|Ben]] ([[User talk:Hackerb9|talk]]) 10:21, 27 March 2015 (UTC)
{{reflist-talk}}
== Algorithm description slightly misleading/inaccurate? ==
At first I thought that my fellow editors were a bit sloppy in some inessentials, but upon skimming Knuth's paper from Arxiv I noticed that the same problem seems to be there, too(!). Both the article and the paper say "If the matrix A is empty, the problem is solved; terminate successfully" and "Any systematic rule for choosing column c in this procedure will find all solutions". Now consider this part in the example (sorry for the quick&dirty notation):
<pre>
The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s:
2 3 5 6
D 0 1 1 1
Thus this branch of the algorithm terminates unsuccessfully.
</pre>
However, here we were supposed to be able to pick any column, so let us pick column 3 instead. The algorithm will remove row D (and columns 3-6), which should result in an empty matrix by normal understanding, and we should get a successful result instead of failure. A remedy to this is to consider the resulting matrix as a non-empty 0x1 matrix (instead of empty 0x0 matrix), because while all rows have been removed, one column (2) wasn't ''explicitly'' removed by the algorithm.
But, then consider this new example:
<pre>
1 2
A 0 0
B 1 1
</pre>
Whichever column you pick, you end up with choosing the row B and reducing the matrix to a 1x0 matrix (because both columns get removed, but the row A doesn't). Yet this is a solution to the problem, right? So we should consider a 1x0 matrix to be empty but a 0x1 matrix to be non-empty. Everything works fine if an empty matrix is defined to be any matrix with 0 columns (and considering 0xn and nx0 matrices where n is not 0 as different from the 0x0 matrix in the first place). It is a somewhat peculiar notion of "empty", though, and I'm not quite bold enough to be sure that I've understood everything correctly on such a quick peek here. After all, it's Knuth's paper, and I don't have any citations for any of this. Hopefully someone else has the energy to look at this someday :-) -- [[User:Coffee2theorems|Coffee2theorems]] ([[User talk:Coffee2theorems|talk]]) 23:02, 4 July 2008 (UTC)
:I think the algorithm is incorrect as in missing the following rule:
: 2. If there is a column ''c'' without any 1s, terminate unsuccessfully, otherwise choose a column ''c'' ([[deterministic algorithm|deterministically]]). -- [[Special:Contributions/139.18.249.154|139.18.249.154]] ([[User talk:139.18.249.154|talk]]) 13:15, 18 October 2011 (UTC)
'''I totally agree''' — the rule should be explicitly reported in the scheme box, as the 2nd condition on which the algoritm terminates
(this time unsuccessfully). Perhaps, the best place to put it would be right after point 1 (i.e., after the successful the termination condition). While it is obvious why the algorithm should stop unsuccessfully on any matrix having an all-zero column (no complete coverage is possible in this case, since the set element represented by such column belongs to no subset), the way in which the (nice) example is worked out makes the unsuccessful termination of '''Level 1: Select Row A''' unnecessarily obscure.[[User:Banquo71|Banquo71]] ([[User talk:Banquo71|talk]]) 13:18, 12 December 2013 (UTC)
: That's a good point, but I suspect that sort of no-solution matrix (a matrix with at least one column C without any 1s) never actually occurs during normal operation, if we add the precondition:
: 1. Before starting Algorithm X, check if there is a column ''c'' without any 1s. If so, there is no solution, so don't even bother running Algorithm X.
: If that situation is checked once before starting Algorithm X, the algorithm never changes a matrix where every column has at least 1 into that sort of problematic matrix, right?
: Is "optimizing" this algorithm to do that check only once, rather than every iteration, a premature optimization? --[[User:DavidCary|DavidCary]] ([[User talk:DavidCary|talk]]) 03:49, 20 February 2016 (UTC)
==Quotation without attribution==
This article directly quotes Knuth's paper without attribution and has apparently done so [https://secure.wikimedia.org/wikipedia/en/w/index.php?title=Knuth%27s_Algorithm_X&diff=next&oldid=63012422 since 2006]. {{small|The article omits Knuth's quotes around "depth first" and one sentence in one of the quoted paragraphs.}} The text ought to be rewritten to avoid copyright problems. [[User:Michael Slone|Michael Slone]] ([[User talk:Michael Slone|talk]]) 03:35, 28 December 2009 (UTC)
== ...but why? ==
Would be interesting to see an additional section here indicating the significance of this algorithm (I can't add it as I don't know what the significance is). I assume it has a 'real world' application?
--[[User:Mortice|Mortice]] ([[User talk:Mortice|talk]]) 23:09, 18 January 2013 (UTC)
== "Nondeterministic" seems misleading ==
It is a branching recursion where all branches are explored. [[Nondeterministic algorithm]] is about something else, as far as I can tell. [[User:Ehasl|Elias]] ([[User talk:Ehasl|talk]]) 07:11, 2 April 2025 (UTC)
| |||