En matemáticas , una explosión combinatoria es el rápido crecimiento de la complejidad de un problema debido a la forma en que su combinatoria depende de la entrada, las restricciones y los límites. La explosión combinatoria a veces se utiliza para justificar la intratabilidad de ciertos problemas. [1] [2] Los ejemplos de tales problemas incluyen ciertas funciones matemáticas , el análisis de algunos rompecabezas y juegos, y algunos ejemplos patológicos que pueden modelarse como la función de Ackermann .
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 aparece exactamente una vez en cada fila y cada columna de la matriz. Un ejemplo de un cuadrado latino de orden tres se da por:
Un ejemplo común de un cuadrado latino sería un sudoku completo . [3] 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 las entradas realmente son. El número de cuadrados latinos en función del orden (independientemente 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.
Una explosión combinatoria también puede ocurrir en algunos rompecabezas que se juegan en una cuadrícula, como el Sudoku. [2] Un Sudoku es un tipo de cuadrado latino con la propiedad adicional de que cada elemento aparece exactamente una vez en subsecciones de tamaño √ n × √ n (llamadas casillas ). La explosión combinatoria ocurre a medida que n aumenta, lo que crea límites a las propiedades de los Sudokus que se pueden construir, analizar y resolver, como se ilustra en la siguiente tabla.
Un ejemplo de un juego en el que la complejidad combinatoria lleva a un límite de resolubilidad es la resolución del ajedrez (una partida con 64 casillas y 32 piezas). El ajedrez no es un juego resuelto . En 2005 se resolvieron todos los finales 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 tabla base con una pieza de ajedrez más añadida, completando así una tabla base de 7 piezas. Añadir una pieza más a un final de ajedrez (haciendo así una tabla base de 8 piezas) se considera intratable debido a la complejidad combinatoria añadida. [6] [7]
Además, la perspectiva de resolver juegos más grandes similares al ajedrez 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 . [8]
La explosión combinatoria puede ocurrir en entornos informáticos de una manera análoga a las comunicaciones y al espacio multidimensional . Imaginemos un sistema simple con una sola variable, una booleana llamada A. El sistema tiene dos estados posibles, A = verdadero o A = falso. Si añadimos otra variable booleana B , el sistema tendrá 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 booleanas tiene 2 n estados posibles, mientras que un sistema de n variables, cada una con Z valores permitidos (en lugar de solo los 2 (verdadero y falso) de las booleanas), tendrá Z n estados posibles.
Los estados posibles pueden considerarse como los nodos de hoja de un árbol de altura n , donde cada nodo tiene Z hijos. Este rápido aumento de nodos de hoja puede ser útil en áreas como la búsqueda , ya que se puede acceder a muchos resultados sin tener que descender demasiado. También puede ser un obstáculo al manipular dichas estructuras.
En un lenguaje orientado a objetos, la jerarquía de clases se puede considerar como un árbol en el que los distintos tipos de objetos heredan de sus padres. Si es necesario combinar distintas clases, como en una comparación (como A < B ), el número de combinaciones posibles que pueden producirse se dispara. Si es necesario programar cada tipo de comparación, esto pronto se vuelve insoluble incluso para un número pequeño de clases. La herencia múltiple puede resolver este problema, al permitir que las subclases tengan varios padres y, por lo tanto, se pueden considerar unas pocas clases padre en lugar de todas las clases hijas, sin alterar ninguna jerarquía existente.
Un ejemplo es una taxonomía en la que diferentes vegetales heredan de sus especies ancestrales. Intentar comparar el sabor de cada vegetal con el de los demás se vuelve inviable, ya que la jerarquía solo contiene información sobre la 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 de manera multiplicada de una clase separada de sabrosos mientras mantienen su jerarquía actual basada en los antepasados; luego, todo lo anterior se puede implementar con solo una comparación sabroso/sabroso.
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 puede visualizarse en la mayoría de las calculadoras, y mucho mayor que el número estimado de partículas fundamentales en el universo observable. [9]
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 a un proceso. (Este crecimiento suele describirse informalmente como "exponencial", pero en realidad es polinómico ).
Si dos organizaciones necesitan comunicarse sobre un tema en particular, puede ser más fácil comunicarse directamente de 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 simplemente el número de 2 combinaciones de n elementos (ver también Coeficiente binomial ). [10]
El enfoque alternativo consiste en 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 entender al otro.
