댄싱 링크스

Dancing Links
Polycube 퍼즐을 푸는 Dances 알고리즘

컴퓨터 과학에서 춤추는 링크(DLX)는 원형 이중 연결 목록에서 노드를 추가하고 삭제하는 기술이다.도날드 크누스의 알고리즘 X와 같은 역추적 알고리즘의 정확한 커버 문제를 효율적으로 구현하는 데 특히 유용하다.[1]알고리즘 X는 정확한 커버 문제에 대한 모든 해결책을 찾는 반복적이고 비결정적, 깊이 우선의 역추적 알고리즘이다.더 잘 알려진 정확한 표지 문제로는 타일링, n퀸 문제, 스도쿠 등이 있다.

게도" 정교하게 춤을 안무."크누스 히로시 Hitotsumatsu과 Kōhei Noshita 1979,[2]에 아이디어가 발명될 수 있었던 것이 있었다고 한다를 많이 닮은 것이 알고리즘의 반복"댄스"파트너와 연계의 연결들을 유발하는 도널드 크누스에 의해 제시되었다 그 이름 춤 링크는 알고리즘이 작동하는 방식을었으나, 그것은 그의 종이 w. 유래한다딸꾹!h는 그것을 대중화했다.

실행

본 기사의 나머지 부분에서는 알고리즘 X에 대한 구현 기법의 세부 사항을 논의하므로, 독자는 알고리즘 X 기사를 먼저 읽도록 강력히 권장한다.

주요 아이디어

DLX의 아이디어는 순환적으로 이중으로 연결된 노드 목록에서

x.left.right x.right; x.right.left x.left;

목록에서 노드 x를 제거하는 동안

x.left.right x; x.right.left x;

x.right와 x.left가 수정되지 않은 채로 남겨졌다고 가정할 때, 목록에서 x의 위치를 회복할 것이다.이것은 비록 그 숫자가 1일지라도 리스트에 있는 요소의 수에 관계 없이 작동한다.

크누스는 자신의 알고리즘 X의 순진한 구현이 1의 알고리즘을 찾는 데 지나치게 많은 시간을 소비할 것이라고 보았다.열을 선택할 때 전체 행렬이 1을 검색해야 했다.행을 선택할 때는 전체 열에서 1을 검색해야 했다.행을 선택한 후, 그 행과 많은 열을 1의 행으로 검색해야 했다.크누스는 이 검색 시간을 복잡도 O(n)에서 O(1)로 개선하기 위해 1개만 저장되는 희소성 매트릭스를 구현했다.

항상 매트릭스의 각 노드는 왼쪽과 오른쪽(같은 행에 있는 1개), 위와 아래(같은 열에 있는 1개), 그리고 해당 열의 헤더(아래 설명)를 가리키는 인접 노드를 가리킨다.행렬의 각 행과 열은 두 배로 연결된 원형 노드 목록으로 구성된다.

헤더

각 열에는 "열 헤더"로 알려진 특수 노드가 있어 열 목록에 포함되며, 행렬에 존재하는 모든 열로 구성된 특수 행("제어 행")을 형성한다.

마지막으로, 각 열 머리글은 선택적으로 열의 노드 수를 추적할 수 있으므로, 노드 수가 가장 적은 열을 찾는 것이 열 수는 n이고 행 수는 m인 O(n)가 아니라 복잡도 O(n)가 되도록 한다.노드 수가 적은 열을 선택하는 것은 어떤 경우에는 성능을 향상시키는 경험적 경험이지만 알고리즘에는 필수적이지 않다.

탐사하는

알고리즘 X에서 행과 열은 정기적으로 제거되고 행렬로 복원된다.제거는 해당 열의 열과 행을 선택하여 결정한다.선택한 열에 행이 없으면 현재 행렬을 확인할 수 없으므로 역추적해야 한다.제거가 발생하면 선택한 행에 1이 포함된 모든 열(선택한 행 포함)과 함께 제거된 열 중 하나에 1이 포함된 모든 행이 제거된다.열은 채워졌으므로 제거되고, 행은 선택한 행과 충돌하므로 제거된다.단일 열을 제거하려면 먼저 선택한 열의 머리글을 제거하십시오.다음으로, 선택한 열에 1이 포함된 각 행에 대해 행을 가로지르고 다른 열에서 제거하십시오(이러하면 해당 행에 액세스할 수 없게 되고 충돌을 방지하는 방법임).선택한 행에 1이 포함된 각 열에 대해 이 열 제거를 반복하십시오.이 순서는 제거된 모든 노드가 정확히 한 번 그리고 예측 가능한 순서로 제거되도록 보장하므로 적절히 역추적될 수 있다.결과 행렬에 열이 없으면 모두 채워지고 선택한 행이 솔루션을 형성한다.

역추적

역추적을 위해서는 위에서 설명한 두 번째 알고리즘을 사용하여 위의 과정을 역추적해야 한다.이 알고리즘을 사용하기 위한 한 가지 요구사항은 제거의 정확한 반전으로 역추적을 수행해야 한다는 것이다.크누스의 논문은 이러한 관계와 노드 제거와 재 삽입이 어떻게 작용하는지에 대한 명확한 그림을 제시하며, 이러한 한계를 약간 완화시켜 준다.

선택적 제약 조건

특정 제약이 선택사항이지만 한 번 이상 만족할 수 없는 원커버 문제도 해결할 수 있다.댄싱 링크는 채워야 하는 기본 열과 옵션인 보조 열로 이들을 수용한다.이것은 알고리즘의 솔루션 테스트를 열이 없는 행렬에서 기본 열이 없는 행렬로 변경하며, 한 열에 최소 한 열의 휴리스틱이 사용되는 경우 기본 열 내에서만 점검하면 된다.크누스는 n 여왕 문제에 적용되는 선택적 제약조건에 대해 논한다.체스판 대각선은 일부 대각선이 점유되지 않을 수 있기 때문에 선택적 제약조건을 나타낸다.대각선이 점유된 경우 한 번만 점유할 수 있다.

참고 항목

참조

  1. ^ Knuth, Donald (2000). "Dancing links". Millennial Perspectives in Computer Science. P159. 187. arXiv:cs/0011047. Bibcode:2000cs.......11047K. Retrieved 2006-07-11.
  2. ^ Hitotumatu, Hirosi; Noshita, Kohei (30 April 1979). "A Technique for Implementing Backtrack Algorithms and its Application". Information Processing Letters. 8 (4): 174–175. doi:10.1016/0020-0190(79)90016-4.

외부 링크