조합 폭발

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 찾기 : '전파 폭발'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2014년 9월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

수학에서, 조합 폭발은 문제의 조합이 입력, 제약, 그리고 문제의 경계에 의해 어떻게 영향을 받는지로 인해 문제의 복잡성이 빠르게 증가하는 것이다.조합 폭발은 때때로 특정 문제의 ^[1][2]난해성을 정당화하기 위해 사용된다.이러한 문제의 예로는 특정 수학 함수, 일부 퍼즐 및 게임의 분석, 애커만 함수로 모델링할 수 있는 병리학적 예가 있습니다.

예

라틴 사각형

순서 n의 라틴 사각형은 n개의 요소 집합에서 엔트리가 있는 n×n 배열로, 집합의 각 요소가 배열의 각 행 및 각 열에 정확히 1개씩 발생한다는 특성을 가진다.순서 3의 라틴어 정사각형의 예는 다음과 같습니다.

1	2	3
2	3	1
3	1	2

라틴어 정사각형의 일반적인 예는 완성된 스도쿠 ^[3]퍼즐이다.라틴 사각형은 엔트리의 배열만이 중요하며 엔트리가 실제로 무엇인지는 중요하지 않기 때문에 (대수적 오브젝트와는 반대되는) 조합 객체입니다.순서 함수로서의 라틴 사각형 수(엔트리가 추출된 집합과는 무관함)는 다음 표와 같이 조합 폭발의 예를 제공한다.

n	순서 n의 라틴어 제곱수
1	1
2	2
3	12
4	576
5	161,280
6	812,851,200
7	61,479,419,904,000
8	108,776,032,459,082,956,800
9	5,524,751,496,156,892,842,531,225,600
10	9,982,437,658,213,039,871,725,064,756,920,320,000
11	776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000

스도쿠

스도쿠와 ^[2]같은 그리드에서 플레이되는 퍼즐에서도 조합 폭발이 발생할 수 있습니다.스도쿠는 각 요소가 크기 θn × θn(박스라고 함)의 하위 섹션에서 정확히 한 번 발생한다는 추가 특성을 가진 라틴 정사각형의 일종입니다.조합 폭발은 n이 증가함에 따라 발생하며, 다음 표에 나타나듯이 구성, 분석 및 해결할 수 있는 Sudokus의 특성에 한계가 생깁니다.

n	순서 n의 스도쿠 그리드 수 (크기는 nn×nn)	순서 n의 라틴어 제곱수 (비교용)
1	1개	1
4	288 [4][5]	576
9	6,670,903,752,021,072,936,960 [4][6]	5,524,751,496,156,892,842,531,225,600
16	5.96×1098 (표준)	—
25	4.36×10308 (표준)	—
(n = 9는 일반적으로 연주되는 9×9 스도쿠이다.이 퍼즐에는 δn이 비합리적인 격자는 포함되지 않는다.)

게임.

조합의 복잡성이 해결 가능성 한계로 이어지는 게임 중 하나는 체스(64개의 정사각형과 32개의 피스를 가진 게임)를 해결하는 것입니다.체스는 해결된 게임이 아니다.2005년에는 6피스 이하의 체스 게임 엔딩이 모두 해결되어 각 포지션의 결과가 완벽하게 나왔다.체스 한 마디가 더해져 테이블 베이스를 완성하는 데 10년이 더 걸렸고, 따라서 7개의 테이블 베이스를 완성했다.체스 엔딩에 한 피스를 추가하는 것(따라서 8피스의 테이블 베이스를 만드는 것)은 추가된 조합 ^[9][10]복잡성 때문에 다루기 어려운 것으로 간주됩니다.

게다가 체스 변종이나 체스 ^[11]무한대 등 보드 사이즈가 커짐에 따라 체스 같은 큰 게임을 풀 수 있는 전망은 더욱 어려워진다.

컴퓨팅

컴퓨팅 환경에서 통신 및 다차원 공간과 유사한 방식으로 조합의 폭발이 발생할 수 있습니다.A라는 부울 변수가 하나뿐인 단순한 시스템을 상상해 보십시오.시스템에는 A = true 또는 A = false의 두 가지 가능한 상태가 있습니다.다른 부울 변수 B를 추가하면 시스템에 A = true 및 B = true, A = true 및 B = false, A = false, B = true, A = false, B = false의 4가지 가능한 상태가 됩니다.n개의 부울란이 있는 시스템은 2개의 가능한 상태를 가지며ⁿ, 각각 허용값이 Z인 n개의 변수 시스템은 (2개의 (참과 거짓)의 부울란이 아닌ⁿ) Z 가능한 상태를 갖습니다.

