크누스의 알고리즘 X

알고리즘 X는 정확한 커버 문제를 해결하기 위한 알고리즘이다.도날드 크누스가 댄싱 링크 기법을 사용하는 DLX라는 효율적인 구현을 시연하기 위해 사용하는 간단한 재귀성, 비결정성, 깊이 우선의 역추적 알고리즘이다.^[1]

정확한 커버 문제는 알고리즘 X에 0s와 1s로 구성된 매트릭스 A로 표시된다.목표는 각 열에 숫자 1이 정확히 한 번 나타나도록 행의 하위 집합을 선택하는 것이다.

알고리즘 X는 다음과 같이 기능한다.

# 매트릭스 A에 열이 없는 경우, 현재의 부분 솔루션은 유효한 솔루션이며, 성공적으로 종료된다.
그렇지 않으면 c 열을 선택하십시오(결정적으로).

A_{r, c} = 1(비정규적으로)과 같은 행 r을 선택하십시오.

부분 용액에 r 행을 포함하십시오.

A_{r, j} = 1과 같은 각 열 j에 대해,
A_{i, j} = 1과 같은 각 행 i에 대해,
행렬 A에서 행 i를 삭제한다.

행렬 A에서 열 j를 삭제한다.

감소된 매트릭스 A에 대해 이 알고리즘을 반복한다.

r의 비결정론적 선택은 알고리즘이 독립적인 하위 알고리즘에 대해 반복된다는 것을 의미한다. 각 하위 알고리즘은 현재 행렬 A를 상속하지만 다른 행 r에 대해서는 이를 감소시킨다.c 열이 완전히 0이면 하위 알고리즘이 없고 프로세스가 성공적으로 종료되지 않는다.

서브알고리즘은 원래 문제가 근본에 있고 레벨 k가 선택된 행에 해당하는 각 서브알고리즘을 포함하는 자연적인 방법으로 검색 트리를 형성한다.역추적이란 먼저 나무를 선주문, 깊이부터 가로지르는 과정이다.

이 절차에서 c 컬럼을 선택하기 위한 어떤 체계적인 규칙은 모든 해결책을 찾을 것이지만, 어떤 규칙은 다른 규칙보다 훨씬 더 잘 작동한다.Knuth는 반복 횟수를 줄이기 위해 컬럼 선택 알고리즘이 가장 적은 1s의 열을 선택할 것을 제안한다.

예

