Explosión combinatoria
En matemáticas, una explosión combinatoria consiste en el crecimiento muy rápido de la complejidad de un problema debido a cómo se ve afectado por las condiciones iniciales, restricciones y límites del propio problema. La explosión combinatoria se utiliza a veces para justificar la intrazabilidad de ciertos problemas.[1][2] Hay muchos ejemplos de tales problemas, que incluyen ciertas funciones, el análisis de algunos rompecabezas y juegos y algunos ejemplos patológicos que pueden ser modelizados, como la Función de Ackermann.
Ejemplos
Cuadrados latinos
Un cuadrado latino de orden n es una matriz n × n cuyos elementos pertenecen a un conjunto de n elementos con la propiedad que cada elemento del conjunto aparece sólo una vez en cada fila y cada columna de la propia matriz. El siguiente es un ejemplo de cuadrado latino de orden tres:
1 2 3 2 3 1 3 1 2
Otro ejemplo muy común de cuadrado latino sería un puzle sudoku completo.[3] Un cuadrado latino es un objeto combinatorio (como opuesto a un objeto algebraico) donde lo único que importa es la disposición de sus elementos y no lo que sus elementos, en esencia, son. El número de cuadrados latinos es una función de su orden, independientemente del conjunto del que se obtienen sus elementos.La (sucesión A002860 en OEIS). es un ejemplo de explosión combinatoria, en relación con los cuadrados latinos. Viene ilustrado por la siguiente tabla.
| n | 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 ocurren explosiones combinatorias en algunos puzles dispuestos en forma matricial, como los sudokus. Un sudoku es un tipo de cuadrado latino con la propiedad adicional que cada elemento ocurre también sólo una vez en sub-secciones de medida √n×√n (llamadas cajas). La explosión combinatoria aparece a medida que aumenta n, creando límites prácticos a las propiedades de los sudokus que se pueden construir, analizar y solucionar, como se muestra en la siguiente tabla:
| n | El número de sudokus de orden n (cajas de tamaño √n×√n) | El número de cuadrados latinos de ordenar n(para comparación) |
|---|---|---|
| 1 | 1 | 1 |
| 4 | 288[4][5] | 576 |
| 9 | 6,670,903,752,021,072,936,960[6] | 5,524,751,496,156,892,842,531,225,600 |
| 16 | 7098596000000000000♠5.96×1098 (estimado)[7] | — |
| 25 | 9000000000000000000♠4.36×10308 (estimado)[8] | — |
| (n = 9 es el generalmente jugó 9×9 Sudoku. El rompecabezas no incluye verjas donde √n es irracional.) | ||
Juegos
Un ejemplo en un juego donde la complejidad combinatoria conduce a un límite para su solución es el es en solucionar ajedrez (un juego con 64 plazas y 32 piezas). Ajedrecístico no es un juego solucionado. En 2005 todos finales de juego ajedrecísticos con seis piezas o menos estuvo solucionado, mostrando el resultado de cada posición si jugó perfectamente. Tome diez más años para completar el tablebase con uno más el trebejo añadió, por ello completando un 7-pieza tablebase. Añadiendo un más pieza a un final ajedrecístico (así haciendo un 8-pieza tablebase) está considerado intratable debido al añadido combinatorial complejidad.[9][10]
Referencias
- Krippendorff, Klaus. «Combinatorial Explosion». Web Dictionary of Cybernetics and Systems. PRINCIPIA CYBERNETICA WEB. Consultado el 29 de noviembre 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.
- Plantilla:Cite OEIS
- «Sudoku maths - can mortals work it out for the 2x2 square ? : General». Forum.enjoysudoku.com. Consultado el 20 de octubre de 2013.
- «Sudoku enumeration problems». Afjarvis.staff.shef.ac.uk. Consultado el 20 de octubre de 2013.
- «Su-Doku's maths : General - Page 36». Forum.enjoysudoku.com. Consultado el 20 de octubre de 2013.
- «RxC Sudoku band counting algorithm : General». Forum.enjoysudoku.com. Consultado el 20 de octubre de 2013.
- http://chessok.com/Lomonosov Endgame Tablebases Lomonosov Endgame Tablebases
- http://chess.stackexchange.com/7-piece-endgame-tablebase (chess) 7-piece-endgame-tablebase (chess)
Enlaces externos
- Esta obra contiene una traducción derivada de «Combinatorial explosion» de la Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.