Gráficos en Python - Teoría e implementación - Algoritmo de búsqueda A*

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de modo...

¿Qué es A*?

Digamos que tienes que atravesar un enorme laberinto. Este laberinto es tan grande que llevaría horas encontrar el objetivo manualmente. Además, una vez que termines el laberinto "a pie", se supone que debes terminar otro.

Para hacer las cosas mucho más fáciles y que consuman menos tiempo, reduciremos el laberinto a un problema de búsqueda y encontraremos una solución que se puede aplicar a cualquier laberinto adicional que podamos encontrar, siempre que siga las mismas reglas. /estructura.

Siempre que queramos convertir cualquier tipo de problema en un problema de búsqueda, tenemos que definir seis cosas:

  1. Un conjunto de todos los estados en los que podríamos terminar
  2. El estado inicial y final
  3. Una verificación de finalización (una forma de verificar si estamos en el estado de finalización)
  4. Un conjunto de acciones posibles (en este caso, diferentes direcciones de movimiento)
  5. Una función transversal (una función que nos dirá dónde terminaremos si vamos en cierta dirección)
  6. Un conjunto de costos de movimiento de estado a estado (que corresponden a los bordes en el gráfico)

El problema del laberinto se puede resolver asignando las intersecciones a los nodos apropiados (puntos rojos) y las posibles direcciones en las que podemos ir a los bordes del gráfico apropiados (líneas azules).

Naturalmente, definimos los estados de inicio y finalización como las intersecciones donde ingresamos al laberinto (nodo A) y donde queremos salir del laberinto (nodo B).

Maze with state nodes

Ahora que tenemos un gráfico terminado, podemos discutir algoritmos para encontrar una ruta desde el estado A al estado B. En casos simples (como este), donde el gráfico generado consta de una pequeña cantidad de nodos y aristas, BFS, [DFS ]{rel=“https://wikihtp.com/profundidad-primera-busqueda-dfs-en-teoria-e-implementacion-de-python/" target="_blank”} y [Dijkstra](/algoritmo-de-dijkstras- en-python/) sería suficiente.

Sin embargo, en un escenario de la vida real, debido a que estamos lidiando con problemas de una enorme complejidad combinatoria, sabemos que tendremos que lidiar con una enorme cantidad de nodos y aristas. Por ejemplo, hay muchos estados en los que puede estar un cubo de Rubik, por lo que resolverlo es tan difícil. Por lo tanto, tenemos que usar un algoritmo que sea, en cierto sentido, guiado. Ahí es donde surge un algoritmo de búsqueda informado, A*.

Búsqueda informada significa que el algoritmo tiene información adicional, para empezar. Por ejemplo, un algoritmo de problema de búsqueda desinformado encontraría un camino desde casa al trabajo completamente ciego.

Por otro lado, un algoritmo de problema de búsqueda informado sería encontrar un camino desde casa al trabajo con la ayuda de su vista (ver qué camino lo acerca a su destino) o un mapa (saber exactamente qué tan lejos está cada punto). de su destino).

A* solo realiza un paso si parece prometedor y razonable, de acuerdo con sus funciones, a diferencia de otros algoritmos de recorrido de grafos. Corre hacia la meta y no considera ningún paso no óptimo si no tiene que considerarlos.

Esto hace que A* sea muy útil para los sistemas de inteligencia artificial, especialmente en el aprendizaje automático y el desarrollo de juegos, ya que estos sistemas replican escenarios del mundo real.

Conceptos básicos de A*

A* se basa en el uso de métodos heurísticos para lograr optimidad y completitud, y es una variante del algoritmo mejor primero.

Cuando un algoritmo de búsqueda tiene la propiedad de optimización, significa que está garantizado para encontrar la mejor solución posible, en nuestro caso, el camino más corto al estado final. Cuando un algoritmo de búsqueda tiene la propiedad de completitud, significa que si existe una solución a un problema dado, se garantiza que el algoritmo la encontrará.

Cada vez que A* ingresa a un estado, calcula el costo, f(n) (siendo n el nodo vecino), para viajar a todos los nodos vecinos, y luego ingresa al nodo con el valor más bajo de f( n).

Estos valores se calculan con la siguiente fórmula:

$$
\mathcal f(n) = \mathcal g(n) + \mathcal h(n)
$$

g(n) es el valor de la ruta más corta desde el nodo de inicio hasta el nodo n, y h(n) es una aproximación heurística del valor del nodo.

Para que podamos reconstruir cualquier camino, necesitamos marcar cada nodo con el relativo que tiene el valor f(n) óptimo. Esto también significa que si volvemos a visitar ciertos nodos, también tendremos que actualizar sus parientes más óptimos. Más sobre eso más adelante.

La eficiencia de A* depende en gran medida del valor heurístico h(n) y, dependiendo del tipo de problema, es posible que necesitemos usar una función heurística diferente para encontrar la solución óptima.

La construcción de tales funciones no es tarea fácil y es uno de los problemas fundamentales de la IA. Las dos propiedades fundamentales que puede tener una función heurística son admisibilidad y consistencia.

Admisibilidad y consistencia

Una función heurística h(n) dada es admisible si nunca sobreestima la distancia real entre n y el nodo objetivo.

