Explosión combinatoria
Explosión combinatoria es un término utilizado para describir el efecto de un aumento brusco ("explosivo") en la complejidad temporal de un algoritmo con un aumento en el tamaño de los datos de entrada del problema [1] .
Más precisamente, esto significa que el algoritmo bajo consideración no es polinomial, es decir, el tiempo para resolver el problema no está limitado por ningún polinomio en la longitud de la entrada. Por lo general, estos problemas tienen una complejidad exponencial o incluso superexponencial.
El origen del nombre se debe a que no se encuentra otra forma de solucionar el problema. , a excepción de una enumeración completa de todas las opciones posibles. En este caso, el tiempo requerido para la solución es proporcional al número de todas las configuraciones posibles, que se determina a partir de ciertas consideraciones combinatorias (combinaciones, permutaciones).
Para eludir el problema de la explosión combinatoria, se buscan métodos de solución especiales, en particular, se utilizan algoritmos heurísticos .
Ejemplos
La explosión combinatoria ocurre en muchos problemas de búsqueda [2] , en problemas de cálculo de secuencias resueltos por métodos de fuerza bruta . [3] [4]
El problema del viajante de comercio
En el problema clásico del viajante de comercio, se requiere encontrar la secuencia óptima de visitas a las ciudades por parte de un viajero de comercio. La única forma exacta de resolver el problema es recorrer todas las rutas posibles y elegir la que lleve la menor cantidad de tiempo. Por lo tanto, la complejidad de resolver el problema del viajante de comercio resulta ser proporcional al número de todas las posibles secuencias de ciudades, lo cual viene dado por la fórmula de permutación:
Ajedrez
Entonces, por ejemplo, es hipotéticamente posible calcular todas las opciones de movimientos en el juego de tablero de ajedrez desde el comienzo del juego hasta el final mediante una enumeración completa de todas las combinaciones. Sin embargo, en la actualidad y en un futuro próximo [2] , es prácticamente imposible solucionar tal problema. Por ejemplo, para una computadora capaz de calcular un millón de combinaciones de juegos por segundo con la eliminación de ramas obviamente no óptimas , tomará 1 segundo calcular 6 movimientos por delante, 11 días para 12 movimientos y alrededor de 32,000 años para 18 movimientos. [2]
Notas
- ↑ Diccionario Web de Cibernética y Sistemas . Fecha de acceso: 29 de mayo de 2010. Archivado desde el original el 6 de agosto de 2010.
- ↑ 1 2 3 Diccionario de informática . Fecha de acceso: 29 de mayo de 2010. Archivado desde el original el 8 de junio de 2013.
- ↑ Artículos sobre Inteligencia Artificial . Consultado el 29 de mayo de 2010. Archivado desde el original el 23 de agosto de 2011.
- ↑ Denys Duchier, Claire Gardent y Joachim Niehren. Programación de Restricciones Concurrentes en Oz para el Procesamiento del Lenguaje Natural . Fecha de acceso: 29 de mayo de 2010. Archivado desde el original el 12 de agosto de 2011.