Explosão combinatória
Em matemática, uma explosão combinatória é o rápido crescimento da complexidade de um problema devido a como a combinatória do problema é afetada pelos seus inputs, restrições e limites. A explosão combinatória às vezes é usada para justificar a intratabilidade de certos problemas. [1] [2] Exemplos incluem certas funções matemáticas, a análise de alguns quebra-cabeças e jogos e alguns exemplos que podem ser modelados como a função de Ackermann.
Exemplos
Quadrados latinos
Um quadrado latino de ordem n é um quadrado n × n com entradas de um conjunto de n elementos com a propriedade de que cada elemento do conjunto ocorra exatamente uma vez em cada linha e cada coluna do quadrado.
Um exemplo comum de um quadrado latino é um quebra-cabeça Sudoku completo. [3] Um quadrado latino é um objeto combinatório (em oposição a um objeto algébrico), pois apenas o arranjo das entradas importa e não o que as entradas realmente são. O número de quadrados latinos em função da ordem fornece um exemplo de explosão combinatória conforme ilustrado na tabela abaixo.
n
|
O número de quadrados latinos de ordem 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
|
A explosão combinatória pode ocorrer em ambientes computacionais de maneira análoga ao espaço multidimensional. Imagine um sistema simples com apenas uma variável, uma booleana chamada A. O sistema possui dois estados possíveis, A = verdadeiro ou A = falso. Adicionar outra variável booleana B dará ao sistema quatro estados possíveis, A = verdadeiro e B = verdadeiro, A = verdadeiro e B = falso, A = falso e B = verdadeiro, A = falso e B = falso. Um sistema com n booleanos tem 2n estados possíveis, enquanto um sistema de n variáveis, cada uma com Z valores permitidos, terá Z n estados possíveis.
Veja também
Referências
- ↑ Krippendorff, Klaus. «Combinatorial Explosion». Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. Consultado em 29 de novembro de 2010
- ↑ http://intelligence.worldofcomputing/combinatorial-explosion Combinatorial Explosion.
- ↑ All completed puzzles are Latin squares, but not all Latin squares can be completed puzzles since there is additional structure in a Sudoku puzzle.
|
|