5.3 ALGORITMOS DE RECORRIDO Y BÚSQUEDA

5.3 ALGORITMOS DE RECORRIDO Y BÚSQUEDA.

En ciencias de la computación, A* es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.)

Peter Hart , Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International ) describieron por primera vez el algoritmo en 1968.Se trata de una extensión de la Edsger Dijkstra algoritmo de 1959 .A* consigue un mejor rendimiento tiempo usando heurística.

5.3.1 EL CAMINO MAS CORTO.

En la teoría de grafos, el problema del camino más corto es el problema de encontrar un camino entre dos vértices (o nodos) en un gráfico de tal manera que la suma de los pesos de sus bordes constituyentes se reduce al mínimo. 

Esto es análogo al problema de encontrar el camino más corto entre dos intersecciones en un mapa de carreteras: vértices del gráfico corresponden a las intersecciones y los bordes corresponden a los segmentos de carretera, cada uno ponderado por la longitud de su segmento de carretera. 

Los algoritmos más importantes para la solución de este problema son: 

El algoritmo de Dijkstra: Resuelve las cortas de origen único problemas de ruta. 

Algoritmo de Bellman-Ford: Resuelve el problema de una sola fuente, si borde pesos pueden ser negativos. 

Un algoritmo de búsqueda *: Resuelve para el par de ruta más corta única utilizando la heurística para tratar de acelerar la búsqueda. 

Algoritmo de Floyd-Warshall: Resuelve todos los pares caminos más cortos.

Algoritmo de Johnson: Resuelve todos los pares de trayectorias más cortas, y puede ser más rápido que Floyd-Warshall en grafos dispersos.

Ahora bien, podemos emplear el algoritmo de Dijkstra para éstos casos, los pasos o procedimientos a seguir para éste algoritmo son los siguientes : Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi
4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

5.3.2 A LO ANCHO.

En ciencias de la computación, A * (pronunciado “Una estrella”) es un algoritmo informático que se utiliza ampliamente en la búsqueda de caminos y el recorrido del grafo, el proceso de trazar un camino transitable de manera eficiente entre los puntos, llamados nodos. Destaca por su rendimiento y precisión, que goza de amplio uso. (Sin embargo, en los sistemas de los viajes de enrutamiento prácticos, generalmente superado por algoritmos que pueden pre-procesar la gráfica para lograr un mejor rendimiento.)

Peter Hart, Nils Nilsson y Bertram Raphael del Instituto de Investigación de Stanford (ahora SRI International) describieron por primera vez el algoritmo en 1968. Se trata de una extensión de la Edsger Dijkstra algoritmo de 1959. A * consigue un mejor rendimiento tiempo usando heurística.

Ejemplo

Un ejemplo de una estrella (A *) algoritmo en acción donde los nodos son las ciudades conectadas con carreteras y h (x) es la distancia en línea recta al punto de destino:

Clave: verde: inicio, el azul: objetivo, de color anaranjado: visitado.

Nota: En este ejemplo se utiliza una coma como separador decimal.

Ilustración de la búsqueda A * para la búsqueda de ruta desde un nodo de inicio a un nodo objetivo en un robot de planificación de movimientos problema.

Una búsqueda de * que utiliza una heurística que es de 5,0 (= ε) veces a la heurística consistente, y obtiene una ruta subóptima.

La búsqueda en anchura es otro procedimiento para visitar sistemáticamente todos los vértices de un grafo. Es adecuado especialmente para resolver problemas de optimización, en los que se deba elegir la mejor solución entre varias posibles. Al igual que en la búsqueda en profundidad se comienza en un vértice v (la raíz) que es el primer vértice activo. En el siguiente paso se etiquetan como visitados todos los vecinos del vértice activo que no han sido etiquetados. Se continúa etiquetando todos los vecinos de los hijos de v (que no hayan sido visitados aún). En este proceso nunca se visita un vértice dos veces por lo que se construye un grafo sin ciclos, que será un árbol. 

5.3.3 EN PROFUNDIDAD.

En ciencias de la computación, recorrido del grafo es el problema de visitar todos los nodos en un gráfico de una manera particular, actualización y / o control de sus valores a lo largo del camino, recorrido del árbol es un caso especial del recorrido del grafo.

Una búsqueda en profundidad (DFS) es un algoritmo para recorrer un grafo finito. DFS visitas los nodos secundarios antes de visitar los nodos del mismo nivel, es decir, que atraviesa la profundidad de cualquier camino en particular antes de explorar su amplitud. Una pila (a menudo del programa pila de llamadas a través de recursión) se usa generalmente cuando la ejecución del algoritmo.

El algoritmo comienza con un nodo “raíz” elegida, entonces iterativamente transiciones desde el nodo actual a una, el nodo no visitado adyacente, hasta que ya no puede encontrar un nodo inexplorado para la transición a partir de su ubicación actual. El algoritmo entonces retrocede a lo largo de los nodos visitados anteriormente, hasta que encuentra un nodo conectado a un territorio aún más desconocido. A continuación, se procederá por el nuevo camino como antes, dando marcha atrás cuando se encuentra con callejones sin salida, y termina cuando el algoritmo ha retrocedido más allá del nodo original “root” desde el primer paso.

DFS es la base de muchos algoritmos de grafos conexos, incluyendo las clases topológicas y pruebas de planitud.

REFERECIAS:

Equipo9. (2014). TEORIA DE GRAFOS. 2017, de blogspot Sitio web: http://9relaciones.blogspot.mx/2014/11/teoria-de-grafos.html

Alex Ortegón. TEORÍA DE GRAFOS . 2017, de blogspot Sitio web: http://mate-discretasj2.blogspot.mx/p/blog-page.html