Explosão combinatória - Combinatorial explosion

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 pelas entradas, restrições e limites do problema. A explosão combinatória às vezes é usada para justificar a intratabilidade de certos problemas. Exemplos de tais problemas incluem certas funções matemáticas , a análise de alguns quebra-cabeças e jogos e alguns exemplos patológicos que podem ser modelados como a função de Ackermann .

Exemplos

Quadrados latinos

Um quadrado latino de ordem n é um n  ×  n matriz com entradas a partir de um conjunto de n elementos, com a propriedade de que cada elemento do conjunto ocorre apenas uma vez em cada fila e de cada coluna da matriz. Um exemplo de um quadrado latino de ordem três é dado por,

1	2	3
2	3	1
3	1	2

Um exemplo comum de quadrado latino seria um quebra- cabeça Sudoku completo . Um quadrado latino é um objeto combinatório (em oposição a um objeto algébrico), uma vez que 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 (independente do conjunto do qual as entradas são retiradas) (sequência A002860 no OEIS ) fornece um exemplo de explosão combinatória conforme ilustrado pela tabela a seguir.

Sudoku

Uma explosão combinatória também pode ocorrer em alguns quebra-cabeças jogados em uma grade, como o Sudoku. Um Sudoku é um tipo de quadrado latino com a propriedade adicional de que cada elemento ocorre exatamente uma vez em subseções de tamanho √ n  ×  √ n (chamadas de caixas ). A explosão combinatória ocorre à medida que n aumenta, criando limites para as propriedades dos Sudokus que podem ser construídos, analisados ​​e resolvidos, conforme ilustrado na tabela a seguir.

Jogos

Um exemplo em um jogo em que a complexidade combinatória leva a um limite de solubilidade está na solução de xadrez (um jogo com 64 quadrados e 32 peças). O xadrez não é um jogo resolvido . Em 2005 todos os finais de xadrez com seis peças ou menos foram resolvidos, mostrando o resultado de cada posição se jogado perfeitamente. Demorou mais dez anos para completar a base de mesa com mais uma peça de xadrez adicionada, completando assim uma base de mesa de 7 peças. Adicionar mais uma peça a um final de xadrez (criando assim uma base de mesa de 8 peças) é considerado intratável devido à complexidade combinatória adicionada.

Além disso, a perspectiva de resolver jogos maiores do tipo xadrez torna-se mais difícil à medida que o tamanho do tabuleiro aumenta, como em grandes variantes de xadrez e xadrez infinito .

Informática

A explosão combinatória pode ocorrer em ambientes de computação de maneira análoga às comunicações e ao espaço multidimensional . Imagine um sistema simples, com apenas uma variável, um boolean chamado A . O sistema tem 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 2 ⁿ estados possíveis, enquanto um sistema de n variáveis, cada uma com Z valores permitidos (em vez de apenas 2 (verdadeiro e falso) dos booleanos) terá Z ⁿ estados possíveis.

Os estados possíveis podem ser considerados os nós folha de uma árvore de altura n , onde cada nó tem Z filhos. Este rápido aumento de nós folha pode ser útil em áreas como pesquisa , uma vez que muitos resultados podem ser acessados ​​sem ter que descer muito. Também pode ser um obstáculo na manipulação de tais estruturas.

Uma hierarquia de classes em uma linguagem orientada a objetos pode ser considerada uma árvore, com diferentes tipos de objetos herdados de seus pais. Se diferentes classes precisam ser combinadas, como em uma comparação (como A  <  B ), então o número de combinações possíveis que podem ocorrer explode. Se cada tipo de comparação precisa ser programado, isso logo se torna intratável, mesmo para um pequeno número de classes. A herança múltipla pode resolver isso, permitindo que as subclasses tenham vários pais e, portanto, algumas classes pai podem ser consideradas em vez de todos os filhos, sem interromper qualquer hierarquia existente.

Um exemplo é uma taxonomia onde diferentes vegetais são herdados de suas espécies ancestrais. Tentar comparar o sabor de cada vegetal com os outros torna-se intratável, uma vez que a hierarquia contém apenas informações sobre genética e não faz menção ao sabor. No entanto, em vez de ter que escrever comparações para cenoura / cenoura, cenoura / batata, cenoura / broto, batata / batata, batata / broto, broto / broto, todos eles podem se multiplicar e herdar de uma classe separada de saborosos, mantendo seu ancestral atual. hierarquia baseada, então todos os itens acima podem ser implementados com apenas uma comparação saborosa / saborosa.

Aritmética

Suponha que tomemos o fatorial de n :

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

Então 1! = 1, 2! = 2, 3! = 6 e 4! = 24. No entanto, rapidamente obtemos números extremamente grandes, mesmo para n relativamente pequeno . Por exemplo, 100! ≈9,332 621 54 × 10 ¹⁵⁷ , um número tão grande que não pode ser exibido na maioria das calculadoras e muito maior do que o número estimado de partículas fundamentais no universo.

Comunicação

Usando linhas de comunicação separadas, quatro organizações exigem seis canais

Usando um intermediário, apenas um canal por organização é necessário

Em administração e computação , uma explosão combinatória é o aumento acelerado nas linhas de comunicação à medida que as organizações são adicionadas em um processo. (Esse crescimento é frequentemente descrito casualmente como "exponencial", mas na verdade é polinomial .)

Se duas organizações precisam se comunicar sobre um determinado tópico, pode ser mais fácil se comunicar diretamente de uma maneira ad hoc - apenas um canal de comunicação é necessário. No entanto, se uma terceira organização for adicionada, três canais separados serão necessários. Adicionar uma quarta organização requer seis canais; cinco dez; seis quinze; etc.

Em geral, serão necessárias linhas de comunicação para n organizações, que é apenas o número de 2 combinações de n elementos (ver também coeficiente binomial ). ${\ displaystyle l = {\ frac {n (n-1)} {2}} = {n \ escolha 2}}$

A abordagem alternativa é perceber quando essa comunicação não será um requisito único e produzir uma forma genérica ou intermediária de passar informações. A desvantagem é que isso requer mais trabalho para o primeiro par, uma vez que cada um deve converter sua abordagem interna para a comum, ao invés da abordagem superficialmente mais fácil de apenas compreender o outro.

Veja também

Referências