Complejidad Computacional

En los problemas de tipo combinatorio existe siempre un procedimiento elemental para determinar la solución optima buscada: realizar una explosió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 si o si al objetivo el tiempo de calculo crece exponencialmente con el numero 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 numero 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(seria 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 CALCULO PARA ANALIZAR LAS 2^60 POSIBLES SOLUCIONES!!!!!!

Esta 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 post.)