Por lo tanto, para cada nodo n se aplica la siguiente fórmula:

$$
h(n)\leq h^*(n)
$$

h*(n) siendo la distancia real entre n y el nodo objetivo. Sin embargo, si la función sobreestima la distancia real, pero nunca por más de d, podemos decir con seguridad que la solución que produce la función tiene una precisión de d (es decir, no sobreestima el camino más corto desde el inicio terminar por más de d).

Una función heurística dada h(n) es consistente si la estimación es siempre menor o igual a la distancia estimada entre el objetivo n y cualquier vecino dado, más el costo estimado de llegar a ese vecino:

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

c(n,m) siendo la distancia entre los nodos n y m. Además, si h(n) es consistente, conocemos la ruta óptima a cualquier nodo que ya haya sido inspeccionado. Esto significa que esta función es óptima.

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

Prueba por inducción completa

El parámetro de inducción N será el número de nodos entre el nodo n y el nodo final s en el camino más corto entre los dos.

Base: N=0

Si no hay nodos entre n y s, y porque sabemos que h(n) es consistente, la siguiente ecuación es válida:

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

Conociendo h*(n)=c(n,s) y h(s)=0 podemos deducir con seguridad que:

$$
h^*(n)\geq h(n)
$$

Hipótesis de inducción: N < k

Suponemos que la regla dada es cierta para todo N < k.

Paso de inducción:

En el caso de nodos N = k en el camino más corto de n a s, inspeccionamos el primer sucesor (nodo m) del nodo final n. Como sabemos que hay un camino de m a n, y sabemos que este camino contiene nodos k-1, la siguiente ecuación es válida:

$$
ℎ^*(𝑛) = 𝑐(𝑛, 𝑚) + ℎ^*(𝑚) ≥ 𝑐(𝑛, 𝑚) + ℎ(𝑚) ≥ ℎ(𝑛)
$$

Q.E.D.

Implementación

Esta es una implementación directa de A* en una estructura gráfica. La función heurística se define como 1 para todos los nodos por razones de simplicidad y brevedad.

El gráfico se representa con una lista de adyacencia, donde las claves representan los nodos del gráfico y los valores contienen una lista de bordes con los nodos vecinos correspondientes.

Aquí encontrarás el algoritmo A* implementado en Python:

  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
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
from collections import deque

class Graph:
    # example of adjacency list (or rather map)
    # adjacency_list = {
    # 'A': [('B', 1), ('C', 3), ('D', 7)],
    # 'B': [('D', 5)],
    # 'C': [('D', 12)]
    # }

    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list[v]

    # heuristic function with equal values for all nodes
    def h(self, n):
        H = {
            'A': 1,
            'B': 1,
            'C': 1,
            'D': 1
        }

        return H[n]

    def a_star_algorithm(self, start_node, stop_node):
        # open_list is a list of nodes which have been visited, but who's neighbors
        # haven't all been inspected, starts off with the start node
        # closed_list is a list of nodes which have been visited
        # and who's neighbors have been inspected
        open_list = set([start_node])
        closed_list = set([])

        # g contains current distances from start_node to all other nodes
        # the default value (if it's not found in the map) is +infinity
        g = {}

        g[start_node] = 0

        # parents contains an adjacency map of all nodes
        parents = {}
        parents[start_node] = start_node

        while len(open_list) > 0:
            n = None

            # find a node with the lowest value of f() - evaluation function
            for v in open_list:
                if n == None or g[v] + self.h(v) < g[n] + self.h(n):
                    n = v;

            if n == None:
                print('Path does not exist!')
                return None

            # if the current node is the stop_node
            # then we begin reconstructin the path from it to the start_node
            if n == stop_node:
                reconst_path = []

                while parents[n] != n:
                    reconst_path.append(n)
                    n = parents[n]

                reconst_path.append(start_node)

                reconst_path.reverse()

                print('Path found: {}'.format(reconst_path))
                return reconst_path

            # for all neighbors of the current node do
            for (m, weight) in self.get_neighbors(n):
                # if the current node isn't in both open_list and closed_list
                # add it to open_list and note n as it's parent
                if m not in open_list and m not in closed_list:
                    open_list.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight

                # otherwise, check if it's quicker to first visit n, then m
                # and if it is, update parent data and g data
                # and if the node was in the closed_list, move it to open_list
                else:
                    if g[m] > g[n] + weight:
                        g[m] = g[n] + weight
                        parents[m] = n

                        if m in closed_list:
                            closed_list.remove(m)
                            open_list.add(m)

            # remove n from the open_list, and add it to closed_list
            # because all of his neighbors were inspected
            open_list.remove(n)
            closed_list.add(n)

        print('Path does not exist!')
        return None

Veamos un ejemplo con el siguiente gráfico ponderado:

Ejecutamos el código así:

1
2
3
4
5
6
7
adjacency_list = {
    'A': [('B', 1), ('C', 3), ('D', 7)],
    'B': [('D', 5)],
    'C': [('D', 12)]
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('A', 'D')

Y la salida se vería así:

1
2
Path found: ['A', 'B', 'D']
['A', 'B', 'D']

Por lo tanto, la ruta óptima de A a D, encontrada usando A*, es A->B->D.

Licensed under CC BY-NC-SA 4.0