Embed Size (px)
Citation preview
ALGORITMOS DE RUTAS CORTAS Y
ÁRBOLES MST
INTEGRANTES
-Aramburu Cornejo Evelyn
-Coaquira Flores Tania
-Luque Carbajal Marleny
Algoritmos de Rutas Cortas
Algoritmo de Dijkstra.Algoritmo de Ford.Algoritmo de Floyd.
Árboles MST
Algoritmo de Prim.Algoritmo de Kruskal.
Algoritmos de Rutas Cortas
Objetivos Generales
El objetivo principal de los algoritmos de rutas cortas es calcular las distancias mínimas entre todos los nodos del grafo.Analizar los diferentes algoritmos de Rutas cortas y así aplicarlos con mayor eficiencia.
Algoritmos de Rutas Cortas
Dado un grafo dirigido G = (V, E) ; y una función de longitud ω : E→R .
Todos los algoritmos de esta sección usan la desigualdad del triángulo :
peso (u, v) > peso (u, i) + peso (i, v). peso (u, v) > peso (u, i) + peso (i, v).
La longitud de una ruta ó camino p = (v0, v1,…, vk)es:
La longitud de la ruta más corta de u a v ω ( p) = δ (u, v).
•Puede haber aristas con longitudes negativas
Algoritmo Dijkstra
Objetivo:
El objetivo de Dijkstra es el de calcular el camino de coste mínimo, desde un nodo origen (v) hasta cualquier otro nodo perteneciente al grafo y al resto de los nodos del grafo.
Definición:
Es un algoritmo iterativo, también llamado algoritmo de caminos mínimos, encuentra el camino más corto entre dos nodos.
La descripción del algoritmo Sea un grafo dirigido G = (V, E).Cada arista posee una longitud no negativa. Se toma uno de los nodos como nodo origen. El problema consiste en determinar la longitud del camino mínimo que va desde el origen hasta cada uno de todos lo demás nodos del grafo. Dado un grafo a cuyos arcos se han asociado una serie de pesos, se define el camino de coste mínimo de un vértice u a otro v, como el camino donde la suma de los pesos de los arcos que lo forman es la más baja entre las de todos los caminos posibles de u a v.
DIJKSTRA (Grafo G, nodo _ fuente s) // Inicializamos todos los nodos del grafo. La distancia de cada nodo es
infinita // y los padres son NULL For u є V[G] do
Distancia[u] = α Padre[u] = α Distancia[s] = 0 //encolamos todos los nodos del grafo Encolar (cola, V [G])
Mientras cola!= 0 do
// OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición // de Cola de prioridad
u = extraer_minimo (cola) for v є adyacencia[u] do If Distancia[v] > distancia[u] + peso (u, v) do
Distancia[v] = distancia[u] + peso (u, v) padre[v] = u
Ejemplov5
v2
v4
v3
v1
1
10
6
1
3
5
2
1 2 3 4 5
1 0 5 α α α 2 α 0 α 1 α 3 α 2 0 6 α 4 α α α 0 α 5 1 α 3 10 0
v5
v2
v4
v3
v1
1
10
6
1
3
5
2
iteracion1
menor
v5
v2
v4
v3
v1
1
10
6
1
3
5
2
Iteración 2
menor
v5
v2
v4
v3
v1
1
10
6
1
3
5
2
Iteración 3
nodo 1 al resto de los nodos del grafo:
D P iteración S W 2 3 4 5 2 3 4 5
-- α α α α -- -- -- -- 1 1 -- 5 α α α 1 -- -- -- 2 1,2 2 5 α 6 α 1 -- 2 -- 3 1,2,4 4 5 α 6 α 1 -- 2 --
Conclusiones:
Este Algoritmo es de mucha importancia por ser el de menor complejidad que los demás y además por que ayuda a solucionar distintos problemas de ruteo que se presentan cada día.
Recomendaciones:
Utilizar este algoritmo para todos aquellos problemas de ruteos, por ser el mas eficiente.
Aplicaciones:
Encaminamiento de paquetes por Encaminamiento de paquetes por los routerslos routers.Enrutamiento de aviones y tráfico aéreo. diseñar recorridos turísticos .
EL ALGORITMO DE BELLMAN-FORD.Objetivo Generar los caminos mínimos desde un nodo origen de
un grafo ponderado al resto de nodos del mismo, en el que las longitudes de las aristas pueden ser negativas.
Definición El algoritmo de Bellman- Ford genera los caminos
mínimos desde un nodo origen de un grafo ponderado al resto de nodos del mismo. Dado un grafo dirigido con peso G = (V;E) con
origen s y función de peso w : E→ R, el algoritmo retorna un valor booleano que indica si existe o no un ciclo de peso negativo que es alcanzable desde el origen. Si no hay un ciclo de peso negativo, el algoritmo produce los caminos mas cortos y sus pesos.
Tiene una complejidad del orden de N3 por cada nodo que realiza el algoritmo, es decir, un orden mayor que Dijkstra
El siguiente es el código del algoritmo:
Observación:
“Relajación” a través de un arco:Sea d[v] la estimación para la distancia más cortas desde el nodo
fuente.Al estudiar e arco (u,v) podemos mejorar la estimación
dependiendo si la rutavía u es mejor. Esta operación es conocida como “Relajar”. El
algoritmo es:Relax (u,v, w){
if (d[v] > d[u] + w(u,v) ){d[v] = d[u] + w(u,v);p[v] = u;
}}
Ejemplo BELLMAN-FORDEl siguiente ejemplo muestra la
ejecución del algoritmo en un grafo de 5 vértices:
Aplicaciones :
El algoritmo de Bellman- Ford es uno de los principales algoritmos de ruteo que se utilizan en Internet en los sistemas autónomos (AS). Este algoritmo es un elemento clave en las redes de comunicación.
El Internet es una enorme red de comunicaciones de ámbito mundial que permite la interconexión de sistemas informáticos. Esta físicamente compuesta por servidores de diversos tipos, marcas y sistemas operativos. Los servidores están unidos a través de enlaces de comunicación, los enlaces de comunicaciones se comunican a través de unos aparatos llamados routers. Los algoritmos de ruteo tienen como fin encontrar el camino óptimo para llevar la información desde una fuente hacia un destino pasando por los routers.
Dado que Internet crece de manera exponencial, es muy importante la eficiencia de los algoritmos de ruteo es por eso que el ruteo juega un papel muy importante en las redes de comunicación.
Conclusiones :
El algoritmo de Bellman- Ford funciona en teoría, pero tiene un gran problema en la práctica: aunque converge en la respuesta correcta, puede hacerlo de forma lentamente.
Pero pese a su lentitud es el más adecuado a emplear en el caso de que el grafo tenga pesos negativos.
Recomendaciones:
Se recomienda utilizar el algoritmo de Bellman- Ford únicamente cuando hay aristas negativas presentes en el grafo porque con el algoritmo de Dijkstra se obtienen los mismos resultados pero con un coste de tiempo menor siempre que las aristas no sean negativas.
ALGORITMO DE FLOYD-WARSHALL
Objetivo:
Encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo.
ALGORITMO FLOYD-WARSHALL
Definición : El algoritmo de Floyd - Warshall , ideado por Floyd en 1962 basándose en un teorema de Warshall también de 1962, usa la metodología de Programación Dinámica para resolver el problema.
El problema que intenta resolver este algoritmo es el de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es semejante a construir una matriz con todas las distancias mínimas entre pares de vértices de un grafo, indicando además la ruta a seguir para ir del primer vértice al segundo. Este es uno de los problemas más interesantes que se pueden resolver con algoritmos de grafos.
Pseudocodigo del Algorimto
Floyd_Warshall(n,W)Var D:arreglo [1..n][1..n] de enteros
Inicio Para i = 1 hasta n hacer Para j = 1 hasta n hacer
Inicio D [i,j] w [i,j]
pred [i,j] nulo fin
finpara k=1 hasta n hacer
para j=1 hasta n hacer inicio
si D[i,k] +D[k,j] < D[i,j] entonces inicio
D [I,j] D[i,k]+ D[k,j]pred[I,j] k
fin fin
return Dfin
Implementación del Algoritmo
public class Floyd{ public static final int INF = Integer.MAX_VALUE/2; public static int[][] algoritmoFloyd(int[][]D)
{ int n=D.length; //nº de vértices del grafo for(int k=0;k<n;k++) for(int i=0;i<n;i++)
for(int j=0;j<n;j++) D[i][j]= D[i][j] < D[i][k] + D[k][j] ? D[i][j] :
D[i][k] + D[k][j]; return D; }
}
Complejidad = O(n3)
Ejemplo Encontrar el camino más corto
entre todos los pares de nodos del siguiente grafo.
…Ejemplo1) Hallamos la Matriz de Distancias del
grafo :
…Ejemplo
2)Inicializamos la matriz de predecesores :
…Ejemplo
3) Primera Iteración : k=0; i=2; j=1;
D(2,1)<D(2,0)+D(0,1)?→ ∞<30+5? →D(2,1)=35
…Ejemplo4)Segunda Iteración : k=0; i=3; j=1D(3,1)<D(3,0)+D(0,1)? → ∞ <15+5?
D(3,1)=20
…Ejemplo 5) Tercera Iteración : k=1; i=0; j=2D(0,2)<D(0,1)+D(1,2)? → ∞ <15+5?
D(0,2)=20
…Ejemplo
6)Cuarta Iteración : k=1; i=0; j=3D(0,3)<D(0,1)+D(1,3)? → ∞ <5+5?
D(0,3)=10
…Ejemplo
7) Quinta Iteración : k=2; i=1; j=0D(1,0)<D(1,2)+D(2,0)?→50<15+30?D
(1,0)=45
…Ejemplo
8)Sexta Iteración : k=3; i=0; j=2D(0,2)<D(0,3)+D(3,2)? → 20<10+5?
D(0,2)=15
…Ejemplo
9)Sétima Iteración : k=3; i=1; j=0D(1,0)<D(1,3)+D(3,0)? → 45<5+15?
D(1,0)=20
…Ejemplo
10)Octava Iteración : k=3; i=1; j=2D(1,2)<D(1,3)+D(3,2)? → 15 <5+5?
D(1,2)=10
…EjemploLas Matrices Resultantes que contiene
las distancia mínimas y la ruta a seguir entre un par de nodos son :
Aplicaciones
Este algoritmo se puede aplicar a multitud de problemas tales como :En el diseño de circuitos En el diseño de rutas de transporteAproximaciones al problema del viajante Como base de otros algoritmos más complejos
CONCLUSIÓNES
Este algoritmo obtiene la mejor ruta entre todo par de nodos . La iteración se produce sobre nodos intermedios , es decir prueba si lo mejor para ir de un nodo a otro es a través de un nodo intermedio elegido o no.
Recomendaciones
Un aspecto importante, es la construcción de la matriz ,por lo tanto se tiene que tener cuidado al construir la matriz de Distancias y Predecesores.
Árboles de Expansión Mínima (MST)
Objetivos:
Estudiar los Árboles MST para usarlos adecuadamente en problemas de optimización Combinatoria.
Encontrar el árbol cuyos arcos suman el peso mínimo.
Definición:Dado en un grado no dirigido G=(V,E).Un árbol de expansión es un mínimo conjunto de enlaces; denotado por T*
Donde: T es un conjunto de árboles de expansión del grafo G.
Para que un árbol de expansión sea mínimo debe cumplir una de tales condiciones:
Ser un subgrafo de G conectado con n-1 enlaces.
Ser un subgrafo de G sin ciclos con n-1 enlaces.
Ademas debe de cumplir que la sumatoria de los pesos de todos los arcos asociados al subgrafo de G es el menor de todos los subgrafos asociados al grafo G que cumplen con las mismas restricciones.
MST(G, w):
A = Øwhile (A no forma un MST)encuentre una arista (u, v) que sea segura para A
A = A U {(u, v)}
return A
Ejemplo de árbol de expansión de mínimo peso
h
i
d
e
g f
b c 8
4
11
8
1 2
7
7
2
14
10
6
9
4 a
h
i
d
e
g f
b c8
4
11
8
1 2
7
2
14
10
6
9
a
V-S
S
7
4
S
V-S
Aplicaciones:
Diseño de redes de telecomunicaciones.Sistemas distribuidos.Transporte.Circuiteria electrónica: se desea unir n pines con n-1 cables.Cableado de la compañía telefónica, cable, etc.
Algoritmo de Kruskal
Objetivo:Construir un árbol (subgrafo sin ciclos)
formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
Definición:
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol expandido mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa).
Algoritmo de Kruskal Idea voraz: construir incrementalmente un
bosque (de recubrimiento), seleccionando en cada paso una arista (u, v) 2 A tal que:
No se cree ningún ciclo. Produzca el menor incremento de peso posible.
Hay que seguir los siguientes pasos: Se marca la arista con menor valor. Si hay más de una,
se elige cualquiera de ellas. De las aristas restantes, se marca la que tenga menor
valor, si hay más de una, se elige cualquiera de ellas. Repetir el paso 2 siempre que la arista elegida no forme
un ciclo con las ya marcadas. El proceso termina cuando tenemos todos los nodos del
grafo en alguna de las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo.
Ejemplo Kruskal
Aplicaciones :
La aplicación típica es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas.
Conclusiones:
Este algoritmo es de tipo Greedy, ya que a cada paso, éste selecciona el arco más barato y lo añade al subgrafo. El algoritmo de Kruskal es uno de los más fáciles de entender y probablemente el mejor para resolver
problemas a mano.
Recomendación:
Se recomienda el empleo del algoritmo de Kruskal, que a comparación de otros algoritmos que resuelven este tipo de problemas, es sumamente sencillo ya que la idea básica consiste en elegir sucesivamente las aristas de mínimo peso sin formar ciclos.
Algoritmo de MST- Prim
Objetivo:
El objetivo primordial de este algoritmo es la de encontrar el árbol generado mínimo a partir de uno dado.
Algoritmo de MST- Prim
Definición : El algoritmo de MST – Prim va construyendo un subconjunto de nodos aumentándolo uno a uno hasta que contenga todos los vértices .En cada paso se localiza el arco mas corto.
Pseudocodigo de MST- Prim
primMST(G,n)Inicializar la cola de prioridad cp como vacía;Seleccionar un Vértice arbitrario “s” para iniciar el árbol;Insertar (cp, s, 0);Mientras cp no este vacía hacer:
v = obtenerMin(cp); borrarMin(cp);añadir la arista que une con v al árbol;actualizar el borde del árbol;
actualizar borde (cp, G, v);Para todos los vértices u de G adyacentes a v
Si u no vistoInsertar en cp (u; w(v ; u));
Si u esta en la cola de prioridad cp hacer:Si la prioridad en cp de u es menor que w(v; u)Cambiar la prioridad en cp de u por w(v; u).
Ejemplo
2
1
5
43
6
6 51
5 5
3 6 4 2
6
1
6
2 3 4
5 6
1
5
34
2
Aplicaciones :
DISEÑO DE REDES FISICAS : teléfonos, hidráulica, TV por cable , computadores , carreteras …ANALISIS DE CLUSTER : Eliminación de aristas largas entre vértices irrelevantes
Distribución de mensajes entre agentesAPLICACIONES DIRECTAS : Plegamiento de proteínas , Reconociendo de células cancerosas…
Recomendación:
La idea es ir haciendo crecer el número de nodos que pertenecen al árbol de peso mínimo.Debemos ir buscando nodos y arcos que puedan ser agregados y que satisfagan la propiedad de mantener mínimo peso.
Comentarios sobre algoritmo de Prim
La eficiencia de este algoritmo depende de cómo se implemente la cola de prioridad Q.Si se implementa con un heap binario se obtiene que el algoritmo corre en tiempo O(V lg V + E lg V) = O(E lg V)Si se usa un heap de Fibonacci (no visto en el curso) el tiempo es O(E+V lgV), lo cual es una mejora cuando |V| << |E|
