Page 106 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En la función tsp( ) de la figura 4.6 se colocan el tercero, cuarto y sexto parámetro para mayor sim-
plicidad del árbol.

Para la figura 4.4, una gira óptima tiene una longitud de 35. Una gira de esta longitud puede ser
construida si se retiene de cada g (i, S) el valor de j que minimiza el lado derecho de (2). Sea J (i, S)
este valor, entonces J (1, {2, 3, 4}) = 2. De esta forma, la gira inicia de 1 a 2. El siguiente punto a
visitar se obtiene de g (2, {3,4}), J (2, {3, 4} = 4, por lo que la siguiente arista es <2. 4>. Lo que falta
de la gira es g (4,{3}), J (4,{3}) = 3. El recorrido óptimo es 1, 2, 4, 3, 1.

cálculo de la coMplejIdad

En el problema del agente viajero, la solución más directa es la de intentar todas las premutaciones
de las n ciudades y encontrar el recorrido más barato, dando una complejidad de (n!). Desafor-
tunadamente, con 8 ciudades ya se tienen problemas (ver tabla 4.1). Un problema de permutacio-
nes es mucho más difícil de resolver que un problema donde solo se escojan subconjuntos, ya que
existen n! permutaciones y 2 diferentes subconjuntos de n objetos. Con programación dinámica
n
se han podido resolver desde 49 ciudades en 1954 al récord actual de 85 900 ciudades en 2006,
el último tomando 136 años de CPU (De los Cobos Silva, Goddard, Gutiérrez Andrade y Martínez
Licona, 2010).

Tabla 4.1. O(n!) > O(2 )
n

Utilizando la estrategia de programación dinámica, la complejidad del algoritmo es esta:

• En la primer iteración se calculan los g(j, ): n-1, siendo esta la primer iteración.

• Se calculan los g(j,S) tales que 1 ≤ S ≤ n-2:

(n-1) k sumas en total.

100