ALGORITMO
DE WARSHALL
Concepto
En informática, el algoritmo de
Floyd-Warshall, descrito en 1959 por Bernard Roy, 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 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 tabla con todas las distancias mínimas entre pares de ciudades de un mapa,
indicando además la ruta a seguir para ir de la primera ciudad a la segunda.
Este es uno de los problemas más interesantes que se pueden resolver con
algoritmos de grafos.
Existen varias
soluciones a este problema y los algoritmos a aplicar dependen también de la
existencia de arcos con pesos o costes negativos en el grafo. En el caso de no
existir pesos negativos, sería posible ejecutar V veces el algoritmo de
Dijkstra para el cálculo del camino mínimo, donde V es el número de vértices o
nodos del grafo. Esto conllevaría un tiempo de ejecución de O(V^3) (aunque se
puede reducir). Si existen arcos con pesos negativos, se puede ejecutar también
V veces el Algoritmo de Bellman-Ford, una vez para cada nodo del grafo. Para
grafos densos (con muchas conexiones o arcos) esto conllevaría un tiempo de
ejecución de O(V^4).
El algoritmo de
Floyd-Warshall ('All-Pairs-Shortest-Path' - Todos los caminos mínimos) 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. Éste puede
resolver el problema con pesos negativos y tiempos de ejecución iguales a
O(V^33); sin embargo, para ciclos de peso negativo el algoritmo tiene problemas.
A continuación se muestra el pseudocódigo del algoritmo:
Aplicación de
ejemplo
El algoritmo de Floyd-Warshall puede ser
utilizado para resolver los siguientes problemas:
Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo
de Warshall. El grafo es un grafo no ponderado y representado por una matriz
booleana de adyacencia. Entonces la operación de adición es reemplazada por
la conjunción lógica(AND) y la operación menor por la disyunción lógica (OR).
Encontrar una expresión regular dada por un lenguaje regular aceptado
por un autómata finito (algoritmo de Kleene).
Ruta óptima. En esta aplicación es interesante
encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en
lugar de tomar los mínimos con el pseudocódigo anterior, se coge el máximo. Los
pesos de las aristas representan las limitaciones del flujo. Los pesos de los
caminos representan cuellos de botella; por ello, la operación de adición
anterior es reemplazada por la operación mínimo.
Comprobar si un grafo no dirigido es
bipartito.
RUTA CRITICA
El método de la ruta crítica CPM (Critical
Path Method) es un algoritmo basado en la teoría de redes diseñado para
facilitar la planificación de proyectos. El resultado final del CPM será un
cronograma para el proyecto, en el cual se podrá conocer la duración total del
mismo, y la clasificación de las actividades según su criticidad. El algoritmo
CPM se desarrolla mediante intervalos determinísticos, lo cual lo diferencia
del método PERT que
supone tiempos probabilísticos.
¿Cómo
funciona?
Regla 1: Cada actividad se debe representar sí y sólo
sí, por un ramal o arco.
www.ingenieriaindustrialonline.com
Regla
2: Cada actividad debe estar identificada por dos
nodos distintos. En el caso de existir actividades concurrentes (que inicien al
mismo tiempo, o que el inicio de una actividad dependa de la finalización de 2
o más actividades distintas) se debe recurrir a actividades ficticias
(representadas por arcos punteados que no consumen ni tiempo ni recursos) para
satisfacer esta regla.
Ejemplo
A diferencia de la técnica de revisión y evaluación de
programas (PERT), el
método de la ruta crítica usa tiempos ciertos (reales o determinísticos). Sin
embargo, la elaboración de un proyecto basándose en redes CPM y PERT son
similares y consisten en:
·
Identificar
todas las actividades que involucra el proyecto, lo que significa, determinar
relaciones de precedencia, tiempos técnicos para cada una de las actividades.
·
Construir
una red con
base en nodos y actividades (o arcos, según el método más usado), que implican
el proyecto.
·
Analizar los cálculos específicos, identificando la
ruta crítica y las holguras de las actividades que componen el proyecto.
En términos
prácticos, la ruta crítica se interpreta como la dimensión máxima que puede
durar el proyecto y las diferencias con las otras rutas que no sean la crítica,
se denominan tiempos de holgura.
Teoría de
Grafos
La teoría de grafos (también
llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que
estudia las propiedades de los grafos (también llamadas gráficas,
que no se debe confundir con las gráficas que tienen una
acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y
el conjunto de aristas, líneas o lados que
pueden ser orientados o no. Por
ello, también se conoce como análisis de redes.1
La teoría de grafos
es una rama de las matemáticas discretas y de las matemáticas aplicadas, y es un tratado que
usa diferentes conceptos de diversas áreas como combinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topología.
Actualmente ha tenido
mayor preponderancia en el campo de la informática, las computación
y telecomunicaciones.
Ejemplos
hoy en día de la teoría de grafos
Gracias a la teoría
de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales,
contadores o sistemas de apertura. Se utiliza para diferentes áreas por
ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.
Los grafos se
utilizan también para modelar trayectos como el de una línea de autobús a
través de las calles de una ciudad, en el que podemos obtener caminos óptimos
para el trayecto aplicando diversos algoritmos como puede ser el
algoritmo de Floyd.
Para la
administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de
programas (PERT) en
las que se modelan los mismos utilizando grafos y optimizando los tiempos para
concretar los mismos.
La teoría de grafos
también ha servido de inspiración para las ciencias sociales, en especial para
desarrollar un concepto no metafórico de red social que sustituye los
nodos por los actores sociales y verifica la posición, centralidad e
importancia de cada actor dentro de la red. Esta medida permite cuantificar y
abstraer relaciones complejas, de manera que la estructura social puede
representarse gráficamente. Por ejemplo, una red social puede representar la
estructura de poder dentro de una sociedad al identificar los vínculos
(aristas), su dirección e intensidad y da idea de la manera en que el poder se
transmite y a quiénes.
Se emplea en
problemas de control de producción, para proyectar redes de ordenadores, para
diseñar módulos electrónicos modernos y proyectar sistemas físicos con
parámetros localizados (mecánicos, acústicos y eléctricos).
Se usa para la
solución de problemas de genética y problemas de automatización de la proyección
(SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la
información. Acude en las investigaciones nucleares (técnica de diagramas de
Feynman).5
Los grafos son
importantes en el estudio de la biología y hábitat. El vértice
representa un hábitat y las aristas (o "edges" en inglés) representa
los senderos de los animales o las migraciones. Con esta información, los
científicos pueden entender cómo esto puede cambiar o afectar a las especies en
su hábitat.
Algoritmo de la esquina noroeste
El método
de la esquina Noroeste es un
algoritmo heurístico capaz de solucionar problemas de
transporte o distribución mediante
la consecución de una solución básica inicial que satisfaga todas las
restricciones existentes sin que esto implique que se alcance el costo óptimo
total.
¿Cómo funciona?
Este método tiene como ventaja frente a sus similares
la rapidez de su ejecución, y es utilizado con mayor frecuencia en
ejercicios donde el número de fuentes y destinos sea muy elevado.
Su nombre se debe al génesis del algoritmo, el cual
inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad
de métodos que se basen en la misma metodología de la esquina Noroeste, dado
que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o
Suroeste.
Aplicación en un ejemplo detallado
Se parte por esbozar en forma matricial el problema, es
decir, filas que representen fuentes y columnas que representen destinos, luego
el algoritmo debe de iniciar en la celda, ruta o esquina Noroeste de la tabla
(esquina superior izquierda).
PASO 1:
En la celda seleccionada como esquina Noroeste se debe
asignar la máxima cantidad de unidades posibles, cantidad que se ve restringida
ya sea por las restricciones de oferta o de demanda. En este mismo paso se
procede a ajustar la oferta y demanda de la fila y columna afectada, restándole
la cantidad asignada a la celda.
PASO 2:
En este paso se procede a eliminar la fila o destino cuya
oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas
son cero arbitrariamente se elige cual eliminar y la restante se deja con
demanda u oferta cero (0) según sea el caso.
PASO 3:
Una vez en este paso existen dos posibilidades, la
primera que quede un solo renglón o columna, si este es el caso se ha llegado
al final el método, "detenerse".
La segunda es que quede más de un renglón o columna, si
este es el caso iniciar nuevamente el "Paso 1".
CPM - MÉTODO DE LA RUTA CRÍTICA
El método de la ruta crítica CPM (Critical Path Method)
es un algoritmo basado en la teoría de redes diseñado para facilitar la
planificación de proyectos. El resultado final del CPM será un cronograma para
el proyecto, en el cual se podrá conocer la duración total del mismo, y la
clasificación de las actividades según su criticidad. El algoritmo CPM se
desarrolla mediante intervalos determinísticos, lo cual lo diferencia del
método PERT que supone tiempos
probabilísticos.
CONCEPTOS
BÁSICOS PARA DIAGRAMAR ACTIVIDADES CON REDES
Regla 1: Cada actividad se debe representar sí y sólo
sí, por un ramal o arco.
www.ingenieriaindustrialonline.com
Regla
2: Cada actividad debe estar identificada por dos
nodos distintos. En el caso de existir actividades concurrentes (que inicien al
mismo tiempo, o que el inicio de una actividad dependa de la finalización de 2
o más actividades distintas) se debe recurrir a actividades ficticias
(representadas por arcos punteados que no consumen ni tiempo ni recursos) para
satisfacer esta regla.
A diferencia de la técnica de revisión y evaluación de
programas (PERT), el
método de la ruta crítica usa tiempos ciertos (reales o determinísticos). Sin
embargo, la elaboración de un proyecto basándose en redes CPM y PERT son
similares y consisten en:
·
Identificar
todas las actividades que involucra el proyecto, lo que significa, determinar
relaciones de precedencia, tiempos técnicos para cada una de las actividades.
·
Construir
una red con
base en nodos y actividades (o arcos, según el método más usado), que implican
el proyecto.
·
Analizar los cálculos específicos, identificando la
ruta crítica y las holguras de las actividades que componen el proyecto.
En términos
prácticos, la ruta crítica se interpreta como la dimensión máxima que puede
durar el proyecto y las diferencias con las otras rutas que no sean la crítica,
se denominan tiempos de holgura.