가능한 상태는 높이 n의 트리의 리프 노드로 생각할 수 있습니다.각 노드에는 Z자식이 있습니다.리프 노드의 급격한 증가는 검색과 같은 영역에서 유용할 수 있습니다. 이는 많은 결과를 멀리 내려가지 않고도 액세스할 수 있기 때문입니다.또한 이러한 구조를 조작할 때 방해가 될 수 있습니다.

오브젝트 지향 언어의 클래스 계층은 부모로부터 상속되는 다양한 오브젝트를 가진 트리로 간주할 수 있습니다.(A < B와 같은) 비교와 같이 다른 클래스를 조합해야 하는 경우 발생할 수 있는 조합의 수는 폭발적으로 증가한다.비교의 각 유형을 프로그래밍해야 한다면, 이는 소수의 클래스라도 다루기 어려워질 것입니다.여러 상속을 통해 하위 클래스가 여러 부모를 가질 수 있으므로 기존 계층을 중단하지 않고 모든 자녀가 아닌 몇 개의 부모 클래스를 고려할 수 있습니다.

다른 채소들이 그들의 조상 종으로부터 물려받은 분류법이 그 예이다.각 채소의 맛을 다른 채소와 비교하는 것은 그 계층이 유전자에 대한 정보만을 포함하고 맛에 대한 언급을 하지 않기 때문에 어려워진다.그러나 당근/당근, 당근/감자, 당근/새싹, 감자/감자, 감자/새싹/새싹에 대한 비교를 작성하는 대신, 그것들은 모두 현재의 조상 기반 계층을 유지하면서 다른 종류의 맛으로부터 증식할 수 있다.

산술

n의 요인식을 취한다고 가정합니다.

$\displaystyle n!=n\cdot (n-1)\cdot \ldots \cdot 2\cdot 1$

그러면 1! = 1, 2! = 2, 3! = 6, 4! = 24!그러나 n이 비교적 작더라도 매우 큰 숫자에 빠르게 도달합니다.예를 들어 100! 9 9.33262154×10은¹⁵⁷ 대부분의 계산기에는 표시할 수 없을 정도로 크고 관측 가능한 우주의 기본 ^[12]입자의 추정 수보다 훨씬 큰 숫자입니다.

의사소통

다른 통신회선을 사용하여 4개 조직에 6개의 채널이 필요

중개업자를 사용하는 경우 조직당 하나의 채널만 필요합니다.

관리 및 컴퓨팅에서 조합의 폭발이란 조직이 프로세스에 추가됨에 따라 통신회선이 급속히 증가하는 것을 말합니다.(이러한 성장은 흔히 "지수적"이라고 표현되지만 실제로는 다항식입니다.)

2개의 조직이 특정 토픽에 대해 커뮤니케이션해야 하는 경우, 애드혹 방식으로 직접 커뮤니케이션하는 것이 가장 쉬울 수 있습니다.필요한 커뮤니케이션 채널은 1개뿐입니다.단, 세 번째 조직을 추가할 경우 3개의 개별 채널이 필요합니다.네 번째 조직을 추가하려면 5, 10, 6, 15 등 6개의 채널이 필요합니다.

일반적으로 n개 조직에 l ${\displaystyle =\frac{n}{}}$ (${\displaystyle \frac{}{\mathrm{}}}$ - ${\displaystyle \frac{1}{}}$) 2${\displaystyle =}$ ( ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$ 2$$) { $displaystyle$ l = n $frac {$n ( $n$- 1 ) } {2}} = {$n$\ $choose$2}개의$$ 통신회선이 $필요$합니다(이항계수 ^[13]참조).

대안적 접근법은 언제 이 통신이 일회성 요건이 되지 않을지를 깨닫고 정보를 전달하는 일반적이거나 중간적인 방법을 생산하는 것이다.단점은 첫 번째 쌍에 대해 더 많은 작업이 필요하다는 것입니다. 왜냐하면 각 쌍은 겉으로 보기에 쉽게 상대방을 이해할 수 있는 접근 방식보다는 내부 접근 방식을 공통 접근 방식으로 전환해야 하기 때문입니다.

「 」를 참조해 주세요.

레퍼런스