Complejidad Computacional
Por mameyugo el 10.Jul.2008
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


