Knuth's Algorithm X: Difference between revisions

Revision as of 03:14, 6 May 2006

Revision as of 07:58, 10 July 2006

Line 17:

Algorithm X functions as follows:

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

# Using any [[deterministic algorithm]], choose a column, c.

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

# Nondeterministically branch, choosing any row, r, which has a 1 in column c, and add that row to the solution set.

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

# Remove any unselected rows which have a 1 in any column which r has a 1 in.

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

# Remove from the matrix any columns for which row r has a 1.

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

# Repeat the algorithm on this reduced matrix.

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

:: for each row ''i'' such that ''A''[''i'', ''j''] = 1,

::: delete row ''i'' from matrix ''A''.

#: Repeat thethis algorithm recursively on thisthe reduced matrix ''A''.

When the matrix is empty, you have a solution. 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.

The example above is solved as follows, using 0 based notation: