Optimización de Redes: Algoritmos de Recorrido Mínimo y Ruta Más Corta

Optimización de Redes: Conceptos y Algoritmos Fundamentales

Conceptos Fundamentales de Redes

En el estudio de las redes, es crucial comprender la terminología básica que las define:

• Puntos (Nodos): Representan ubicaciones o entidades discretas dentro de una red.
• Curvas (Ramas): Son las conexiones o enlaces entre los nodos.

Una Red es un conjunto de puntos y curvas, denominados nodos y ramas, respectivamente.

Tipos de Ramas y Redes

• Ramas Orientadas: Poseen una dirección asociada, indicada esquemáticamente por una flecha.
• Ramas Conexas: Comparten un nodo en común.
• Rutas: Son secuencias de ramas conexas en las que, durante la alternancia de ramas y nodos, no se repite ningún nodo.
• Red Conexa: Se considera conexa si para cada par de nodos existe al menos una ruta que los une.
• Árbol: Es una red conexa en la que la ruta entre cada par de nodos es única. Esto equivale a una red conexa que tiene un nodo más que el número de ramas.

Algoritmo de Recorrido Mínimo (Árbol de Expansión Mínima)

Este algoritmo no es orientado y su objetivo principal es construir una red conexa con el costo total mínimo posible.

Pasos del Algoritmo

1. Se selecciona un nodo inicial de forma arbitraria.
2. Se consideran todas las ramas conectadas a él y sus respectivos costos. Se selecciona la más económica, la cual se agrega a la red solución (en caso de empate, se selecciona una al azar).
3. ¿Todos los nodos son conexos? Si la respuesta es sí, ir al paso 5.
4. Se consideran todas las ramas que conectan los nodos ya conexos con los no conexos, seleccionando la más económica, y se agrega a la red solución (en caso de empate, se elige una al azar). Volver al paso 3.
5. Acumular los costos de la red solución (Z* = Σ Ci; función objetivo).

Algoritmo de la Ruta Más Corta

Este problema se aplica a una red conexa donde un nodo se denomina fuente y otro destino. El objetivo es determinar una ruta que una la fuente con el destino, de manera que la suma de los costos asociados con las ramas en la ruta sea mínima.

Pasos del Algoritmo

1. Construir una lista maestra tabulando, bajo cada nodo y en orden ascendente según el costo, las ramas que llegan a él. Cada rama, bajo un nodo dado, se escribe con ese nodo como su primer nodo (omitir de la lista cualquier rama que tenga el destino como primer nodo).
2. Marcar con un asterisco (*) la fuente y asignarle el valor cero (0). Localizar la rama más barata que coincida con la fuente y encerrarla en un círculo. Marcar con asterisco (*) el segundo nodo de esta rama y asignarle a ese nodo un valor igual al costo de la rama. Eliminar de la lista maestra todas aquellas otras ramas que tengan como segundo nodo al que acaba de marcar con asterisco (*).
3. Si el nodo que acaba de marcarse con * es el destino, continuar en el paso 5. Si no, continuar con el paso 4.
4. Considerar en la lista maestra actual todos los nodos marcados con * que tengan ramas encerradas en círculos. Para cada uno de ellos, agregar el valor asignado al nodo al costo de las ramas y círculos más baratos bajo él. Permitir que la menor de estas sumas sea M (mayúscula) y encerrar en un círculo la rama cuyo costo contribuyó a M. Marcar con un * el segundo nodo de esta rama y asignarle el valor M. Eliminar de la lista maestra todas las otras ramas que tengan al nodo que acaba de marcarse con un * como segundo. Continuar en el paso 3.
5. Z* es el valor asignado al destino. Una ruta de costo mínimo se obtiene recursivamente, iniciando con el destino, al incluir en la ruta cada rama encerrada en un círculo cuyo nodo pertenece a la ruta.