예를 들어 우주 U = {1, 2, 3, 4, 5, 6, 7} 및 ${\mathcal {S}}$ ${\$ ${\mathcal {S}}$ = {A, B, C, D, E, F} 집합에서 지정한 정확한 커버 문제를 고려하십시오. 여기서:

A = {1, 4, 7};
B = {1, 4};
C = {4, 5, 7};
D = {3, 5, 6};
E = {2, 3, 6, 7} 및
F = {2, 7}.

이 문제는 다음 행렬로 나타난다.

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
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

Knuth가 제안하는 칼럼 선택용 휴리스틱을 가진 알고리즘 X는 다음과 같이 이 문제를 해결한다.

레벨 0

1단계—매트릭스가 비어 있지 않으므로 알고리즘이 계속 진행하십시오.

2단계—모든 열에서 가장 낮은 1초 수는 2이다.1열은 두 개의 1초를 가진 첫 번째 열이므로 (결정적으로) 선택된다.

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
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

3단계—A열과 B열은 각각 1열로 되어 있으므로(비교적) 선택된다.

알고리즘은 레벨 1에서 첫 번째 분기로 이동한다.

레벨 1: A행 선택

4단계—A행은 부분 솔루션에 포함되어 있다.

5단계—A열은 1, 4, 7열에 1이 있음:

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
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

1열은 A열과 B열에 1이 있고, 4열은 A열, B열, C열에 1이 있으며, 7열은 A열, C열, E열, F열에 1이 있다.따라서 A, B, C, E, F 행을 제거하고 1, 4, 7 열을 제거한다.

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
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

D행은 남고 2, 3, 5, 6열은 남는다.

	2	3	5	6
D	0	1	1	1

1단계—매트릭스가 비어 있지 않으므로 알고리즘이 계속 진행하십시오.

2단계—모든 열의 최저 1초 수는 0이고 2열은 0초인 첫 번째 열:

	2	3	5	6
D	0	1	1	1

따라서 알고리즘의 이 분기는 성공적으로 종료되지 않는다.

알고리즘은 레벨 1에서 다음 분기로 이동한다.

레벨 1: B행 선택

4단계—B행은 부분 용액에 포함된다.

B행은 1열과 4열에 1이 있다.

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
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

1열은 A열과 B열에 1이 있고, 4열은 A열, B열, C열에 1이 있다.따라서 A, B, C 행을 제거하고 1열과 4열을 제거한다.

	1	2	3	4	5	6	7
A	1	0	0	1	0	0	1
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

D, E, F 행은 남고 2, 3, 5, 6 및 7 열은 남는다.

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

1단계—매트릭스가 비어 있지 않으므로 알고리즘이 계속 진행하십시오.

2단계—모든 열에서 가장 낮은 1초 수는 1이다.5열은 1이 1인 첫 번째 열이므로(결정적으로):

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

3단계—D행은 5열에 1이 있으므로 (비정상적으로) 선택된다.

알고리즘은 레벨 2에서 첫 번째 분기로 이동한다.

레벨 2: D행 선택

4단계—D행은 부분 솔루션에 포함되어 있다.

5단계—D행 3, 5, 6열에 1이 있음:

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

3열은 D열과 E열에 1이 있고, 5열은 D열에 1이 있으며, 6열은 D열과 E열에 1이 있다.따라서 D행과 E행은 제거되고 3, 5, 6열은 제거된다.

	2	3	5	6	7
D	0	1	1	1	0
E	1	1	0	1	1
F	1	0	0	0	1

F열은 남고 2열과 7열은 남는다.

	2	7
F	1	1

1단계—매트릭스가 비어 있지 않으므로 알고리즘이 계속 진행하십시오.

2단계—모든 열에서 가장 낮은 1초 수는 1이다.2열은 1이 1인 첫 번째 열이므로 (결정적으로) 선택된다.

F행은 2열에 1이 있으므로 (비교적으로) 선택된다.

알고리즘은 레벨 3에서 첫 번째 분기로 이동한다.

레벨 3: F행 선택

4단계—F행은 부분 솔루션에 포함되어 있다.

F행은 2열과 7열에 1이 있다.

	2	7
F	1	1

2열은 F열에 1개, 7열은 F열에 1개 있다.따라서 F열은 제거되고 2열과 7열은 제거된다.

	2	7
F	1	1

1단계—매트릭스가 비어 있으므로 알고리즘의 이 분기가 성공적으로 종료된다.

B행, D행, F행 등이 선택됨에 따라 최종 해결책은 다음과 같다.

	1	2	3	4	5	6	7
B	1	0	0	1	0	0	0
D	0	0	1	0	1	1	0
F	0	1	0	0	0	0	1

즉, 모든 원소가 정확히 B = {1, 4, D = {3, 5, 6} 또는 F = {2, 7} 세트 중 하나에 포함되기 때문에 하위 집합 {B, D, F}은 정확한 표지다.

레벨 3에는 더 이상 선택된 행이 없으므로 알고리즘은 레벨 2에서 다음 분기로 이동한다.

레벨 2에는 더 이상 선택된 행이 없으므로 알고리즘은 레벨 1에서 다음 분기로 이동한다.

레벨 1에는 더 이상 선택된 행이 없으므로 알고리즘은 레벨 0에서 다음 분기로 이동한다.

레벨 0에는 분기가 없으므로 알고리즘은 종료된다.

요약하면 알고리즘은 ${\mathcal {S}}^{*}$ 한 표지가 S ${\mathcal {S}}^{*}$ ${\$ ${\mathcal {S}}^{*}$ = {B, D, F} 하나만 있다고 판단한다.

구현

알고리즘 X를 설명하는 도널드 크누스의 주된 목적은 댄스 링크의 유용성을 증명하는 것이었다.크누스는 크누스가 "DLX"라고 부르는 과정에서 알고리즘 X가 춤추는 링크를 사용하여 컴퓨터에서 효율적으로 구현될 수 있다는 것을 보여주었다.DLX는 매트릭스 1s의 이중 연계 목록으로 구현된 정확한 커버 문제의 매트릭스 표현을 사용한다. 각 1개 요소는 위, 아래, 왼쪽 및 자신의 오른쪽에 다음 1에 대한 링크를 가지고 있다.(기술적으로, 리스트는 순환적이기 때문에, 이것은 토러스(torus)를 형성한다.)정확한 표지 문제는 희박한 경향이 있기 때문에, 이 표현은 일반적으로 크기와 필요한 처리 시간 모두에서 훨씬 더 효율적이다.그런 다음 DLX는 댄스 링크를 사용하여 가능한 해결책으로 행의 순열을 신속하게 선택하고 잘못된 추측을 효율적으로 역추적(undo)한다.^[1]

참고 항목

참조

^ ^a ^b Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047.

Knuth, Donald E. (2000), "Dancing links", in Davies, Jim; Roscoe, Bill; Woodcock, Jim (eds.), Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare, Palgrave, pp. 187–214, arXiv:cs/0011047, Bibcode:2000cs.......11047K, ISBN 978-0-333-92230-9.

외부 링크

Knuth의 문서 - PDF 파일(arXiv:cs/0011047)
댄스 링크 최적화를 설명하는 Knuth의 논문 - Gzip'd postscript 파일.

[knuth-1] Knuth, Donald (2000). "Dancing links". arXiv:cs/0011047.

[1]

v t 도널드 크누스
출판물	컴퓨터 프로그래밍의 기술 "곡의 복잡성" 컴퓨터 및 유형설정 콘크리트 수학 초현실 수 컴퓨터 과학자가 좀처럼 입에 담지 않는 것 선택된 논문 시리즈
소프트웨어	TEX 메타폰트 믹살(MIX) MMIX GNU MDK)
글꼴	AMS 오일러 컴퓨터 모던 콘크리트 로마인
리터레이트 프로그래밍	웹 CWEB
알고리즘	크누스의 알고리즘 X 크누스-벤딕스 완성 알고리즘 크누스-모리스-프라트 알고리즘 크누스 셔플 로빈슨-스헨스테드-크누스 통신 트래브 파르도-크누스 알고리즘 Dijkstra 알고리즘 일반화 크누스의 심패스 알고리즘
기타	댄싱 링크스 크누스 보상조회 크누스상 남자 또는 남자 테스트 쿼터-상상 베이스 -yllion 포츠비 계통 도량형

Search

크누스의 알고리즘 X

네임스페이스

더

목차

예

구현

참고 항목

참조

외부 링크