Matemáticas - Teoría de grafos

Algoritmos de grafos

 algoritmo de búsqueda A* (pronunciado "A asterisco" o "A estrella") se clasifica dentro de los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo.

Ejemplo de aplicación del algoritmo A*.

Motivación y descripción

El problema de algunos algoritmos de búsqueda en grafos informados, como puede ser el algoritmo voraz, es que se guían en exclusiva por la función heurística, la cual puede no indicar el camino de coste más bajo, o por el coste real de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el caso de que sea necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante intuitivo el hecho de que un buen algoritmo de búsqueda informada debería tener en cuenta ambos factores, el valor heurístico de los nodos y el coste real del recorrido.

Así, el algoritmo A* utiliza una función de evaluación ${\displaystyle f(n)=g(n)+h'(n)}$, donde ${\displaystyle h'(n)}$ representa el valor heurístico del nodo a evaluar desde el actual, n, hasta el final, y ${\displaystyle g(n)}$, el coste real del camino recorrido para llegar a dicho nodo, n, desde el nodo inicial. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor ${\displaystyle f(n)}$ de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados. En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la ${\displaystyle f(n)}$ de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.

El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que ${\displaystyle h'(n)}$ tiende a primero en profundidad, ${\displaystyle g(n)}$tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.

Propiedades

Como todo algoritmo de búsqueda en amplitud, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella.

Si para todo nodo n del grafo se cumple ${\displaystyle g(n)=0}$, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple ${\displaystyle h(n)=0}$, A* pasa a ser una búsqueda de coste uniforme no informada.

Para garantizar la optimización del algoritmo, la función ${\displaystyle h(n)}$ debe ser heurística admisible, esto es, que no sobrestime el coste real de alcanzar el nodo objetivo.

De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que ${\displaystyle h(n)}$ es consistente (o monótona), es decir, que para cualquier nodo ${\displaystyle n}$ y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el objetivo desde el sucesor.

Complejidad computacional

La complejidad computacional del algoritmo está íntimamente relacionada con la calidad de la heurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el caso mejor, con una buena ${\displaystyle h'(n)}$, el algoritmo se ejecutará en tiempo lineal. Para que esto último suceda, se debe cumplir que

${\displaystyle h'(x)\leq g(y)-g(x)+h'(y)}$

donde h' es una heurística óptima para el problema, como por ejemplo, el coste real de alcanzar el objetivo.

Complejidad en memoria

El espacio requerido por A* para ser ejecutado es su mayor problema. Dado que tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema. Para solucionar este problema, se han propuesto diversas variaciones de este algoritmo, como pueden ser RTA*, IDA* o SMA*.

Implementación en pseudocódigo

Tratar punto

.:= .
                                   // coste del camino hasta .

caso . = . perteneciente a ()
   si g(.) < g(.) entonces // (-----)
      // nos quedamos con el camino de menor coste
      .:= MEJORNODO
      actualizar g(.) y f'(.)
      propagar g a . de .
   eliminar .
   añadir . a ._MEJORNODO
caso . = . perteneciente a )-----(
   si g(.) < g(.) entonces
      // nos quedamos con el camino de menor coste
      .:= MEJORNODO
      actualizar g(.) y f'(.)
   eliminar .
   añadir . a ._MEJORNODO
caso . no estaba en ).( ni (.)
   añadir . a ).(
   añadir . a ._MEJORNODO
   f'(.) := g(.) + h'(.)

Implementación en pseudocódigo

ABIERTOS := [INICIAL] //inicialización 
CERRADOS := [] 
f'(INICIAL) := h'(INICIAL) 
repetir 
si ABIERTOS = [] entonces FALLO 
si no // quedan nodos 
extraer MEJORNODO de ABIERTOS con f' mí­nima 
// cola de prioridad 
mover MEJORNODO de ABIERTOS a CERRADOS 
si MEJORNODO contiene estado_objetivo entonces 
SOLUCION_ENCONTRADA := TRUE 
si no 
generar SUCESORES de MEJORNODO 
para cada SUCESOR hacer TRATAR_SUCESOR 
hasta SOLUCION_ENCONTRADA o FALLO

Tratar sucesor

SUCESOR.ANTERIOR := VIEJO 
// coste del camino hasta SUCESOR 

caso SUCESOR = VIEJO perteneciente a CERRADOS 
si g(SUCESOR) < g(VIEJO) entonces // (no si monotoní­a) 
// nos quedamos con el camino de menor coste 
VIEJO.ANTERIOR := MEJORNODO 
actualizar g(VIEJO) y f'(VIEJO) 
propagar g a sucesores de VIEJO 
eliminar SUCESOR 
añadir VIEJO a SUCESORES_MEJORNODO 
caso SUCESOR = VIEJO perteneciente a ABIERTOS 
si g(SUCESOR) < g(VIEJO) entonces 
// nos quedamos con el camino de menor coste 
VIEJO.ANTERIOR := MEJORNODO 
actualizar g(VIEJO) y f'(VIEJO) 
eliminar SUCESOR 
añadir VIEJO a SUCESORES_MEJORNODO 
caso SUCESOR no estaba en ABIERTOS ni CERRADOS 
añadir SUCESOR a ABIERTOS 
añadir SUCESOR a SUCESORES_MEJORNODO 
f'(SUCESOR) := g(SUCESOR) + h'(SUCESOR)

Observaciones

Como se mencionó anteriormente ${\displaystyle h'(x)}$ es un estimador de ${\displaystyle h(x)}$ que informa la distancia al nodo objetivo, entonces

Si ${\displaystyle h'(x)}$ hace un estimación perfecta de ${\displaystyle h(x)}$, A* converge inmediatamente al objetivo.

Si ${\displaystyle h'(x)}$ = 0, la función ${\displaystyle g(x)}$ controla la búsqueda.

Si ${\displaystyle h'(x)}$ = 0 y ${\displaystyle g(x)}$ =0 la búsqueda será aleatoria.

Si ${\displaystyle h'(x)}$ = 0 y ${\displaystyle g(x)}$ =1 o constante la búsqueda será Primero en Anchura.

Si ${\displaystyle h'(x)}$ nunca sobrestima a ${\displaystyle h(x)}$ (o subestima), se garantiza encontrar el camino óptimo, pero se desperdicia esfuerzo explorando otras rutas que parecieron buenas.

Si ${\displaystyle h'(x)}$ sobrestima a ${\displaystyle h(x)}$, no puede garantizarse la consecución del camino del menor coste.

El algoritmo A* ^[24]es un algoritmo de búsqueda que puede ser empleado para el cálculo de caminos mínimos en una red. Se va a tratar de un algoritmo heurístico, ya que una de sus principales características es que hará uso de una función de evaluación heurística, mediante la cual etiquetará los diferentes nodos de la red y que servirá para determinar la probabilidad de dichos nodos de pertenecer al camino óptimo.

Esta función de evaluación que etiquetará los nodos de la red estará compuesta a su vez por otras dos funciones. Una de ellas indicará la distancia actual desde el nodo origen hasta el nodo a etiquetar, y la otra expresará la distancia estimada desde este nodo a etiquetar hasta el nodo destino hasta el que se pretende encontrar un camino mínimo. Es decir, si se pretende encontrar el camino más corto desde el nodo origen s, hasta el nodo destino t, un nodo intermedio de la red n tendría la siguiente función de evaluación f(n) como etiqueta:

f(n)= g(n) + h(n)

Donde:

-g(n) indica la distancia del camino desde el nodo origen s al n.

-h(n) expresa la distancia estimada desde el nodo n hasta el nodo destino t.

h(n) se trata de una función heurística, expresa la idea de cuán lejos aún se está de alcanzar el nodo destino, y de su correcta elección dependerá en gran medida el rendimiento del algoritmo A* al aplicarlo en una red. Así, en el caso de que esta función heurística nunca sobreestime 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 contario, 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.

A la función de evaluación f que caracteriza a un nodo y que sirve para etiquetarlo, también se la conoce como mérito de ese nodo, y expresa la probabilidad del nodo de estar en el camino más corto. Cuanto menor sea el mérito de un nodo, es decir, cuanto menor sea el valor de su función de evaluación, más probable será que el camino más corto atraviese ese nodo. En este mérito de los diferentes todos se basará el funcionamiento del algoritmo A*. El algoritmo irá explorando nodos de la red y sus sucesores (aquellos nodos con lo que les une algún enlace) basándose en su valor de mérito. Es decir, mantendrá una lista ordenada por valor creciente de mérito de los nodos que pueden ser explorados, y de ahí seleccionará el de menor valor, que será el primero de la lista. El algoritmo empezará analizando el nodo que se toma como origen para el problema del camino más corto. Calculará su mérito, y a continuación pasará a explorar sus nodos sucesores, es decir, los nodos con los que esté unido por un enlace este nodo fuente. Para estos nodos se calculará su mérito, y se seleccionará aquél de ellos que presente un menor valor, que será el que se someterá a análisis. Ahora el algoritmo continuará su ejecución explorando los nodos vecinos de ese nodo con merito menor, y así sucesivamente, hasta llegar al caso donde el nodo a analizar sea el nodo destino del problema, momento en que el algoritmo termina y ya se dispone de la solución. Para llevar a cabo este funcionamiento será necesario un registro donde el algoritmo ira guardando el conjunto de nodos que han sido explorados con sus valores correspondientes de mérito, y de donde se irán eliminando aquellos que sean seleccionados para ser analizados.

El funcionamiento anteriormente descrito del algoritmo A*, puede ser esquematizado mediante la siguiente sucesión de pasos:

Algoritmo A*

1.- Establecer el nodo s como origen. Hacer f(s)=0, y f(i)=∞ para todos los nodos i diferentes del nodo s. Iniciar el conjunto Q vacío. 2.- Calcular el valor de f(s) y mover el nodo s al conjunto Q . 3.- Seleccionar el nodo i del conjunto Q que presente menor valor de la función f(i) y eliminarlo del conjunto Q. 4.- Analizar los nodos vecinos j de i. Para cada enlace (i, j) con coste cij hacer: 4.1.-Calcular: f(j)’=g(i)+cij +h(j) 4.2.-Si f(j)’ 4.2.1.-Actualizar la etiqueta de j y su nuevo valor será: f(j)= g(i)+cij +h(i) 4.2.2.-Insertar el nodo j en Q 4.3.-Si f(j)’≥f(j) 4.3.1.-Dejar la etiqueta de j como está, con su valor f(j) 5.- Si Q está vacío el algoritmo se termina. Si no está vacío, volver al paso 3.

Este algoritmo permite una implementación conservadora de memoria puesto que sólo necesita almacenar en su estado los nodos visitados según lo indica su heurística.

 algoritmo de Christofides es un algoritmo aproximado que permite resolver instancias del problema del viajante de comercio (designado convencionalmente por suacrónimo en inglés, TSP) en donde los pesos de las aristas del grafo satisfacen la desigualdad triangular. Fue desarrollado en 1976 por Nicos Christofides, profesor delImperial College London.¹

Supongamos que ${\displaystyle G=(V,w)}$ representa una instancia del TSP, en donde ${\displaystyle G}$ es un grafo completo definido por: un conjunto ${\displaystyle V}$ de vértices o nodos y una función ${\displaystyle w}$ que asocia un peso o valor real positivo a cada arista del grafo ${\displaystyle G}$.

Descripción

A continuación, se describen las fases del algoritmo en pseudocódigo:²

1. Obtener el árbol recubridor mínimo T de G.
2. Sea O el conjunto de vértices de grado impar en T, hallar un apareamiento perfecto M de mínimo peso en el grafo completo sobre los vértices de O.
3. Combinar las aristas de M y T para crear el multigrafo H.
4. Obtener un ciclo euleriano en H (H se considera "euleriano" si es conexo y solo presenta vértices de grado par).
5. Obtener un ciclo hamiltoniano a partir del ciclo euleriano anterior, descartando los nodos visitados (shortcutting).

Demostración

El coste de la solución obtenida por el algoritmo es 3/2 de la solución óptima.

La prueba es la siguiente:³

Sea A el conjunto de aristas de la solución óptima del TSP para G. Como (V,A) es conexo, contendrá varios árboles recubridores T, y por tanto, w(A) ≥ w(T). Además, sea B el conjunto de aristas de la solución óptima del TSP para el grafo completo sobre los vértices de O. Como los pesos asociados a las aristas son "triangulares" (visitar más nodos no reduce, en ningún caso, el coste total), se tiene que w(A) ≥ w(B). Se demuestra así que existe un apareamiento perfecto de vértices de O con peso tal que w(B)/2 ≤ w(A)/2, de forma que este límite constituye una cota superior para M (ya que M es un apareamiento perfecto de mínimo coste).

Debido a que O debe contener un número par de vértices, existe apareamiento perfecto. Sea e₁, ..., e_2k el (único) camino euleriano en (O,B). Es evidente que tanto e₁,e₃, ...,e_2k-1 como e₂, e₄, ..., e_2k son apareamientos perfectos, y que el peso de (al menos) uno de ellos es menor o igual que w(B)/2. Así, se tiene que w(M)+w(T) ≤ w(A) + w(A)/2, y de la desigualdad triangular se deduce que el algoritmo se aproxima en 3/2 al óptimo.