Explosión combinatoria - Combinatorial explosion
En matemáticas , una explosión combinatoria es el rápido crecimiento de la complejidad de un problema debido a cómo la combinatoria del problema se ve afectada por la entrada, las restricciones y los límites del problema. La explosión combinatoria se utiliza a veces para justificar la intratabilidad de ciertos problemas. Ejemplos de tales problemas incluyen ciertas funciones matemáticas , el análisis de algunos acertijos y juegos, y algunos ejemplos patológicos que pueden modelarse como la función de Ackermann .
Ejemplos de
Cuadrados latinos
Un cuadrado latino de orden n es una matriz n × n con entradas de un conjunto de n elementos con la propiedad de que cada elemento del conjunto ocurre exactamente una vez en cada fila y cada columna de la matriz. Un ejemplo de un cuadrado latino de orden tres viene dado por,
1 2 3 2 3 1 3 1 2
Un ejemplo común de un cuadrado latino sería un Sudoku completo . Un cuadrado latino es un objeto combinatorio (a diferencia de un objeto algebraico) ya que solo importa la disposición de las entradas y no lo que realmente son las entradas. El número de cuadrados latinos en función del orden (independiente del conjunto del que se extraen las entradas) (secuencia A002860 en la OEIS ) proporciona un ejemplo de explosión combinatoria como se ilustra en la siguiente tabla.
| norte | El número de cuadrados latinos de orden 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 |
Sudoku
También puede ocurrir una explosión combinatoria en algunos rompecabezas que se juegan en una cuadrícula, como el Sudoku. Un Sudoku es un tipo de cuadrado latino con la propiedad adicional de que cada elemento ocurre exactamente una vez en subsecciones de tamaño √ n × √ n (llamadas cajas ). La explosión combinatoria ocurre cuando n aumenta, creando límites a las propiedades de los Sudokus que pueden construirse, analizarse y resolverse, como se ilustra en la siguiente tabla.
| norte | El número de cuadrículas de Sudoku de orden n (los cuadros son de tamaño √ n × √ n ) |
El número de cuadrados latinos de orden n (para comparación) |
|---|---|---|
| 1 | 1 | 1 |
| 4 | 288 | 576 |
| 9 | 6,670,903,752,021,072,936,960 | 5.524.751.496.156.892.842.531.225.600 |
| dieciséis | 5,96 × 10 98 ( estimado ) | - |
| 25 | 4,36 × 10 308 ( estimado ) | - |
| ( n = 9 es el Sudoku 9 × 9 que se juega comúnmente. El rompecabezas no incluye cuadrículas donde √ n es irracional ). | ||
Juegos
Un ejemplo en un juego donde la complejidad combinatoria lleva a un límite de capacidad de solución es resolver ajedrez (un juego con 64 casillas y 32 piezas). El ajedrez no es un juego resuelto . En 2005 se resolvieron todos los finales de las partidas de ajedrez con seis piezas o menos, mostrando el resultado de cada posición si se jugaba perfectamente. Se necesitaron diez años más para completar la base de la mesa con una pieza de ajedrez más agregada, completando así una base de mesa de 7 piezas. Agregar una pieza más a un final de ajedrez (haciendo así una base de mesa de 8 piezas) se considera intratable debido a la complejidad combinatoria agregada.
Además, la perspectiva de resolver juegos de ajedrez más grandes se vuelve más difícil a medida que aumenta el tamaño del tablero, como en las variantes de ajedrez grandes y el ajedrez infinito .
Informática
La explosión combinatoria puede ocurrir en entornos informáticos de una manera análoga a las comunicaciones y el espacio multidimensional . Imagine un sistema sencillo con una sola variable, un booleano llamado A . El sistema tiene dos estados posibles, A = verdadero o A = falso. Agregar otra variable booleana B le dará al sistema cuatro estados posibles, A = verdadero y B = verdadero, A = verdadero y B = falso, A = falso y B = verdadero, A = falso y B = falso. Un sistema con n booleanos tiene 2 n estados posibles, mientras que un sistema de n variables, cada una con valores Z permitidos (en lugar de solo los 2 (verdadero y falso) de los booleanos) tendrá Z n estados posibles.
Los estados posibles se pueden considerar como los nodos de las hojas de un árbol de altura n , donde cada nodo tiene Z hijos. Este rápido aumento de nodos de hojas puede ser útil en áreas como la búsqueda , ya que se puede acceder a muchos resultados sin tener que descender mucho. También puede ser un obstáculo a la hora de manipular dichas estructuras.
Una jerarquía de clases en un lenguaje orientado a objetos se puede considerar como un árbol, con diferentes tipos de objetos heredados de sus padres. Si es necesario combinar diferentes clases, como en una comparación (como A < B ), el número de combinaciones posibles que pueden ocurrir aumenta enormemente. Si es necesario programar cada tipo de comparación, esto pronto se vuelve intratable incluso para un número reducido de clases. La herencia múltiple puede resolver esto, al permitir que las subclases tengan múltiples padres y, por lo tanto, se pueden considerar algunas clases principales en lugar de cada hijo, sin interrumpir ninguna jerarquía existente.
Un ejemplo es una taxonomía donde diferentes vegetales heredan de sus especies ancestrales. Intentar comparar el sabor de cada vegetal con los demás se vuelve intratable, ya que la jerarquía solo contiene información sobre genética y no menciona el sabor. Sin embargo, en lugar de tener que escribir comparaciones para zanahoria / zanahoria, zanahoria / papa, zanahoria / brote, papa / papa, papa / brote, brote / brote, todos pueden heredar por multiplicación de una clase separada de sabroso mientras mantienen su antepasado actual. jerarquía basada, entonces todo lo anterior se puede implementar con solo una comparación sabrosa / sabrosa.
Aritmética
Supongamos que tomamos el factorial de n :
¡Entonces 1! = 1, 2! = 2, 3! = 6 y 4! = 24. Sin embargo, rápidamente llegamos a números extremadamente grandes, incluso para n relativamente pequeños . Por ejemplo, ¡100! ≈9.332 621 54 × 10 157 , un número tan grande que no se puede mostrar en la mayoría de las calculadoras, y mucho más grande que el número estimado de partículas fundamentales en el universo.
Comunicación
En administración e informática , una explosión combinatoria es el aumento acelerado de las líneas de comunicación a medida que se agregan organizaciones en un proceso. (Este crecimiento a menudo se describe casualmente como "exponencial", pero en realidad es polinomio ).
Si dos organizaciones necesitan comunicarse sobre un tema en particular, puede ser más fácil comunicarse directamente de una manera ad hoc: solo se requiere un canal de comunicación . Sin embargo, si se agrega una tercera organización, se requieren tres canales separados. Agregar una cuarta organización requiere seis canales; Cinco diez; seis quince; etc.
En general, se necesitarán líneas de comunicación para n organizaciones, que es solo el número de 2- combinaciones de n elementos (ver también Coeficiente binomial ).
El enfoque alternativo es darse cuenta de cuándo esta comunicación no será un requisito único y producir una forma genérica o intermedia de transmitir información. El inconveniente es que esto requiere más trabajo para el primer par, ya que cada uno debe convertir su enfoque interno en el común, en lugar del enfoque superficialmente más fácil de simplemente comprender al otro.