Page 87 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 87
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 3.4. Un ejemplo para el algoritmo del trayecto más corto (Horowitz y Sahni, 1978)
Para formular un algoritmo greedy y generar el trayecto más corto, debemos concebir una solución
multietapa. Una posibilidad es construir el trayecto más corto uno por uno. Como una medida de
optimización se puede usar la suma de todos los trayectos generados hasta el momento. En orden
de que la medida sea mínima, cada trayecto individual debe ser de tamaño mínimo. Si se han cons-
truido i trayectos mínimos, el siguiente que debe ser construido debería ser el próximo trayecto con
mínima distancia.
El camino greedy para formar los trayectos cortos desde v a los vértices remanentes se logra gene-
0
rando los trayectos en orden creciente. Primero, se crea el trayecto más corto al vértice más cerca-
no. Entonces el trayecto más corto al segundo vértice más cercano se genera, y así sucesivamente.
En la figura 3.4, el trayecto más cercano para v es v (c (v v ) = 10), por lo que el trayecto v v será
0 2 0, 2 0 2
el primero generado.
El segundo trayecto más cercano de v es v , v con una distancia de 25. Para generar los siguientes
0 2 3
trayectos se debe determinar i) el siguiente vértice con el cual deba generar un camino más corto y
ii) un camino más corto para cada uno de los vértices partiendo del vértice original. Sea S el conjunto
de vértices (incluyendo V ) en el cual el trayecto más corto ha sido generado.
0
Sea W el conjunto de vértices no en S, sea DIST(w) la distancia del trayecto más corto desde v
0
yendo solo a través de estos vértices que están en S y terminando en w. Se observa lo siguiente:
I. Si el siguiente trayecto más corto es al vértice u, el trayecto inicia en v , termina
0
en u y va a través de algunos de los vértices localizados en S.
II. El destino del siguiente trayecto generado debe de ser aquel vértice u tal que
forme la mínima distancia —DIST(u)— sobre todos los vértices, no en S.
III. Habiendo seleccionado un vértice u en II y generado el trayecto más corto de v
0
81
