Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
Tabla de datos
n
1
2,3
4
5
6
Nodos resueltos
conectados
directamente a nodos
no resueltos Nodo no resuelto
más cercano
conectado Distancia total
involucrada n-ésimo nodo
más cercano Distancia
mínima Última
conexión
O
O
A
A
B
C
A
B
E
D
E A
C
B
D
E
E
D
D
D
T
T 2
4
2+2=4
2+7=9
4+3=7
4+4=8
2+7=9
4+4=8
7+1=8
8+5=13
7+7=14 A
C
B 2
4
4 OA
OC
AB
E 7 BE
D
D
T 8
8
13 BD
ED
DT
Ahora se debe relacionar las columnas con la descripción del algoritmo. La entrada para la n-ésima
iteración se encuentra en las columnas 5 y 6 de las iteraciones anteriores, donde los nodos resueltos de la
quinta columna se enumeran después en la segunda par la iteración actual después de eliminar los que no
tienen conexión directa con nodos no resueltos. Los candidatos, para el n-ésimo nodo más cercano se
realiza en la columna 4 y los resultados se registran en las última tres columnas de la iteración actual.
La ruta más corta desde el nodo destino hasta el origen se puede rastrear hacia atrás en la última
columna de la tabla, con lo que se obtiene T→D→E→B→A→O o bien T→D→B→A→O. Por lo tanto, se
identificaron las dos opciones de ruta más corta desde el origen hasta el destino como
O→A→B→E→D→T y O→A→B→D→T, con una distancia total de 13 millas en cualquiera de las dos.
Problema del Árbol de Expansión Mínima
El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del
problema de la ruta más corta. En ambos casos se considera una red no dirigida y conexa, en la que la
información dada incluye alguna medida de longitud positiva – distancia, costo, tiempo, etc. – asociada con
la ligadura. Los dos problemas involucran también el hecho de seleccionar un conjunto de ligaduras con la
longitud más corta entre los dos conjuntos de ligaduras que satisfacen cierta propiedad. En el caso del
problema de la ruta más corta, esta propiedad es que la ligadura seleccionada debe proporcionar una
trayectoria entre el origen y el destino. Para el árbol de expansión mínima la propiedad requerida es que las
ligaduras seleccionadas deben proporcionar una trayectoria entre cada par de nodos.
El problema del árbol de expansión mínima se puede resumir de la siguiente manera:
1. Se tiene los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras
potenciales y la longitud positiva de cada una si s inserta en la red. (Las medidas alternativas
para la longitud de una ligadura incluyen distancia, costo y tiempo).
2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un
camino entre cada par de nodos.
3. El objetivo es satisfacer este requisito de manera que se minimice la longitud total de las
ligaduras insertadas en la red.
44