Gráficos en Java - Algoritmo A*

En este artículo, profundizamos en la teoría y la implementación de A* en Java con explicaciones detalladas y ejemplos prácticos.

Introducción

A* es un algoritmo gráfico de búsqueda de ruta heurística. Esto significa que dado un gráfico ponderado, genera el camino más corto entre dos nodos dados.

Se garantiza que el algoritmo terminará para gráficos finitos con pesos de borde no negativos. Además, si logra garantizar ciertas propiedades al diseñar su heurística, también siempre devolverá una solución casi óptima de una manera bastante eficiente.

Una heurística es un método construido para guiarnos a la solución óptima la mayor parte del tiempo, lo que significa que cambiamos cierta precisión por mucha velocidad (si la heurística está bien construida).

a star in java

En este artículo, repasaremos:

  • Algunas características que pretendemos tener en nuestros algoritmos de búsqueda heurística en general.
  • Mostrar una progresión lógica desde una búsqueda codiciosa hasta A*.
  • Pasar por las condiciones antes mencionadas que permitan a A* resolver nuestro problema de manera óptima y eficiente.

Características de búsqueda de gráficos

Comenzaremos describiendo algunas cosas que tendemos a querer lograr con nuestro algoritmo.

Las siguientes son métricas muy importantes que separan a A* de otros algoritmos similares y, por lo tanto, deben entenderse a fondo si queremos aplicarlas de manera significativa en la práctica:

  1. Completitud: es una propiedad de un algoritmo que garantiza que un algoritmo terminará con una solución si existe una solución.
  2. Optimalidad: es una propiedad que garantiza que la solución de nuestro algoritmo será la mejor solución disponible según los criterios que establecemos como objetivo.
  3. Complejidad de tiempo y memoria: mide la eficiencia del uso de recursos de nuestro algoritmo y, por lo tanto, su aplicabilidad práctica.

Deficiencias de otros algoritmos

Cuando nos enfrentamos al problema de encontrar el camino más corto en un gráfico en una cantidad de tiempo razonable, muchos de nosotros estaríamos tentados a sacrificar la optimidad e ir a por la solución codiciosa, siempre eligiendo el borde con el peso más bajo, yendo a lo largo de la corriente con la menor resistencia.

Un lector observador podría notar que al hacer eso, también hemos sacrificado la integridad: la búsqueda codiciosa a veces puede quedar atrapada en bucles infinitos. Podemos hacerlo mejor que eso.

Si has pensado en Algoritmo de Dijkstra, ¡puntos para ti! Ese es un gran algoritmo para encontrar el camino más corto y también es bastante eficiente. Hace el trabajo incluso para cálculos a gran escala, como el enrutamiento en la totalidad de Internet. También es completo y óptimo.

Así que el trabajo está hecho, ¿verdad?

No tan rápido.

Si bien Dijkstra puede ser la mejor solución posible para algunos problemas del mundo real, puede dedicar mucho tiempo a verificar rutas alternativas, especialmente en un gráfico denso con muchos nodos. De hecho, Dijkstra evalúa cada nodo en el gráfico. Incluso los que están detrás, alejándose de la portería. Si el objetivo estuviera justo en frente del nodo actual, todavía evaluaría los nodos en el lado opuesto del gráfico, aunque solo podría evaluar los nodos intermedios entre él y el objetivo.

Es como echar un vistazo al mapa completo de la ciudad en cada paso que das hacia una cafetería, en lugar de dirigir tu búsqueda en la dirección general de la tienda.

Si de alguna manera pudiéramos guiar la dirección general en la que va, hacia el nodo de destino, podríamos saltarnos mucho trabajo innecesario.

Digamos que podemos adivinar aproximadamente la distancia entre dos nodos. Tal vez estemos tratando de calcular una ruta de viaje por carretera entre dos puntos de la Tierra. Podríamos decir que la distancia recorrida en avión en línea recta es una estimación aproximada de la distancia que los separa. ¿Qué pasa si usamos esta estimación para elegir el siguiente nodo en lugar de usar el peso del borde?

Ese enfoque se llama búsqueda de lo mejor primero y, a menudo, aumentará nuestra eficiencia, pero a menudo terminaremos con una solución subóptima.

Eso nos lleva a cómo A* logra resolver todos estos problemas.

