Escuela superior politécnica del litoral facultad de Ingeniería en Electricidad y Computación



Descargar 396.87 Kb.
Página5/10
Fecha de conversión24.03.2017
Tamaño396.87 Kb.
1   2   3   4   5   6   7   8   9   10

Algoritmos de Rutas Mínimas


Para encontrar rutas mínimas es necesario calcular el camino más corto desde un nodo de origen a un nodo destino. Existen dos algoritmos importantes para el camino más corto entre dos nodos: Dijkstra y A-star, ambos se describen brevemente en esta sección.



  1. Dijkstra

El algoritmo de Dijkstra, concebido por el holandés Edsger Dijkstra, científico de computación en 1959, es un algoritmo de búsqueda de grafos que resuelve el problema de ruta más corta para un grafo con los costos de enlace no negativo.


Se da un grafo G donde cada enlace es asignado a un costo no negativo y también se tiene un nodo de inicio s y un nodo destino g. Se requiere la ruta de menos costo de s a g.
Procedimiento de la ruta más corta de Dijkstra.


  1. Inicializar Q con el conjunto de par simple (s, 0).

  2. S 0.

  3. Mientras Q no es vacío y S no contiene una

asignación a g:

  1. Remover un par (n, w) de Q con costo w mínimo

(sobre todos los elementos de Q).

  1. Si S no contiene un costo para n, por ejemplo, si

S no contiene cualquier par de la forma (n, w’),

entonces:



  1. Añada (n, w) a S.

  2. Para cada enlace (n, m) con costo w’ en el

grafo G añada el par (m, w + w’) a Q.

  1. Si S contiene una asignación a g entonces termina

con éxito (una ruta ha sido encontrada) sino

termina con fracaso (no hay ruta).


Note que si removiendo (n, w) de Q resulta en añadiendo (m, w’) entonces porque los costos de enlace son no negativos se tiene que w’ ≥ w. Esto implica que los costos removidos de Q monótonamente incrementan. Esto implica que cuando un par (n, w) es añadido a S, w es el costo de la ruta más corta a n.
Luego de haber encontrado la ruta más corta, se puede leer la ruta más corto desde el origen al destino por iteración:
S := secuencia vacía

u := destino



Mientras previous[u] es definido:

inserte u en el inicio de S

u := previous[u]
La secuencia S es la lista de nodos que constituyen una de las rutas más cortas del destino al origen, o una secuencia vacía si no existe camino.

    1. A-star


A * (pronunciado como “A star”) es uno de los mejores algoritmos de búsqueda de grafos que encuentra el camino de menor costo de un nodo inicial a un nodo final (de uno o más objetivos posibles).


El algoritmo fue descrito por primera vez en 1968 por Peter Hart, NilsNilsson, y Bertram Raphael [10]. En su documento, es llamado algoritmo A. Desde que se usó este algoritmo produjo un comportamiento óptimo para una heurística dada, por lo que se lo ha denominado A*.
El siguiente procedimiento difiere de la ruta de menor costo de Dijkstra solamente en la prioridad usada en el paso 4.
Procedimiento A*


  1. Inicialice Q a ser el conjunto conteniendo el par

simple (s, 0).

  1. S 0.

  2. Mientras Q no es vacío y S no contiene una

asignación a g:

  1. Remover un par (n, w) de Q minimizando w +

h(n) (sobre todos los elementos de Q).

  1. Si S no contiene un costo para n, por ejemplo,

si S no contiene cualquier par de la forma (n,

w’), entonces:



  1. Añada (n, w) a S.

  2. Para cada enlace (n, m) con costo w’ en el

grafo G añada el par (m, w + w’) a Q.

  1. Si S contiene una asignación a g entonces termina

con éxito (una ruta ha sido encontrada) sino

termina con fracaso (no hay ruta).

Si h es monótono entonces la suma w + h(n) de el ítem removido de la cola monótonamente incrementa. Esto implica que cuando se remueve (n, w) de la cola, el costo w es el menor costo posible para n. La monotonicidad sólo da exactitud del algoritmo.
Tomando la distancia a la meta en cuenta A* puede ser bastamente más eficiente que la ruta más corta de Dijkstra.
El algoritmo A* dirige la búsqueda hacia la meta deseada preferentemente que explorando los nodos basado simplemente sobre la distancia del vértice inicial. La idea clave es definir una función heurística que estime cuán lejos un vértice dado n esta del vértice destino. Preferentemente que tratando de minimizar la distancia del vértice inicial, se debe entonces correr el algoritmo de ruta más corta de Dijkstra con la noción de distancia definida como la suma de la distancia real y la función heurística. Eso es, cuando seleccionamos un vértice a quitar de la cola, preferentemente que seleccionando la distancia mínima actual, el algoritmo selecciona el vértice que minimiza esta suma.
Idealmente, una función heurística satisface dos propiedades:


  • Una función heurística es admisible si ello nunca sobrestima la distancia al vértice destino. Por ejemplo, cuando la función heurística es aplicada al vértice destino por sí mismo, ello debe retornar cero. La admisibilidad asegura que cuando el vértice destino es primero encontrado por la búsqueda, la ruta usada es una ruta óptima. Para el prototipo a implementar, se utilizará como heurística admisible la distancia Euclideana (distancia en línea recta) entre el vértice dado y el vértice destino. Esta heurística ayudará a dirigir la búsqueda, que es también claramente admisible.

  • Una función heurística es monotónica si la combinación de distancia+heurística del vértice inicial nunca decrementa a lo largo de cualquier ruta. Esto es actualmente una propiedad más fuerte que la admisibilidad: si una función es monotónica, ello debe ser también admisible. La mayoría de las funciones admisibles son también monotónicas. Monotonicidad corresponde al requerimiento de Dijkstra que el grafo contenga enlaces de costo no negativo.

1   2   3   4   5   6   7   8   9   10


La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal