Mdelo De La Ruta Mas Corta
Páginas: 7 (1501 palabras)
Publicado: 9 de julio de 2011
MODELO DE LA RUTA MÁS CORTA
CONCEPTOS
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. El problema se resuelve por el "algoritmo de etiquetado".
La esencia delprocedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.
CARACTERISTICAS
Determina el camino más corto dado un vértice origen.
Utiliza un tipo de estructura decola llamado cola de prioridad.
ORIGEN DEL ALGORITMO DE DIJKSTRA Y EJEMPLO DE ESTE ALGORITMO
ORIGEN
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funcionaen grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
ALGORITMO
Paso 1 [Inicialización]
T = {s} el conjunto de nodos incorporado sólo consta del nodo origen
L(n) = w(s, n) para n ≠ s
El coste inicialde las rutas a los nodos vecinos es el asociado a los enlaces
Paso 2 [Obtención del siguiente nodo]
Se busca el nodo vecino que no esté en T con el camino de menor coste
Incorporar el nodo en T
También se incorporará el enlace desde ese nodo hasta un nodo de T que forma parte del camino
Paso 3 [Actualización de los caminos de mínimo coste]
L(n) = min[L(n), L(x) + w(x, n)] para todon ∉ T
El algoritmo concluye cuando todos los nodos han sido añadidos a T
EJEMPLO
[pic]
Se quiere llegar del nodo V1 al nodo V6
|Iteración |T |L(2) |
|Los Ángeles |1 000 |1 690 |
|Detroit |1 250|1 350 |
|Nueva Orleans |1 275 |850 |
Esto produce en costo por automóvil a razón de 8 centavos por milla recorrida. Produce los costos siguientes (redondeados a enteros), que representan a C i j del modelo original:
Mediante el uso de códigos numéricos que representan las plantas y centros dedistribución, hacemos que X i j represente el número de automóviles transportados de la fuente i al destino j. Como la oferta total ( = 1 000 + 1 500 + 1 200 = 3 700) es igual a la demanda ( = 2 300 + 1 400 = 3 700), el modelo de transporte resultante esta equilibrado. Por lo tanto, el siguiente modelo de PL que representa el problema tiene todas las restricciones de igualdad.
Minimizar Z =80X 11 + 215X 12 + 100X 21 + 108X 22 + 102X 31 + 68X 32
Sujeto a:
|X 11 |X 12 | | | | |= 1 000 |
| | |X 21 |X 22 | | |= 1 500 |
| | | | |X 31 |X 32...
CONCEPTOS
El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. El problema se resuelve por el "algoritmo de etiquetado".
La esencia delprocedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.
CARACTERISTICAS
Determina el camino más corto dado un vértice origen.
Utiliza un tipo de estructura decola llamado cola de prioridad.
ORIGEN DEL ALGORITMO DE DIJKSTRA Y EJEMPLO DE ESTE ALGORITMO
ORIGEN
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funcionaen grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
ALGORITMO
Paso 1 [Inicialización]
T = {s} el conjunto de nodos incorporado sólo consta del nodo origen
L(n) = w(s, n) para n ≠ s
El coste inicialde las rutas a los nodos vecinos es el asociado a los enlaces
Paso 2 [Obtención del siguiente nodo]
Se busca el nodo vecino que no esté en T con el camino de menor coste
Incorporar el nodo en T
También se incorporará el enlace desde ese nodo hasta un nodo de T que forma parte del camino
Paso 3 [Actualización de los caminos de mínimo coste]
L(n) = min[L(n), L(x) + w(x, n)] para todon ∉ T
El algoritmo concluye cuando todos los nodos han sido añadidos a T
EJEMPLO
[pic]
Se quiere llegar del nodo V1 al nodo V6
|Iteración |T |L(2) |
|Los Ángeles |1 000 |1 690 |
|Detroit |1 250|1 350 |
|Nueva Orleans |1 275 |850 |
Esto produce en costo por automóvil a razón de 8 centavos por milla recorrida. Produce los costos siguientes (redondeados a enteros), que representan a C i j del modelo original:
Mediante el uso de códigos numéricos que representan las plantas y centros dedistribución, hacemos que X i j represente el número de automóviles transportados de la fuente i al destino j. Como la oferta total ( = 1 000 + 1 500 + 1 200 = 3 700) es igual a la demanda ( = 2 300 + 1 400 = 3 700), el modelo de transporte resultante esta equilibrado. Por lo tanto, el siguiente modelo de PL que representa el problema tiene todas las restricciones de igualdad.
Minimizar Z =80X 11 + 215X 12 + 100X 21 + 108X 22 + 102X 31 + 68X 32
Sujeto a:
|X 11 |X 12 | | | | |= 1 000 |
| | |X 21 |X 22 | | |= 1 500 |
| | | | |X 31 |X 32...
Leer documento completo
Regístrate para leer el documento completo.