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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En la siguiente discusión se comentará sobre un recorrido que inicia en el vértice 1 y termina en el
mismo vértice, siendo el recorrido el del mínimo costo. Toda gira consiste en una arista <1, k> para
algún k є V – {1} y un trayecto desde el vértice k al vértice 1. El trayecto desde el vértice k al vértice
1 va a través de cada vértice en V – {1, k}. De aquí que el principio de optimización se mantiene. Sea
g (i, S) la longitud del trayecto más corto iniciando en el vértice i, yendo a través de todos los vértices
en S y terminando en el vértice 1; g (1, V – {1}) es la longitud de una gira óptima de un agente viajero.
Desde el principio de optimalidad se deduce lo siguiente:

Se puede resolver g (1, V- {1}) si conocemos g (k, V- {1, k}) para todas las opciones de k. Los valores
de g pueden ser obtenidos usando (2). Claramente, g (i, ) = C , 1 i n. De aquí podemos usar (2)
i,1
para obtener g (i, S) para todo S de tamaño 1, entonces se puede obtener g (i, S) para S con |S| = 2,
etc. Cuando |S| < n – 1, los valores de i y S para el cual se necesita g (i, S) son tales que

Por ejemplo, considere la gráfica de la figura 4.4, donde el tamaño de las aristas se observa en la
matriz de costos c:

Figura 4.4. Gráfica dirigida cuya longitud de cada arista se localiza en la matriz C

(Horowitz y Sahni, 1978)

96