Nota: Algunos se refieren a A* como la Dijkstra informada.

El algoritmo A* en Java

Condiciones iniciales:

  • Tenemos un nodo inicial (llamado start) y un nodo objetivo (llamado target).
  • Tenemos un gráfico dirigido ponderado de n nodos.

La meta:

  • Encuentre la ruta más corta desde start hasta finish

Función de Costo - f(n)

Queremos determinar a qué nodo moverse en cada paso. Para hacer eso, diseñaremos una función matemática f(n) que medirá qué tan bueno es un nodo como candidato para ser incluido en nuestro camino más corto.

Esta es la función de costo, y queremos minimizarla para producir un resultado óptimo.

La función de costo es la suma de una función de movimiento y una función heurística.

Función de movimiento - g(n)

Debido a que estamos en el nodo n, sabemos el costo que nos costó llegar allí desde el nodo start. Llamaremos a esa función de movimiento - g(n).

Si decimos que f(n)=g(n) crearemos el algoritmo de Dijkstra. En cada paso, estaríamos eligiendo el nodo con el costo más bajo para llegar desde start - el nodo con el valor más pequeño para g(n). Esto significa que a nuestra función le falta un "componente guía", por así decirlo.

Función heurística - h(n)

Llamaremos a este componente guía una heurística y lo etiquetaremos como h(n). Usaremos este componente para estimar qué tan cerca está el nodo que estamos viendo del objetivo.

Esta estimación es el corazón y el alma de A* y hará o romperá cualquier implementación particular de la misma, pero teóricamente hablando, puede usar cualquier función que desee. Si supiéramos la distancia exacta en términos de nodos, ya tendríamos la solución óptima.

Sin embargo, si conocemos la posición del nodo de destino, podemos, por ejemplo, calcular la distancia euclidiana entre el nodo de destino y nuestro nodo actual. Cuanto más corto es, más cerca estamos del nodo de destino, aproximadamente.

Nota: Obtendrá mejores resultados si elabora cuidadosamente su heurística.

Cálculo de A* Moves

Entonces, la fórmula final que obtenemos es f(n)=g(n)+h(n). Comenzamos desde el nodo start, lo agregamos a una lista de nodos abiertos. Evaluamos todos los vecinos de los nodos abiertos y los agregamos a la lista de nodos abiertos. Elegimos el que tiene el valor más bajo para f(n) y si no es el objetivo repetimos el proceso.

Cuantos menos pasos demos desde el punto de partida, combinados con lo cerca que estemos de la meta, el valor de f(n) será más bajo si vamos por el camino más corto hacia la meta. Alejarse de la meta y dar más pasos de los necesarios para llegar allí aumenta la función f(n).

Si estás un poco confundido con la diferencia entre g(n) y h(n), míralo así:

  • g es algo que podemos (y hacemos) calcular en cualquier paso dado, y es la distancia entre start y n.
  • h es algo que no sabemos, y necesitamos estimar - la distancia desde n hasta el nodo objetivo.
  • f es la suma de los dos

a star cost function

A* Pseudocódigo

Mantenemos dos listas de nodos, una lista abierta y una lista cerrada.

La lista abierta contiene nodos que hemos encontrado, pero que aún no hemos analizado. Inicialmente, solo contiene el nodo de inicio.

La lista cerrada contiene nodos cuyos vecinos se han agregado a la lista abierta. Los nodos cerrados tienen su ruta más corta calculada y sus nodos adyacentes "programados" para el análisis al agregarlos a la lista abierta.

Los nodos cerrados pueden volver a abrirse si los encontramos a través de un camino diferente y ese camino es más óptimo que el que usamos anteriormente para llegar a ellos.

Pasamos por nodos abiertos, abrimos sus vecinos, calculamos sus f y g y luego los cerramos de nuevo.

Por lo general, necesitará calcular h una vez, la primera vez que encuentre un nodo. No tienes que volver a calcularlo varias veces porque está arreglado. Hemos omitido eso en este código, suponiendo que la heurística se calcule de antemano, pero puede agregarla según su aplicación:

make an empty list C of closed nodes
make a list O of open nodes and their respective f values containing the start node
while O isn't empty:
    pick a node n from O with the best value for f
    if n is target:
        return solution
    for every m which is a neighbor of n:
        if (m is not in C) and (m is not in O):
            add m to O, set n as m's parent
            calculate g(m) and f(m) and save them
        else:
            if f(m) from last iteration is better than g(m) from this iteration:
                set n as m's parent
                update g(m) and f(m)
                if m is in C:
                    move m to O
    move n from O to C

