Wikipedia

Knuth's Algorithm X: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Rob Zako (talk | contribs)
328 edits
→Example: Illustrate operation of algorithm step-by-step with matrices.
Line 63:
'''Level 0'''
 
Step 1—The matrix is not empty, so the algorithm proceeds.
The lowest number of 1s in any column is two and column 1 is the first column with two 1s, thus column 1 is selected (deterministically).
 
RowsStep ''A''2—The andlowest ''B''number eachof have1s ain any column is two. Column 1 inis the first column 1with two 1s and thus areis selected (nondeterministicallydeterministically).:
 
:{| border="1" cellpadding="5" cellspacing="0"
The algorithm moves to the first branch at level 1.
! !! <span style="color:red">1</span> !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
! ''A''
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 1 || 0 || 0 || 1
|-
! ''B''
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 1 || 0 || 0 || 0
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
Step 3—Rows ''A'' and ''B'' each have a 1 in column 1 and thus are selected (nondeterministically).
 
The algorithm moves to the first branch at level 1…
 
: '''Level 1: Select Row ''A'''''
 
: Step 4—Row ''A'' is included in the partial solution.
: Row ''A'' has a 1 in columns 1, 4, and 7. Column 1 has a 1 in rows ''A'' and ''B''; column 4 has a 1 in rows ''A'', ''B'', and ''C''; and column 7 has a 1 in rows ''A'', ''C'', ''E'', and ''F''. Thus rows ''A'', ''B'', ''C'', ''E'', and ''F'' are removed and columns 1, 4 and 7 are removed. Row ''D'' remains and columns 2, 3, 5, and 6 remain:
 
: Step 5—Row ''A'' has a 1 in columns 1, 4, and 7:
 
::{| border="1" cellpadding="5" cellspacing="0"
! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! <span style="color:blue">7</span>
|-
! <span style="color:red">''A''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span>
|-
! ''B''
| 1 || 0 || 0 || 1 || 0 || 0 || 0
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
: Column 1 has a 1 in rows ''A'' and ''B''; column 4 has a 1 in rows ''A'', ''B'', and ''C''; and column 7 has a 1 in rows ''A'', ''C'', ''E'', and ''F''. Thus rows ''A'', ''B'', ''C'', ''E'', and ''F'' are to be removed and columns 1, 4 and 7 are to be removed:
 
::{| border="1" cellpadding="5" cellspacing="0"
! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! <span style="color:red">7</span>
|-
! <span style="color:blue">''A''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span>
|-
! <span style="color:blue">''B''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 0
|-
! <span style="color:blue">''C''</span>
| 0 || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 1 || 0 || <span style="color:red;font-weight:bold">1</span>
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! <span style="color:blue">''E''</span>
| 0 || 1 || 1 || 0 || 0 || 1 || <span style="color:red;font-weight:bold">1</span>
|-
! <span style="color:blue">''F''</span>
| 0 || 1 || 0 || 0 || 0 || 0 || <span style="color:red;font-weight:bold">1</span>
|}
 
: Row ''D'' remains and columns 2, 3, 5, and 6 remain:
 
::{| border="1" cellpadding="5" cellspacing="0"
Line 80 ⟶ 154:
|}
 
: Step 1—The matrix is not empty, so the algorithm proceeds.
: The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s, thus this branch of the algorithm terminates unsuccessfully.
 
: Step 2—The lowest number of 1s in any column is zero and column 2 is the first column with zero 1s:
: The algorithm moves to the next branch at level 1.
 
::{| border="1" cellpadding="5" cellspacing="0"
! !! <span style="color:red">2</span> !! 3 !! 5 !! 6
|-
! ''D''
| 0 || 1 || 1 || 1
|}
: Thus this branch of the algorithm terminates unsuccessfully.
 
: The algorithm moves to the next branch at level 1…
 
: '''Level 1: Select Row ''B'''''
 
: Step 4—Row ''B'' is included in the partial solution.
: Row ''B'' has a 1 in columns 1 and 4. Column 1 has a 1 in rows ''A'' and ''B''; and column 4 has a 1 in rows ''A'', ''B'', and ''C''. Thus rows ''A'', ''B'', and ''C'' are removed and columns 1 and 4 are removed. Rows ''D'', ''E'', and ''F'' remain and columns 2, 3, 5, 6, and 7 remain:
 
: Row ''B'' has a 1 in columns 1 and 4:
 
::{| border="1" cellpadding="5" cellspacing="0"
! !! <span style="color:blue">1</span> !! 2 !! 3 !! <span style="color:blue">4</span> !! 5 !! 6 !! 7
|-
! ''A''
| 1 || 0 || 0 || 1 || 0 || 0 || 1
|-
! <span style="color:red">''B''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 0
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
: Column 1 has a 1 in rows ''A'' and ''B''; and column 4 has a 1 in rows ''A'', ''B'', and ''C''. Thus rows ''A'', ''B'', and ''C'' are to be removed and columns 1 and 4 are to be removed:
 
::{| border="1" cellpadding="5" cellspacing="0"
! !! <span style="color:red">1</span> !! 2 !! 3 !! <span style="color:red">4</span> !! 5 !! 6 !! 7
|-
! <span style="color:blue">''A''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 1
|-
! <span style="color:blue">''B''</span>
| <span style="color:red;font-weight:bold">1</span> || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 0 || 0 || 0
|-
! <span style="color:blue">''C''</span>
| 0 || 0 || 0 || <span style="color:red;font-weight:bold">1</span> || 1 || 0 || 1
|-
! ''D''
| 0 || 0 || 1 || 0 || 1 || 1 || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! ''F''
| 0 || 1 || 0 || 0 || 0 || 0 || 1
|}
 
: Rows ''D'', ''E'', and ''F'' remain and columns 2, 3, 5, 6, and 7 remain:
 
::{| border="1" cellpadding="5" cellspacing="0"
Line 101 ⟶ 235:
|}
 
: Step 1—The matrix is not empty, so the algorithm proceeds.
: The lowest number of 1s in any column is one and column 5 is the first column with one 1, thus column 5 is selected (deterministically).
 
: RowStep ''D''2—The haslowest anumber 1of 1s in any column is one. Column 5 is the first column with one 1 and thus is selected (nondeterministicallydeterministically).:
 
::{| border="1" cellpadding="5" cellspacing="0"
: The algorithm moves to the first branch at level 2.
! !! 2 !! 3 !! <span style="color:red">5</span> !! 6 !! 7
|-
! ''D''
| 0 || 1 || <span style="color:red;font-weight:bold">1</span> || 1 || 0
|-
! ''E''
| 1 || 1 || 0 || 1 || 1
|-
! ''F''
| 1 || 0 || 0 || 0 || 1
|}
 
: Step 3—Row ''D'' has a 1 in column 5 and thus is selected (nondeterministically).
 
: The algorithm moves to the first branch at level 2…
 
:: '''Level 2: Select Row ''D'''''
 
:: Step 4—Row ''D'' is included in the partial solution.
:: Row ''D'' has a 1 in columns 3, 5, and 6. Column 3 has a 1 in rows ''D'' and ''E''; column 5 has a 1 in row ''D''; and column 6 has a 1 in rows ''D'' and ''E''. Thus rows ''D'' and ''E'' are removed and columns 3, 5, and 6 are removed. Row ''F'' remains and columns 2 and 7 remain:
 
:: Step 5—Row ''D'' has a 1 in columns 3, 5, and 6:
 
:::{| border="1" cellpadding="5" cellspacing="0"
! !! 2 !! <span style="color:blue">3</span> !! <span style="color:blue">5</span> !! <span style="color:blue">6</span> !! 7
|-
! <span style="color:red">''D''</span>
| 0 || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || 0
|-
! ''E''
| 1 || 1 || 0 || 1 || 1
|-
! ''F''
| 1 || 0 || 0 || 0 || 1
|}
 
:: Column 3 has a 1 in rows ''D'' and ''E''; column 5 has a 1 in row ''D''; and column 6 has a 1 in rows ''D'' and ''E''. Thus rows ''D'' and ''E'' are to be removed and columns 3, 5, and 6 are to be removed:
 
:::{| border="1" cellpadding="5" cellspacing="0"
! !! 2 !! <span style="color:red">3</span> !! <span style="color:red">5</span> !! <span style="color:red">6</span> !! 7
|-
! <span style="color:blue">''D''</span>
| 0 || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span> || 0
|-
! <span style="color:blue">''E''</span>
| 1 || <span style="color:red;font-weight:bold">1</span> || 0 || <span style="color:red;font-weight:bold">1</span> || 1
|-
! ''F''
| 1 || 0 || 0 || 0 || 1
|}
 
:: Row ''F'' remains and columns 2 and 7 remain:
 
:::{| border="1" cellpadding="5" cellspacing="0"
Line 118 ⟶ 299:
|}
 
:: Step 1—The matrix is not empty, so the algorithm proceeds.
:: The lowest number of 1s in any column is one and column 2 is the first column with one 1s, thus column 2 is selected (deterministically).
 
:: Step 2—The lowest number of 1s in any column is one. Column 2 is the first column with one 1 and thus is selected (deterministically).
 
:: Row ''F'' has a 1 in column 2 and thus is selected (nondeterministically).
 
:: The algorithm moves to the first branch at level 3.3…
 
::: '''Level 3: Select Row ''F'''''
 
::: Step 4—Row ''F'' is included in the partial solution.
::: Row ''F'' has a 1 in columns 2 and 7. Column 2 has a 1 in row ''F''; and column 7 has a 1 in row ''F''. Thus row ''F'' is removed and columns 2 and 7 are removed. The matrix is empty, thus this branch of the algorithm terminates successfully.
 
::: Row ''F'' has a 1 in columns 2 and 7:
 
::::{| border="1" cellpadding="5" cellspacing="0"
! !! <span style="color:blue">2</span> !! <span style="color:blue">7</span>
|-
! <span style="color:red">''F''</span>
| <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span>
|}
 
::: Column 2 has a 1 in row ''F''; and column 7 has a 1 in row ''F''. Thus row ''F'' is is to removed and columns 2 and 7 are to be removed:
 
::::{| border="1" cellpadding="5" cellspacing="0"
! !! <span style="color:red">2</span> !! <span style="color:red">7</span>
|-
! <span style="color:blue">''F''</span>
| <span style="color:red;font-weight:bold">1</span> || <span style="color:red;font-weight:bold">1</span>
|}
 
::: Step 1—The matrix is empty, thus this branch of the algorithm terminates successfully.
 
::: As rows ''B'', ''D'', and ''F'' are selected, the final solution is:
Line 145 ⟶ 348:
::: In other words, the subcollection {''B'', ''D'', ''F''} is an exact cover, since every element is contained in exactly one of the sets ''B'' = {1, 4}, ''D'' = {3, 5, 6}, or ''F'' = {2, 7}.
 
::: There are no more selected rows at level 3, thus the algorithm moves to the next branch at level 2.2…
 
:: There are no more selected rows at level 2, thus the algorithm moves to the next branch at level 1.1…
 
: There are no more selected rows at level 1, thus the algorithm moves to the next branch at level 0.0…
 
TheThere are no branches at level 0, thus the algorithm is complete.
 
In summary, the algorithm determines there is only one exact cover: <math>\mathcal{S}^*</math> = {''B'', ''D'', ''F''}.
Retrieved from "https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X"