5 Teoría de Grafos

5.3 Algoritmos de Recorridos y Búsqueda

ALGORITMOS DE RECORRIDOS Y BÚSQUEDA.

A* es un algoritmo informático que se utiliza en la búsqueda de caminos y el recorrido del grafo, proceso de trazar un camino transitable de manera eficiente entre los dos puntos, llamados nodos.

5.3.1  ALGORITMOS DE RECORRIDO Y BÚSQUEDA EL CAMINO MAS CORTO

El problema del camino más corto es encontrar un camino entre dos vértices de tal manera que la suma de los pesos de las aristas sea mínima, para esto se utilizara el algoritmo de DIJKSTRA que es el siguiente:

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 almacenando los  valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

5.3.2  ALGORITMOS DE RECORRIDO Y BÚSQUEDA A LO ANCHO

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 generador de la componente conexa que contiene a v. Sea G(V, E) un grafo conexo y v un vértice de V. El algoritmo de búsqueda en anchura puede detallarse así: 1. Designamos a v como vértice activo y como raíz del árbol generador T que se construirá. Se le asigna a v la etiqueta 0. 2. Sea i=0 y S={v}. 3. Hallar el conjunto M de todos los vértices no etiquetados que son adyacentes a algún vértice de S. 4. Si M es vacío el algoritmo termina. En caso contrario, se etiquetan todos los vértices de M con i+1, se añaden a T las aristas entre cada vértice de S y su vecino en M y se hace S=M. 5. i=i+1 y volver al paso 3. Al terminar el proceso se habrá construido un árbol generador del grafo inicial. En caso de G no ser conexo, habría que modificar el algoritmo para encontrar un árbol generador de cada componente conexa de G. La complejidad de este algoritmo es O(max{n, m}). Como podemos observar tanto el algoritmo de búsqueda en profundidad como el algoritmo de búsqueda en anchura pueden ser utilizados para verificar si un grafo simple es o no conexo. El problema de decisión consistente en determinar si un grafo simple es o no conexo, es entonces un problema de la clase P, pues hemos encontrado dos algoritmos de tiempo polinomial que resuelven este problema.  

5.3.3 ALGORITMOS DE RECORRIDO Y BÚSQUEDA EN PROFUNDIDAD

En esta búsqueda se va marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado sin repetir ningún vértice.

Muchos algoritmos de grafos necesitan visitar de un modo sistemático todos los vértices de un grafo. En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste. Si dado un grafo simple G, escogemos un vértice v para iniciar la exploración del grafo utilizando la búsqueda en profundidad, el árbol que se construye es un árbol generador de la componente conexa del grafo que contiene a v. Sea G(V, E) un grafo conexo y v un vértice de V. El algoritmo de búsqueda en profundidad puede detallarse así: 1. Se comienza en un vértice v (vértice activo) y se toma como la raíz del árbol generador T que se construirá. Se marca el vértice v. 2. Se elige un vértice u, no marcado, entre los vecinos del vértice activo. Si no existe tal vértice, ir a 4. 3. Se añade la arista (v, u) al árbol T. Se marca el vértice u y se toma como activo. Ir al paso 2. 4. Si se han alcanzado todos los vértices de G el algoritmo termina. En caso contrario, se toma el vértice padre del vértice activo como nuevo vértice activo y se vuelve al paso 2. La complejidad de este algoritmo es O(max{n, m})

Referencias

Cruz, E. G. (4 de julio de 2016). Udea. Obtenido de http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C3_Profundidad.pdf

Leyva, M. A. (23 de febrero de 2015). sites.google.com. Obtenido de https://sites.google.com/site/matemaicasdiscretas/6-3-algoritmos-de-recorridos-y-búsqueda