Conceptos básicos de IA: A * Algoritmo de búsqueda

Introducción

La inteligencia artificial en su núcleo se esfuerza por resolver problemas de enorme complejidad combinatoria. Con el paso de los años, estos problemas se redujeron a problemas de búsqueda.
Un problema de búsqueda de ruta es un problema computacional en el que tiene que encontrar una ruta desde el punto A al punto B. En nuestro caso, mapearemos los problemas de búsqueda a los gráficos apropiados, donde los nodos representan todos los estados posibles en los que podemos terminar. y los bordes que representan todos los caminos posibles que tenemos a nuestra disposición.
Entonces la siguiente pregunta lógica sería:
¿Cómo convertimos un problema en un problema de búsqueda?

¿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 significativamente más fáciles y que requieran menos tiempo, reduciremos el laberinto a un problema de búsqueda y encontraremos una solución que se pueda aplicar a cualquier laberinto adicional con el que nos encontremos, siempre que siga las mismas reglas / estructura.
Cada vez que queremos 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 finalizado)
  4. Un conjunto de acciones posibles (en este caso, diferentes direcciones de movimiento).
  5. Una función de recorrido (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 mediante la asignación de las intersecciones a los nodos apropiados (puntos rojos), y las posibles direcciones que podemos ir a los bordes del gráfico apropiado (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).
Laberinto con nodos estatales
Ahora que tenemos un gráfico terminado, podemos analizar algoritmos para encontrar una ruta desde el estado A al estado B. En casos simples (como este), donde el gráfico generado consta de un pequeño número de nodos y bordes, BFS , DFS y Dijkstra sería suficiente.
Sin embargo, en un escenario de la vida real, debido a que estamos lidiando con problemas de enorme complejidad combinatoria, sabemos que tendremos que lidiar con una enorme cantidad de nodos y aristas. Por ejemplo, hay muchos estados en los que se puede encontrar un cubo de Rubik, por lo que resolverlo es tan difícil. Por lo tanto, tenemos que usar un algoritmo que, en cierto sentido, sea guiadoAhí es donde surge un algoritmo de búsqueda informado , A *.
La búsqueda informada significa que el algoritmo tiene información adicional, para empezar. Por ejemplo, un algoritmo de problema de búsqueda desinformado sería encontrar una ruta desde su casa para trabajar completamente ciego.
En el reverso, un algoritmo de búsqueda informada sería encontrar un camino desde casa para trabajar 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 gráfico. Corre hacia la meta y no considera pasos no óptimos si no tiene que considerarlos.
Esto hace que A * sea muy útil para sistemas artificialmente inteligentes, especialmente en el aprendizaje automático y el desarrollo de juegos, ya que estos sistemas replican escenarios del mundo real.
Si desea leer más sobre los algoritmos de cruce de gráficos , sus aplicaciones y diferencias, ¡los tenemos cubiertos!

Conceptos básicos de A *

A * se basa en el uso de métodos heurísticos para lograr la optimización y la integridad , y es una variante del mejor algoritmo primero.
Cuando un algoritmo de búsqueda tiene la propiedad de optimalidad, significa que está garantizado para encontrar la mejor solución posible, en nuestro caso, el camino más corto hacia el estado final. Cuando un algoritmo de búsqueda tiene la propiedad de estar completo, significa que si existe una solución a un problema dado, se garantiza que el algoritmo lo encontrará.
Cada vez que A * ingresa a un estado, calcula el costo, f(n)(n es 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:
F(norte)=sol(norte)+h(norte)
g(n)siendo el valor de la ruta más corta desde el nodo de inicio hasta el nodo n , y h(n)siendo una aproximación heurística del valor del nodo.
Para que podamos reconstruir cualquier ruta, necesitamos marcar cada nodo con el pariente que tenga el f(n)valor ó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, según el tipo de problema, es posible que debamos utilizar 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 la admisibilidad y la consistencia .

Admisibilidad y Consistencia

Una función heurística dada h(n)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(norte)h(norte)
h*(n)siendo la distancia real entre n y el nodo objetivo. Sin embargo, si la función sobreestima la distancia real, pero nunca más de d , podemos decir con seguridad que la solución que produce la función es de precisión d (es decir, no sobrestima el camino más corto de principio a fin por más de d).
Una función heurística dada h(n)es consistente si la estimación siempre es menor o igual a la distancia estimada entre la meta ny cualquier vecino dado, más el costo estimado de alcanzar a ese vecino:
do(norte,metro)+h(metro)h(norte)
c(n,m)siendo la distancia entre nodos nmAdemás, si h(n)es consistente, entonces conocemos la ruta óptima para 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 Nserá el número de nodos entre el nodo ny el nodo final sen la ruta más corta entre los dos.
Base : N = 0
Si no hay nodos entre ns, y como sabemos que h(n)es consistente, la siguiente ecuación es válida:
do(norte,s)+h(s)h(norte)
Sabiendo h*(n)=c(n,s)y con h(s)=0seguridad podemos deducir que:
h(norte)h(norte)
Hipótesis de inducción : N <k
Nuestra hipótesis es que la regla dada es cierta para todos N < k.
Paso de inducción:
En el caso de N = klos nodos de la ruta más corta desde nque s, inspeccionamos el primer sucesor (nodo m) del nodo final nComo sabemos que hay una ruta de acceso mn, y sabemos que esta ruta contiene k-1nodos, la siguiente ecuación es válida:
(𝑛)=𝑐(𝑛,𝑚)+(𝑚)𝑐(𝑛,𝑚)+(𝑚)(𝑛)
QED

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 en aras de la simplicidad y la brevedad.
El gráfico se representa con una lista de adyacencia, donde las claves representan 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:
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:
Laberinto ejemplo 2
Ejecutamos el código como tal:
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 como:
Path found: ['A', 'B', 'D']  
['A', 'B', 'D']
Por lo tanto, la ruta óptima de AD, que se encuentra utilizando A *, es A-> B-> D.

Conclusión

A * es un algoritmo muy poderoso con un potencial casi ilimitado. Sin embargo, es tan buena como su función heurística, que puede ser muy variable teniendo en cuenta la naturaleza de un problema.
Ha encontrado aplicaciones en muchos sistemas de software, desde Machine Learning y Search Optimization hasta el desarrollo de juegos donde los personajes de los NPC navegan a través del terreno complejo y los obstáculos para llegar al jugador.

Acerca de: Programator

Somos Instinto Programador

0 comentarios:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Con tecnología de Blogger.