BIOGRAFIA
Martinez Cabarcas Luis Daniel
Cabarcas Carlos Eduardo
(2013) algoritmo de floyd
Lunes 15/04/2013 y Martes 16/04/2013
Fuentes de apoyo o fuentes bibliográficas
martes, 16 de abril de 2013
EJERCICIOS PROPUESTOS
- Implementar los algoritmos
paralelos de cálculo de todos los caminos más cortos que han sido
descritos previamente. Se aconseja realizar cambios sobre la clase Graph,
que encapsula la gestión del grafo etiquetado, para implementar todas las
operaciones de comunicación dentro de dicha clase. Por tanto, la clase
encapsularía un grafo distribuido entre los procesadores en base a una
determinada distribución (por bloques de filas para la descomposición
unidimensional, o por bloques cuadrados para la descomposición
bidimensional). Se debe crear un directorio diferente para cada versión
paralela (Floyd_1, Floyd_2). Cada directorio mantendrá los mismos archivos
que se usan en la versión secuencial pero con diferente código. De esa
forma el Makefile se puede reutilizar y se percibe claramente la
diferencia entre versiones.
- Realizar medidas de tiempo
de ejecución sobre los algoritmos implementados. Para medir tiempos de
ejecución, podemos utilizar la función MPI_Wtime. Para asegurarnos de que
todos los procesadores comienzan su computación al mismo tiempo, podemos
utilizar MPI_Barrier. Las medidas deberán
excluir las fases de entrada/salida. Deberán realizarse las siguientes
medidas:
(A) Medidas para el algoritmo
secuencial (P=1).
(B) Medidas para el algoritmo paralelo (P=4). Las medidas deberán excluir las fases de entrada/salida, así como la fase de distribución inicial de la matriz A desde P0 y la fase de reunión del resultado en P0.
Las medidas deberán realizarse para diferentes tamaños de problema, para así poder comprobar el efecto de la granularidad sobre el rendimiento de los algoritmos. Se presentará una tabla con el siguiente formato:
(B) Medidas para el algoritmo paralelo (P=4). Las medidas deberán excluir las fases de entrada/salida, así como la fase de distribución inicial de la matriz A desde P0 y la fase de reunión del resultado en P0.
Las medidas deberán realizarse para diferentes tamaños de problema, para así poder comprobar el efecto de la granularidad sobre el rendimiento de los algoritmos. Se presentará una tabla con el siguiente formato:
Suponiendo que las P tareas se ejecutan sobre P
procesadores conectados todos con todos, y que las operaciones colectivas se han
implementado siguiendo algoritmos que asumen un hipercubo como topología de
conexión, obtener fórmulas de tiempo de ejecución para los algoritmos
implementados en base a parámetros del problema y a parámetros que caracterizan
la arquitectura (tc=tiempo que lleva una comparación, ts=tiempo de
inicialización de envío, tw=tiempo de transferencia por palabra).
PARA QUE SE USA EL ALGORITMO DE FLOYD
El algoritmo de Floyd-Warshall, explicado en 1959 por
Bernard Roy, es un algoritmo de análisis de grafos para encontrar el camino
mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre
todos los pares de vértices en una única ejecución.
Trabaja con la matriz D inicializada con las distancias
directas entre todo par de nodos. La iteración se realiza sobre nodos
intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor
para ir de i a j es a través de un nodo intermedio elegido o como estaba antes,
y esto lo probamos con todos los nodos de la red. Una vez probados todos los
nodos de la red como nodos intermedios, la matriz resultante da la mejor
distancia entre todo par de nodos.
BIOGRAFÍA DEL AUTOR
Robert W. (Bob) Floyd nació en Nueva York el 8 de Junio de 1936 y
murió el 25 septiembre 2001 en Stanford, California, fue un eminente científico
de la computación.
Sus contribuciones incluyen el diseño
del algoritmo de Floyd-Warshall (independientemente de Stephen Warshall ), que
se encuentra de manera eficiente todos los caminos más cortos en un gráfico ,
el ciclo del hallazgo de Floyd algoritmo para la detección de los ciclos en una
secuencia, y su trabajo en el análisis . En un artículo aislado que introdujo
el concepto importante de difusión de error para las imágenes que prestan,
también llamado Floyd-Steinberg tramado (aunque él distingue tramado de
difusión). Un logro importante fue pionero en el campo de la verificación de
programas con afirmaciones lógicas con los 1967 de papel asignar significados a
los programas. Esta fue una importante contribución a lo que más tarde se
convirtió en la lógica de Hoare.
Floyd terminó la escuela a los 14 años.
En la Universidad de Chicago , recibió una licenciatura en artes liberales en
1953 (cuando todavía sólo el 17) y una licenciatura en el segundo la física en
1958.
Floyd se convirtió en un miembro del
personal de la Fundación Armour Research (ahora IIT Research Institute) en el
Illinois Institute of Technology en 1950. Convertirse en un operador de la
computadora en la década de 1960, comenzó a publicar muchos artículos dignos de
mención y fue nombrado profesor asociado en la Universidad Carnegie Mellon en
el momento en que él tenía 27 años y se convirtió en un profesor de tiempo
completo en la Universidad de Stanford, seis años después. Obtuvo este puesto
de trabajo sin un Ph.D.
Recibió el Premio Turing en 1978
"para tener una clara influencia sobre las metodologías para la creación
de software eficiente y fiable, y para ayudar a encontrar los siguientes
subcampos importantes de la ciencia de la computación: la teoría del análisis ,
las semántica de los lenguajes de programación, manual del programa la verificación
, automática síntesis de programas y análisis de algoritmos ".
Floyd trabajó estrechamente con Donald
Knuth , en particular por lo que el crítico importante para el libro seminal de
Knuth El Arte de la Programación de Computadoras , y es la persona más citada
en este trabajo. Él era el co-autor, junto a Richard Beigel, del libro de texto
El lenguaje de las máquinas: una Introducción a la Computabilidad y Lenguajes
Formales (1994, WH Freeman and Company, ISBN 978-0-7167-8266-7 ). Floyd supervisado
7 doctorados .
Floyd casado y divorciado dos veces,
incluso con equipo científico Floyd Christiane , y tenía cuatro hijos. Sus
pasatiempos incluyen ir de excursión y él era un ávido backgammon jugador.
lunes, 15 de abril de 2013
EXPLICACION DEL ALGORITMO
El algoritmo de Floyd es más general que el de Dijkstra, ya que determina la ruta más corta entre dos nodos cualquiera de la red.
- El algoritmo representa una red de n nodos como una matriz cuadrada de orden n, la llamaremos matriz C. De esta forma, el valor Cijrepresenta el coste de ir desde el nodo i al nodo j, inicialmente en caso de no existir un arco entre ambos, el valor Cij será infinito.
- Definiremos otra matriz D, también cuadrada de orden n, cuyos elementos van a ser los nodos predecesores en el camino hacia el nodo origen, es decir, el valor Dij representará el nodo predecesor a j en el camino mínimo desde i hasta j. Inicialmente se comienza con caminos de longitud 1, por lo que Dij = i.
- Las diagonales de ambas matrices representan el coste y el nodo predecesor para ir de un nodo a si mismo, por lo que no sirven para nada, estarán bloqueadas.
Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes:
- Formar las matrices iniciales C y D.
- Se toma k=1.
- Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i≠k, j≠k e i≠j, hacemos:
Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj
- Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las iteraciones.
- La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino óptimo para ir de un vértice a otro.
codigo de algoritmo floyd
import
java.io.*;
for (int
i=0;i<n;i++)
} }
El algoritmo de Floyd es más general que el de Dijkstra, ya que determina la ruta más corta entre dos nodos cualquiera de la red.
codigo de algoritmo floyd
import
java.io.*;
public
class Floyd
{
static int
[ ][ ]floyd;
static
BufferedReader leer=new BufferedReader(new InputStreamReader(System.in));
public
static void main()
{
int n=0;
try {
System.out.print(“Ingrese n (tamaño de la matriz n X n) :
“);
n=Integer.parseInt(leer.readLine());
floyd=new
int[n][n];
for (int
i=0;i<n;i++)
for (int
j=0;j<n;j++)
{
System.out.println(“Inserte
la componente W(” + i + “)(” + j +”)”);
floyd[i][j]=Integer.parseInt(leer.readLine());
}
}
catch(Exception
e){}
for (int
k=0;k<=n-1;k++)
{
for (int
i=0;i<=n-1;i++)
{for (int
j=0;j<=n-1;j++)
if ((floyd[i][k]!=-1)&&(floyd[k][j]!=-1))
floyd[i][j]=funcionfloyd(floyd[i][j],floyd[i][k]+floyd[k][j]);}
}
System.out.println(“Matriz de adyacencia correspondiente:
“);
for (int
i=0;i<n;i++)
{
for (int
j=0;j<n;j++)
System.out.print(”
– “+floyd[i][j]);
System.out.println();
}
}
public
static int funcionfloyd(int A, int B)
{
if
((A==-1)&&(B==-1))
return -1;
else if
(A==-1)
return B;
else if
(B==-1)
return A;
else if
(A>B)
return B;
else return
A;
} }
ESTADO DEL ARTE FLOYD
Es un algoritmo de análisis
sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El
algoritmo encuentra el camino entre todos los pares de vértices en una única
ejecución. El algoritmo de Floyd es un ejemplo de programación
dinámica.
El algoritmo de Floyd 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 dos vértices, hasta que se sabe que la
estimación es óptima.
Como ya se ha mencionado, se basa en
el esquema de ‘programación dinámica’. Este método utiliza una tabla para ir
almacenando los resultados correspondientes a instancias más sencillas del
problema a resolver.
Suscribirse a:
Comentarios (Atom)