Complejidad computacional
En los problemas de tipo combinatorio existe siempre un procedimiento elemental para determinar la solución óptima buscada: realizar una exploración exhaustiva del conjunto de soluciones (enumeración completa). Es decir, generar todas las soluciones factibles (o sea, las que cuadran con las restricciones), calcular para cada una el coste asociado y elegir finalmente la que haya dado el mejor resultado. Aunque este método nos lleva sí o sí al objetivo, el tiempo de cálculo crece exponencialmente con el número de ítems del problema.
Ejemplo: consideremos el problema de la mochila (imagínese hacer una excursión a la que solo podemos llevar una mochila que, lógicamente, tiene una capacidad limitada. Cada objeto que introducimos ocupa un volumen dentro de la misma y en contrapartida durante el viaje nos proporcionará un beneficio o utilidad (ejemplo: una cantimplora), el problema surge cuando debemos elegir qué objetos seleccionar para llevar en la mochila de forma que nuestro beneficio sea máximo (tengamos todo lo necesario) sin exceder su capacidad. Fuente: Wikipedia (problema de la mochila)). El número de subconjuntos del conjunto {1..n} es 2^n. Por tanto, si un ordenador pudiese, en tan solo un segundo, generar un millón de estos subconjuntos y evaluar su valor (sería bastante rápido), es lo que necesitaría para hallar la solución de un problema con n=20 (2^20=1048576) (aprox.), pero con este mismo ordenador, si los ítems fueran 40 (n=40), necesitarías unas 2 semanas, y si los ítems fueran 60 (n=60) tardaría ¡¡365 SIGLOS DE CÁLCULO PARA ANALIZAR LAS 2^60 POSIBLES SOLUCIONES!!
Está claro que hay cuatro posibles soluciones:
- No ir de excursión nunca.
- En el caso de ir: comprar una mochila gigante.
- Meterle RAM al ordenador.
- O plantear el problema con lógica y no a lo basto (próximos posts).