Hola
Páginas: 8 (1887 palabras)
Publicado: 9 de diciembre de 2010
1.Introduccion
El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V3 comparaciones (esto es notable considerando que puede haber hasta V2 aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dosvértices, hasta que se sabe que la estimación es óptima.
Sea un grafo G con conjunto de vértices V, numerados de 1 a N. Sea además una función camino Minimo(i,j,k) que devuelve el camino mínimo de i a j usando únicamente los vértices de 1 a k como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada i a cada j usando únicamente losvértices de 1 hasta k + 1.
Hay dos candidatos para este camino: un camino mínimo, que utiliza únicamente los vértices del conjunto (1...k); o bien existe un camino que va desde i hasta k + 1, después de k + 1 hasta j que es mejor. Sabemos que el camino óptimo de i a j que únicamente utiliza los vértices de 1 hasta k está definido por camino Minimo(i,j,k), y está claro que si hubiera un camino mejor dei a k + 1 a j, la longitud de este camino sería la concatenación del camino mínimo de i a k + 1 (utilizando vértices de (1...k)) y el camino mínimo de k + 1 a j (que también utiliza los vértices en (1...k)).
2. algoritmo de Floyd Paralelo
Grafos con Pesos
Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un grafo dirigido con pesos.
El largode una trayectoria de un vértice u a otro vértice v es la suma de los pesos de las aristas que componen la trayectoria.
El Problema de Todos Pares Distancias mas Cortas
Dado un grafo dirigido con pesos, ¿cuales son las trayectorias de largos mínimos (es decir “distancias mas cortas”) entre todos los pares de vértices?.
La Matríz de Adyacencias
Representar un grafo dirigido con pesos Gcon n vértices por una matríz MG como sigue:
Si 1,2, … ,n son los vértices, entonces el elemento en la fila #i y la columna #j es 0 si i=j, es ∞ (un número mas grande que cualquier peso) si no hay arista de I a j, y es el peso de la arista de i a j si tal arista existe. llamemos MG la matríz de adyacencias.
Ejemplo
La Solución al Ejemplo Anterior
El Diseño del Algoritmo Paralelo* Particionar
* En el seudo código la misma asignación se ejecuta n3 veces.
* No hay paralelismo funcional.
* Usemos descomposición de dominio: particionar la matriz A en sus n2 elementos.
* Patronos de Comunicaciones
* Aglomeración y Asignación
* El número de tareas es estatico
* Las comunicaciones entre las tareas son regulares
* Eltiempo de computación por tarea es constante
* Un buena estrategia en este caso es
* Aglomerar tareas para minimizar las comunicaciones
* Crear una tarea por proceso MPI
Dos Descomposiciones
Comparación de Descomposiciones
* Bloques de Columnas
* Se eliminan las emisiones dentro de las columnas
* Bloques de Filas
* Se eliminan las emisionesdentro de las columnas
* Escribir la salida es mas simple
* Escoger descomposión en bloque de filas
Ejemplo con resultados
Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias
Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.
1ª Iteración: nodo intermedio = 1
La matriz essimétrica, por lo que solamente hará falta calcular el triángulo superior de las distancias.
d23 = min(d23, d21 + d13) = 8
d24 = min(d24, d21 + d14) = 4
d25 = min(d25, d21 + d15) = 9
d26 = min(d26, d21 + d16) =
d34 = min(d34, d31 + d14) = 6
d35 = min(d35, d31 + d15) = 7
d36 = min(d36, d31 + d16) = 1
d45 = min(d45, d41 + d15) =
d46 = min(d46, d41 + d16) = 4
d56 = min(d56, d51 + d16) =...
El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices. El algoritmo es capaz de hacer esto con sólo V3 comparaciones (esto es notable considerando que puede haber hasta V2 aristas en el grafo, y que cada combinación de aristas se prueba). Lo hace mejorando paulatinamente una estimación del camino más corto entre dosvértices, hasta que se sabe que la estimación es óptima.
Sea un grafo G con conjunto de vértices V, numerados de 1 a N. Sea además una función camino Minimo(i,j,k) que devuelve el camino mínimo de i a j usando únicamente los vértices de 1 a k como puntos intermedios en el camino. Ahora, dada esta función, nuestro objetivo es encontrar el camino mínimo desde cada i a cada j usando únicamente losvértices de 1 hasta k + 1.
Hay dos candidatos para este camino: un camino mínimo, que utiliza únicamente los vértices del conjunto (1...k); o bien existe un camino que va desde i hasta k + 1, después de k + 1 hasta j que es mejor. Sabemos que el camino óptimo de i a j que únicamente utiliza los vértices de 1 hasta k está definido por camino Minimo(i,j,k), y está claro que si hubiera un camino mejor dei a k + 1 a j, la longitud de este camino sería la concatenación del camino mínimo de i a k + 1 (utilizando vértices de (1...k)) y el camino mínimo de k + 1 a j (que también utiliza los vértices en (1...k)).
2. algoritmo de Floyd Paralelo
Grafos con Pesos
Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un grafo dirigido con pesos.
El largode una trayectoria de un vértice u a otro vértice v es la suma de los pesos de las aristas que componen la trayectoria.
El Problema de Todos Pares Distancias mas Cortas
Dado un grafo dirigido con pesos, ¿cuales son las trayectorias de largos mínimos (es decir “distancias mas cortas”) entre todos los pares de vértices?.
La Matríz de Adyacencias
Representar un grafo dirigido con pesos Gcon n vértices por una matríz MG como sigue:
Si 1,2, … ,n son los vértices, entonces el elemento en la fila #i y la columna #j es 0 si i=j, es ∞ (un número mas grande que cualquier peso) si no hay arista de I a j, y es el peso de la arista de i a j si tal arista existe. llamemos MG la matríz de adyacencias.
Ejemplo
La Solución al Ejemplo Anterior
El Diseño del Algoritmo Paralelo* Particionar
* En el seudo código la misma asignación se ejecuta n3 veces.
* No hay paralelismo funcional.
* Usemos descomposición de dominio: particionar la matriz A en sus n2 elementos.
* Patronos de Comunicaciones
* Aglomeración y Asignación
* El número de tareas es estatico
* Las comunicaciones entre las tareas son regulares
* Eltiempo de computación por tarea es constante
* Un buena estrategia en este caso es
* Aglomerar tareas para minimizar las comunicaciones
* Crear una tarea por proceso MPI
Dos Descomposiciones
Comparación de Descomposiciones
* Bloques de Columnas
* Se eliminan las emisiones dentro de las columnas
* Bloques de Filas
* Se eliminan las emisionesdentro de las columnas
* Escribir la salida es mas simple
* Escoger descomposión en bloque de filas
Ejemplo con resultados
Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias
Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.
1ª Iteración: nodo intermedio = 1
La matriz essimétrica, por lo que solamente hará falta calcular el triángulo superior de las distancias.
d23 = min(d23, d21 + d13) = 8
d24 = min(d24, d21 + d14) = 4
d25 = min(d25, d21 + d15) = 9
d26 = min(d26, d21 + d16) =
d34 = min(d34, d31 + d14) = 6
d35 = min(d35, d31 + d15) = 7
d36 = min(d36, d31 + d16) = 1
d45 = min(d45, d41 + d15) =
d46 = min(d46, d41 + d16) = 4
d56 = min(d56, d51 + d16) =...
Leer documento completo
Regístrate para leer el documento completo.