Knuth's Algorithm X: Difference between revisions

Revision as of 07:58, 10 July 2006

Revision as of 08:10, 10 July 2006

Line 17:

Algorithm X functions as follows:

: If the matrix ''A'' is empty, the problem is solved; terminate successfully.

:{| border="1" cellpadding="5" cellspacing="0"

: Otherwise choose a column ''c'' ([[deterministic algorithm|deterministically]]).

|

: Choose a row ''r'' such that ''A''[''r'', ''c''] = 1 ([[nondeterministic algorithm|nondeterministically]]).

:# If the matrix ''A'' is empty, the problem is solved; terminate successfully.

: Include row ''r'' in the partial solution.

:# Otherwise choose a column ''c'' ([[deterministic algorithm|deterministically]]).

: For each column ''j'' such that ''A''[''r'', ''j''] = 1,

:# Choose a row ''r'' such that ''A''[_{''r'', ''c'']} = 1 ([[nondeterministic algorithm|nondeterministically]]).

:: delete column ''j'' from matrix ''A'';

::# for eachInclude row ''ir'' suchin that ''A''[''i'', ''j'']the =partial 1,solution.

:::# deleteFor roweach column ''ij'' fromsuch matrixthat ''A''._{''r'', ''j''} = 1,

#: Repeatdelete thiscolumn algorithm recursively on the''j'' reducedfrom matrix ''A''.;

#: Forfor each columnrow ''ji'' such that ''A''[_{''ri'', ''j'']} = 1,

#:: delete columnrow ''ji'' from matrix ''A'';.

# Repeat this algorithm recursively on the reduced matrix ''A''.

|}

To reduce the number of iterations, [[Donald Knuth|Knuth]] suggests that the column choosing algorithm select a column with the lowest number of 1s in it.