UNIDAD PROFESIONAL INTERDISCIPLINARIA DE INGENIERÍA CIENCIAS SOCIALES Y ADMINISTRATIVAS

INSTITUTO POLITÉCNICO NACIONAL[pic 1][pic 2][pic 3]

UNIDAD PROFESIONAL INTERDISCIPLINARIA DE INGENIERÍA CIENCIAS SOCIALES Y ADMINISTRATIVAS

Trabajo de investigación para 1er departamental

Redes y simulación

Profesor:

José Armando Arroyo Sánchez

Alumno:

Secuencia:

Fecha de entrega:

Jueves 8 de Marzo de 2017

Contenido

1.        ALGORITMOS CON LOS QUE SE PLANEA LA RUTA MAS CORTA EN LOS GPS        1

1.1 Algoritmo de Dijkstra.        1

1.1.1 Complejidad del algoritmo Dijsktra        2

1.2 Algoritmo de Dijkstra bidireccional        2

1.3 Algoritmo voraz        3

1.4 Algoritmo A*        3

1. Algoritmos con los que se planea la ruta mas corta en los GPS

Para el camino o ruta más corta que se usa en un GPS será necesaria la presencia delos grafos de los cuales un nodo representa una intersección de carreteras o un punto sin salida y una arista representa el segmento de una carretera que une dos intersecciones o una intersección y un punto sin salida.

1.1 Algoritmo de Dijkstra.

El GPS se encarga de encontrar la ruta más corta entre dos lugares definidos por el usuario, empleando carreteras que tienen una cierta longitud. Para representar esto en forma de grafo, éste debe ser finito y dirigido. Además, cada arista e tiene un peso que se corresponde con la distancia l(e)>0.

Uno de los algoritmos para calcular la ruta más corta entre un nodo origen y un nodo destino, conectados mediante aristas, con un peso positivo es el algoritmo de Dijkstra.

El algoritmo de Dijkstra consta de los siguientes pasos:

[pic 4]

[pic 5]

En la figura se puede observar como se expande el algoritmo de Dijkstra. Este algoritmo primero se expande a los nodos que tiene más cercanos a su alrededor, a continuación a los siguientes más cercanos. De este modo, el algoritmo de Dijkstra se expande en forma de bola.

1.1.1 Complejidad del algoritmo Dijsktra

En el paso 3 hay que encontrar del algoritmo hay que encontrar u un vértice en T para el cual λ (u) es mínimo, esto puede ser realizado en |T| - 1 comparaciones. Al comienzo T = V, pero T disminuye un nodo en cada iteración, por lo tanto la búsqueda es repetida |V| veces. En conclusión el tiempo total invertido en el paso 3 es O(|V|2). En el paso 5, si tenemos en cuenta todas las iteraciones, cada arista va a ser recorrida una sola vez por lo tanto el tiempo invertido es O(|E|). En el caso del GPS no tiene sentido que haya dos carreteras que tengan el mismo lugar de partida y el mismo lugar de llegada, ni que haya una carretera que parta de un lugar y vuelva al mismo lugar, entonces el grafo que consideramos no tendrá aristas paralelas ni bucles, entonces |E| ≤ |V| × (|V| - 1).

Por consiguiente, la complejidad del algoritmo es O(|V|2).

1.2 Algoritmo de Dijkstra bidireccional

        El algoritmo de búsqueda bidireccional alterna entre dos algoritmos de Dijkstra, uno del nodo inicial s al nodo destino t, llamado búsqueda hacia delante y el otro llamado búsqueda hacia atrás, del nodo destino t al nodo origen s. Observar que no es necesario que las aristas estén en ambas direcciones, simplemente en la búsqueda hacia atrás consideraremos las aristas en sentido contrario. El algoritmo va alternando ambas búsquedas hasta que sacan el mismo nodo del conjunto T (no tiene porqué ser a la vez), entonces se para la ejecución del algoritmo. En este punto el camino más corto puede ser encontrado recorriendo los predecesores (en ambas direcciones) del nodo en el que se han encontrado.

1.3 Algoritmo voraz

Un algoritmo voraz o greedy es aquel que, para resolver un determinado problema, en cada paso elige la opción óptima con la esperanza de llegar a una solución general óptima.

[pic 6]

En el caso de los grafos G(V, E) en el que cada arista e ∈ E tienen una longitud asociada l(e), en cada vértice v ∈ V , se elige tomar la arista asociada que tenga menor longitud.

Cada arista e se evalúa una única vez, siendo descartada o seleccionada, de tal forma que si es seleccionada forma parte de la solución, y si es descartada, no forma parte de la solución ni volverá a ser considerada para la misma. De ahí viene su nombre, voraz. Al contrario que con otros métodos algorítmicos, no siempre es posible dar una solución a un problema empleando un algoritmo voraz.

El algoritmo voraz como máximo va a recorrer todos los vértices de V antes de encontrar la solución, por lo tanto tiene una complejidad lineal O(|V|). También podría existir otro algoritmo voraz que se mueva al nodo que está más cerca del nodo destino empleando para ello una heurística.

1.4 Algoritmo A*

El algoritmo A∗ es un algoritmo de búsqueda que encuentra el camino de menor longitud entre dos puntos, siempre y cuando se cumplan una serie de condiciones. El algoritmo A∗ se dice que es un algoritmo informado, ya que en cada paso decidimos qué rama seguir dependiendo de una regla o heurística. La heurística es una función que nos da información sobre ciertas partes del grafo, aunque todavía no hayan sido estudiadas. El uso de una heurística permite resolver un problema de manera más rápida que los algoritmos no informados, como pueden ser el de Dijkstra, el bidireccional o el voraz.

Es un algoritmo que tiene un cierto paralelismo con el algoritmo de Dijkstra. Se trata de un algoritmo heurístico, ya que una de sus principales características es que hace uso de h(n) una función heurística, h(n) ≥ 0 porque es la distancia de n al nodo destino. Esta expresa la idea de cuán lejos se está de alcanzar el nodo destino, y de su correcta elección dependerá en gran medida el rendimiento del algoritmo A*. Así, en el caso de que esta función heurística no sobrestime nunca el valor de la distancia real entre el nodo y el destino, se dice que es admisible, y está garantizada la solución óptima. Por el contrario, en el caso en que la función no sea admisible, no se puede garantizar el hallazgo de la solución óptima para el problema del camino más corto. La cause por la que se les llama funciones admisibles es porque un algoritmo se denomina admisible si garantiza encontrar un camino óptimo del nodo origen s al nodo destino t.

...