return that there's no solution

A* Implementación en Java

Implementaremos un algoritmo para el gráfico que se muestra al principio del artículo. Nuestra heurística tratará cada "capa" como un paso hacia el nodo objetivo. Los números dentro de los nodos son sus ID, que usaremos para imprimir la ruta resultante:

a star implementation in java

Nota: Esta no es una buena heurística en la práctica.

Cada problema tendrá su propia heurística de ajuste, porque un gráfico se puede dibujar de muchas maneras: los nodos pueden aparecer más cerca o más lejos del objetivo de lo que realmente están cuando se considera el peso de los bordes.

Hemos optado por este enfoque con fines ilustrativos y, en la siguiente sección, profundizaremos en cómo hacer una heurística útil en la práctica.

Hagamos una clase Nodo para representar un nodo en nuestro gráfico:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Node implements Comparable<Node> {
      // Id for readability of result purposes
      private static int idCounter = 0;
      public int id;

      // Parent in the path
      public Node parent = null;

      public List<Edge> neighbors;

      // Evaluation functions
      public double f = Double.MAX_VALUE;
      public double g = Double.MAX_VALUE;
      // Hardcoded heuristic
      public double h; 

      Node(double h){
            this.h = h;
            this.id = idCounter++;
            this.neighbors = new ArrayList<>();
      }

      @Override
      public int compareTo(Node n) {
            return Double.compare(this.f, n.f);
      }

      public static class Edge {
            Edge(int weight, Node node){
                  this.weight = weight;
                  this.node = node;
            }

            public int weight;
            public Node node;
      }

      public void addBranch(int weight, Node node){
            Edge newEdge = new Edge(weight, node);
            neighbors.add(newEdge);
      }

      public double calculateHeuristic(Node target){
            return this.h;
      }
}

Y aquí está el algoritmo en sí:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public static Node aStar(Node start, Node target){
    PriorityQueue<Node> closedList = new PriorityQueue<>();
    PriorityQueue<Node> openList = new PriorityQueue<>();

    start.f = start.g + start.calculateHeuristic(target);
    openList.add(start);

    while(!openList.isEmpty()){
        Node n = openList.peek();
        if(n == target){
            return n;
        }

        for(Node.Edge edge : n.neighbors){
            Node m = edge.node;
            double totalWeight = n.g + edge.weight;

            if(!openList.contains(m) && !closedList.contains(m)){
                m.parent = n;
                m.g = totalWeight;
                m.f = m.g + m.calculateHeuristic(target);
                openList.add(m);
            } else {
                if(totalWeight < m.g){
                    m.parent = n;
                    m.g = totalWeight;
                    m.f = m.g + m.calculateHeuristic(target);

                    if(closedList.contains(m)){
                        closedList.remove(m);
                        openList.add(m);
                    }
                }
            }
        }

        openList.remove(n);
        closedList.add(n);
    }
    return null;
}

public static void printPath(Node target){
    Node n = target;

    if(n==null)
        return;

    List<Integer> ids = new ArrayList<>();

    while(n.parent != null){
        ids.add(n.id);
        n = n.parent;
    }
    ids.add(n.id);
    Collections.reverse(ids);

    for(int id : ids){
        System.out.print(id + " ");
    }
    System.out.println("");
}

Y ahora, construyamos un gráfico y llamemos a este método:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void main(String[] args) {
    Node head = new Node(3);
    head.g = 0;

    Node n1 = new Node(2);
    Node n2 = new Node(2);
    Node n3 = new Node(2);

    head.addBranch(1, n1);
    head.addBranch(5, n2);
    head.addBranch(2, n3);
    n3.addBranch(1, n2);

    Node n4 = new Node(1);
    Node n5 = new Node(1);
    Node target = new Node(0);

    n1.addBranch(7, n4);
    n2.addBranch(4, n5);
    n3.addBranch(6, n4);

    n4.addBranch(3, target);
    n5.addBranch(1, n4);
    n5.addBranch(3, target);

    Node res = aStar(head, target);
    printPath(res);
}

Cuando ejecutemos esto, obtendremos el resultado impreso:

