열거 알고리즘

컴퓨터 과학에서 열거 알고리즘은 계산 문제에 대한 답을 열거하는 알고리즘입니다.형식적으로 이러한 알고리즘은 함수 문제와 마찬가지로 입력을 받아 해결책 목록을 생성하는 문제에 적용됩니다.각 입력에 대해 열거 알고리즘은 중복 없이 모든 솔루션 목록을 생성한 후 중지해야 합니다.열거 알고리즘의 성능은 모든 솔루션을 생성하는 데 필요한 총 시간, 또는 연속된 두 솔루션 간의 최대 지연 및 전처리 시간 측면에서 첫 번째 솔루션을 출력하기 전의 시간으로 계산됩니다.이 복잡도는 출력에 민감한 알고리즘에서 수행하는 것과 마찬가지로 입력 크기, 각 개별 출력 크기 또는 모든 출력 세트의 총 크기로 나타낼 수 있습니다.

정식 정의

열거 $문제{\displaystyle }$ P$(\displaystyle$ P$)$는 임의의 알파벳$\delta {\displaystyle \mathrm{}}$(\$displaystyle \Sigma$ 문자열에 대한 $R$(\$displaystyle$ R$$$)$로 정의됩니다.

${\displaystyle R\subseteq\Sigma ^{*}\times \Sigma ^{*}}$

알고리즘은 모든 $입력{\displaystyle }$x(\$displaystyle$x)에$$ 대해 y$(\displaystyle$ y$)$가 중복되지 $않고{\displaystyle }$ $z{\displaystyle }$$(x$, z)$$$the$ R$(\$${\displaystyle \mathrm{displaystyle}}$ (x$, z$$in$Y가 Algori인 경우에만${\displaystyle }$y$(\$$displaystyle$ z\$in$ y$)$를 생성하면$$P(\$displaystyle$$)$를 해결합니다.$시퀀스 y$가 유한하면 thm은 정지합니다$.$

공통 복잡도 클래스

열거형 문제는 계산 복잡도 이론의 맥락에서 연구되어 왔고, 그러한 문제에 대해 몇 가지 복잡도 클래스가 도입되었다.

매우 일반적인 클래스는 EnumP로,^[1] 입력 및 출력에서 가능한 출력의 정확성을 다항식 시간으로 확인할 수 있는 문제의 클래스입니다.형식적으로는 이러한 문제에 대해 문제 입력 x, 후보 출력 y를 입력으로 받아들여 입력 x에 대해 y가 정확한 출력인지 아닌지에 대한 판정 문제를 x 및 y의 다항식 시간으로 해결하는 알고리즘 A가 존재해야 한다.예를 들어 이 클래스에는 NP 클래스의 문제의 목격자를 열거하는 것과 같은 모든 문제가 포함됩니다.

정의된 다른 클래스는 다음과 같습니다.EnumP에도 있는 문제의 경우, 이러한 문제는 최소에서 가장 구체적인 순서로 정렬됩니다.

• 출력 다항식, 다항식 시간에 전체 출력을 계산할 수 있는 문제의 클래스입니다.
• 증분 다항식 시간, 즉 모든 i에 대해 입력 크기와 숫자 i의 다항식 시간으로 i번째 출력을 생성할 수 있는 문제의 클래스입니다.
• 다항식 지연, 연속된 두 출력 사이의 지연이 입력에서 다항식(및 출력과 독립)인 문제의 클래스입니다.
• 강한 다항식 지연은 각 출력 전의 지연이 이 특정 출력의 크기(및 입력 또는 다른 출력과 독립적)에서 다항식인 문제의 클래스입니다.전처리는 일반적으로 다항식으로 가정됩니다.
• 고정 지연, 즉 각 출력 전의 지연이 일정한 문제의 클래스, 즉 입력 및 출력과 무관합니다.전처리 단계는 일반적으로 입력에서 다항식으로 가정됩니다.

일반적인 기술

• 역추적:모든 솔루션을 열거하는 가장 간단한 방법은 가능한 결과의 공간을 체계적으로 탐색하는 것입니다(연속되는 ^[2]각 단계에서 분할).단, 이를 실행하면 지연에 대한 보장이 잘 이루어지지 않을 수 있습니다.즉, 역추적 알고리즘은 완전한 솔루션을 발생시키지 않는 가능한 결과의 일부 공간을 탐색하는 데 오랜 시간이 걸릴 수 있습니다.
• 손전등 검색:이 기술은 가능한 모든 솔루션의 공간을 탐색하지만 각 단계에서 현재의 부분 솔루션을 부분 ^[1]솔루션으로 확장할 수 있는지 여부를 해결함으로써 역추적을 개선합니다.응답이 '아니오'인 경우 알고리즘은 즉시 백트래킹하여 시간 낭비를 방지할 수 있습니다.이를 통해 2개의 완전한 솔루션 간의 지연에 대한 보증을 쉽게 표시할 수 있습니다.특히 이 기술은 스스로 줄일 수 있는 문제에 잘 적용된다.
• 설정 작업 중 닫힘:두 집합의 분리된 결합을 열거하려면 첫 번째 집합을 열거한 다음 두 번째 집합을 열거하여 문제를 해결할 수 있습니다.결합이 분리되지 않았지만 집합이 정렬된 순서로 열거될 수 있는 경우 중복을 즉시 제거하면서 두 집합 모두에서 열거를 병렬로 수행할 수 있습니다.결합이 분리되지 않고 두 집합이 정렬되지 않으면 예를 들어 해시 테이블을 사용하여 더 높은 메모리 사용량을 희생하여 중복을 제거할 수 있습니다.마찬가지로, 두 세트의 데카르트 곱은 한 세트를 열거하고 두 번째 단계를 열거할 때 얻은 모든 결과와 각 결과를 결합함으로써 효율적으로 열거할 수 있다.

열거 문제의 예

• 선형 부등식의 시스템으로 설명되는 폴리토프가 주어지고 폴리토프의 정점을 열거해야 하는 정점 열거 문제.
• 하이퍼그래프의 최소 횡단을 열거합니다.이 문제는 단조 이원화와 관련이 있으며 데이터베이스 이론 및 그래프 ^[3]이론의 많은 응용 프로그램과 관련되어 있습니다.
• 데이터베이스 쿼리에 대한 응답(예: 연결 쿼리 또는 모노딕 2차 순서로 표현된 쿼리)을 열거합니다.데이터베이스 이론에는 선형 전처리 및 지속적인 ^[4]지연으로 열거할 수 있는 결합 쿼리의 특성이 있다.
• 예를 들어 Bron-Kerbosch 알고리즘을 사용하여 입력 그래프에서 최대 클리어를 열거하는 문제
• 매트로이드 및 탐욕스러운 구조체의 모든 요소 나열
• 그래프에 대한 몇 가지 문제, 예를 들어 독립 세트, 경로, 절단 등을 열거한다.
• 부울 함수의 표현에 대한 만족스러운 할당을 열거하는 것. 예를 들어 연결 정규 형식 또는 분리 정규 형식으로 작성된 부울 공식, OBDD와 같은 이진 결정 다이어그램 또는 지식 ^[5]컴파일에서 연구된 제한된 클래스의 부울 회로.

계산가능성 이론과의 연관성

열거 알고리즘의 개념은 또한 계산 가능성 이론 분야에서 모든 재귀적으로 열거할 수 있는 문제의 클래스인 RE와 같은 일부 고복잡도 클래스를 정의하기 위해 사용됩니다.이것은 집합의 모든 요소를 생성하는 열거 알고리즘이 존재하는 집합의 클래스입니다. 집합이 무한하다면 알고리즘은 영원히 실행될 수 있지만, 각 솔루션은 유한 시간 후에 알고리즘에 의해 생성되어야 합니다.

레퍼런스