explosión combinatoria

Un cuadrado latino de orden n es una matriz de 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 en cada columna de la matriz. Un ejemplo de un cuadrado latino de orden tres se da por:

Un ejemplo común de cuadrado latino sería un rompecabezas de 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 cuáles son las entradas en sí. 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.

También puede producirse una explosión combinatoria 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 se produce a medida que n aumenta, creando 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 donde la complejidad combinatoria conduce a un límite de resolubilidad es el ajedrez (un juego con 64 casillas y 32 piezas). El ajedrez no es un juego resuelto . En 2005 se resolvieron todos los finales de partidas de ajedrez con seis piezas o menos, mostrando el resultado de cada posición si se jugara a la perfección. Se necesitaron diez años más para completar la base de datos con una pieza de ajedrez adicional, completando así una base de datos de 7 piezas. Agregar una pieza más a un final de ajedrez (creando así una base de datos de 8 piezas) se considera intratable debido a la complejidad combinatoria adicional. ^{[ 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 forma análoga a la comunicación y el 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ⁿ ^estados posibles, mientras que un sistema de n variables, cada una con ^Z valores permitidos (en lugar de solo los 2 (verdadero y falso) booleanos), tendrá Zⁿ estados posibles.

Los estados posibles pueden considerarse como los nodos hoja de un árbol de altura n , donde cada nodo tiene Z hijos. Este rápido aumento de nodos hoja puede ser útil en áreas como la búsqueda , ya que se puede acceder a muchos resultados sin tener que descender demasiado. Sin embargo, también puede ser un obstáculo al manipular dichas estructuras.

En un lenguaje orientado a objetos, la jerarquía de clases puede representarse como un árbol, donde los distintos tipos de objetos heredan de sus padres. Si es necesario combinar diferentes clases, como en una comparación (por ejemplo, A < B ), el número de combinaciones posibles se multiplica exponencialmente. Si cada tipo de comparación debe programarse, esto se vuelve rápidamente inmanejable incluso para un número reducido de clases. La herencia múltiple resuelve este problema, permitiendo que las subclases tengan múltiples padres, de modo que se pueden considerar unas pocas clases padre en lugar de todas las hijas, sin alterar la jerarquía existente.  

Un ejemplo es una taxonomía donde las diferentes verduras heredan de sus especies ancestrales. Intentar comparar el sabor de cada verdura con las demás resulta inviable, ya que la jerarquía solo contiene información genética y no menciona el sabor. Sin embargo, en lugar de tener que escribir comparaciones para zanahoria/zanahoria, zanahoria/patata, zanahoria/brote, patata/patata, patata/brote, brote/brote, todas pueden heredar por multiplicación de una clase separada de sabor manteniendo su jerarquía actual basada en ancestros; entonces todo lo anterior se puede implementar con una simple comparación de sabor/sabor.

En administración e informática , una explosión combinatoria es el rápido aumento de las líneas de comunicación a medida que se incorporan 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, lo más sencillo puede ser hacerlo directamente de forma puntual ; basta con un único canal de comunicación . Sin embargo, si se añade una tercera organización, se requieren tres canales distintos. Si se añade una cuarta, se necesitan seis canales; cinco, diez; seis, quince; etc.

En general, tomará ${\displaystyle l={\frac {n(n-1)}{2}}={n \choose 2}}$ líneas de comunicación para n organizaciones, que es simplemente el número de combinaciones de 2 elementos (véase también coeficiente binomial ). ^{[ 9 ]}

La alternativa consiste en identificar cuándo esta comunicación no será un requisito puntual y desarrollar una forma genérica o intermedia de transmitir información. El inconveniente es que esto requiere más trabajo para la primera pareja, ya que cada una debe adaptar su enfoque interno al común, en lugar de optar por la solución aparentemente más sencilla de simplemente comprender al otro.