1
0 3 2 5 6

a star in java result

Crear una buena función heurística

Admisibilidad y consistencia

El rendimiento de A* depende del uso de una buena heurística. El propio algoritmo puede tener algunas propiedades muy útiles si nos aseguramos de que la heurística siga ciertas reglas. Vamos a ver.

La función h(n) es admisible si nunca sobreestima la distancia real entre el nodo actual y el objetivo. Lo que significa que la siguiente desigualdad es cierta para cada nodo n:

$$
h(n)\leq h\ ⃰(n)
$$

Donde h ⃰ es la heurística ideal, que mide con precisión el camino más corto.

Si h es admisible, A* siempre devolverá la ruta óptima.

Si h no es admisible, pero no sobrestima la distancia real en más de algún valor d, entonces la longitud de la ruta encontrada por A* no diferirá de la ruta óptima en más de d.

La función h(n) es consistente si se evalúa como 0 para el nodo de destino y si por cada dos nodos vecinos es cierto que:

$$
c(n,m)+h(m)\geq h(n)
$$

Donde c(n,m) es el peso de la arista (n,m).

Teorema: Si una función heurística es consistente, entonces también es admisible.

The prueba of this theorem is done by complete induction.

Complejidad

Salvo casos especiales, la complejidad de A* se puede aproximar en base al número de vecinos de cada nodo y la longitud de el camino más corto. Digamos que cada nodo tiene como máximo b vecinos y el camino más corto es de distancia d. La complejidad de A* es entonces:

$$
O(b^d)
$$

La complejidad exponencial no sería mejor que la fuerza bruta, por lo que esto puede parecer malo. La cuestión es que podemos reducir esto a una complejidad polinomial si nuestra heurística satisface la siguiente ecuación:

$$
|h(x)-h\ ⃰(x)| \leq O(\log h\ ⃰(x))
$$

A* también es óptimamente eficiente, lo que significa que se ha demostrado que ningún algoritmo completo es más eficiente que A* para resolver el mismo problema.

Ejemplo: terreno 2D con obstáculos

Digamos que tenemos una cuadrícula 2D con obstáculos. Cada cuadrado corresponde a un nodo y podemos movernos como un rey en el ajedrez: un cuadrado horizontal, vertical o diagonalmente. Queremos encontrar el camino más corto desde el principio hasta el objetivo.

2d terrain with obstacles a star java

Representación

En este caso, podemos representar nuestro gráfico como una matriz de nodos, en lugar de usar listas de adyacencia. Cada nodo puede tener un indicador de si es transitable o un obstáculo. Podemos usar índices de matriz para averiguar nodos adyacentes, así como usarlos como si fueran coordenadas al calcular nuestras distancias heurísticas.

Heurística

Tu primer pensamiento podría ser usar la distancia euclidiana. Sin embargo, en problemas grandes, esto debe evitarse ya que calcular la raíz cuadrada a menudo puede causar ineficiencia. Es una buena métrica si nada más se ajusta al problema, pero si puede salirse con la suya usando una distancia simplificada, debe intentarlo.

Una segunda idea podría ser la distancia de Manhattan (también llamada distancia de taxi o distancia de manzana). Distancia Manhattan la suma de las diferencias horizontales y verticales:

$$
D_{Manhattan}(p,q)=|q_x-p_x|+|q_y-p_y|
$$

Sin embargo, esta métrica no es admisible porque muchas veces sobreestima la distancia. Imagine una cuadrícula sin obstáculos y el inicio y el objetivo colocados en diagonal. Manhattan siempre sobreestimaría este caso.

Una buena opción, en este caso, es la llamada distancia de Chebyshev:

$$
D_{Chebyshev}(p,q)=máx(|q_x-p_x|,|q_y-p_y|)
$$

Esta métrica es admisible y por lo tanto garantiza una solución óptima. También es rápido de calcular, por lo que no ejerce presión sobre los recursos en cada iteración.

Conclusión

Hemos echado un vistazo al algoritmo de búsqueda A* y sus propiedades. Hemos aprendido cómo funciona y por qué es muy bueno en la práctica, siempre que podamos garantizar ciertas propiedades de una heurística que lo guíe.

Aplicar esto a problemas reales requiere práctica y experiencia, pero este artículo debería haberle dado al lector una buena base para comenzar.