Knuth X 알고리즘은 Exact Cover 문제를 해결하기 위해 Donald Knuth가 고안한 알고리즘이다.
이 알고리즘은 DLX(Dancing Links) 기법을 사용하여 효율적으로 구현된 재귀적, 비결정적, 깊이 우선 역추적 알고리즘이다.
Exact Cover 문제
- U = {1, 2, 3, 4, 5, 6, 7, 8}
- S $\subset$ U = {A, B, C, D, E, F, G, H, I}
- A = {1, 4, 7}
- B = {1, 2, 3}
- C = {5}
- D = {4, 5, 6}
- E = {3, 6}
- F = {7, 8}
- G = {2, 4, 8}
- H = {3, 5, 7}
- I = {6, 8}
- 다음 조건을 만족하는 $S$의 부분 집합 $S'$ 구하는 것
<aside>
💡
조건
- $\forall S_i,S_j \in S'\ (i\neq j \Rightarrow S_i \cap S_j = \phi)$
- $\bigcup_{S_k \in S'}S_k = U$
</aside>
즉, A~F 집합을 한번씩 선택하여 U의 모든 원소가 단 한번 나타나게 하는 것.
위 문제에서는 $S' = \{B,D,F\}$가 Exact Cover문제의 해로 성립한다.
문제 해결 전략
우선 각 집합 A~F가 어떤 원소를 가지고 있으면 1, 가지고 있지 않다면 0으로 표기하여 행렬을 만든다.
이러한 행렬에서 크누스 X 알고리즘은 다음과 같은 흐름을 가진다.
<aside>
💡
알고리즘의 흐름
- 종료 조건 확인 : 행렬이 비어있다면(열이 하나도 없다면), 현재까지의 부분 해답(partial solution)은 Exact Cover문제의 해답으로 알고리즘을 종료한다
- 열(Column) 선택 : 행렬 A에서 ‘1’의 개수가 가장 적은 열(0 포함) c를 선택한다
- 만약 선택한 열 c에 ‘1’이 하나도 없다면, 이 경로로는 해답을 찾을 수 없다는 의미로 백트래킹을 한다. 모든 열에 적어도 하나의 ‘1’이 존재해야한다.
- 행(Row) 선택 (비결정적) : 2번에서 선택한 열 c에 ‘1’을 포함하는 모든 행 r에 대해 아래 4번 과정을 반복한다
- 탐색 및 커버
- 선택한 행 r을 부분 해답에 추가한다
- 행 r에 ‘1’이 있는 모든 열을 행렬에서 제거한다
- 방금 제거한 열들에 ‘1’이 있는 모든 행들을 행렬에서 제거한다
- 이렇게 축소된 새 행렬에 대해 1번부터 재귀적으로 알고리즘을 호출한다
</aside>
예시
<aside>
💡
문제 상황
- U = {1, 2, 3, 4, 5, 6, 7, 8}
- S $\subset$ U = {A, B, C, D, E, F, G, H, I}
- A = {1, 4, 7}
- B = {1, 2, 3}
- C = {5}
- D = {4, 5, 6}
- E = {3, 6}
- F = {7, 8}
- G = {2, 4, 8}
- H = {3, 5, 7}
- I = {6, 8}
</aside>
각 집합 A~F가 어떤 원소를 가지고 있으면 1, 가지고 있지 않다면 0으로 표기하여 행렬을 만든다
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| A |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
| B |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
| D |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
| E |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
| F |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
| G |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
| H |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
| I |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
열(Column) 선택 : 행렬에서 ‘1’의 개수가 가장 적은 열(0 포함) c를 선택한다
각 열이 가지는 1의 개수는 순서대로 2, 2, 3, 3, 3, 3, 3, 3이다. 1의 개수가 제일 적은 1열을 먼저 선택한다