Uso de la búsqueda A* en Python

Uso de la búsqueda A en Python*

La búsqueda A* es un algoritmo de búsqueda heurística que se utiliza para encontrar el camino más corto entre dos puntos en un mapa. Es un algoritmo eficiente y eficaz, y se utiliza en una amplia gama de aplicaciones, como la planificación de rutas, la robótica y los juegos.

En este tutorial, veremos cómo implementar la búsqueda A* en Python. Comenzaremos con una descripción general del algoritmo, y luego veremos cómo implementarlo paso a paso. Finalmente, veremos un ejemplo de cómo utilizar la búsqueda A* para encontrar el camino más corto entre dos puntos en un mapa.

Introducción a la búsqueda A*

La búsqueda A* es un algoritmo de búsqueda heurística. Esto significa que utiliza una función heurística para estimar la distancia entre el nodo actual y el objetivo. La función heurística debe ser admisible, lo que significa que nunca debe sobreestimar la distancia real.

El algoritmo A* funciona de la siguiente manera:

1. Comienza en el nodo inicial.
2. Calcula la distancia estimada entre el nodo actual y el objetivo.
3. Agrega el nodo actual a una lista de nodos abiertos.
4. Mientras la lista de nodos abiertos no esté vacía:
   • Elige el nodo con la distancia estimada más baja.
   • Si el nodo actual es el objetivo, termina el algoritmo.
   • Expande el nodo actual, agregando sus vecinos a la lista de nodos abiertos.
   • Actualiza las distancias estimadas de los vecinos.

Implementación de la búsqueda A en Python*

Para implementar la búsqueda A* en Python, necesitamos definir las siguientes clases:

• Nodo: Representa un nodo en el mapa.
• Lista de abiertos: Representa una lista de nodos que aún no se han explorado.
• Lista de cerrados: Representa una lista de nodos que ya se han explorado.

Nodo

class Nodo:
    def __init__(self, x, y, costo, padre):
        self.x = x
        self.y = y
        self.costo = costo
        self.padre = padre

Lista de abiertos

class ListaAbiertos:
    def __init__(self):
        self.nodos = []

    def agregar(self, nodo):
        self.nodos.append(nodo)

    def remover(self, nodo):
        self.nodos.remove(nodo)

    def obtener_nodo_mas_cercano(self):
        return self.nodos[0]

Lista de cerrados

class ListaCerrados:
    def __init__(self):
        self.nodos = []

    def agregar(self, nodo):
        self.nodos.append(nodo)

    def contiene(self, nodo):
        return nodo in self.nodos

Implementación del algoritmo

def busqueda_a_estrella(mapa, nodo_inicial, nodo_objetivo):
    lista_abiertos = ListaAbiertos()
    lista_cerrados = ListaCerrados()

    # Agrega el nodo inicial a la lista de abiertos

    lista_abiertos.agregar(nodo_inicial)

    while True:
        # Obtiene el nodo con la distancia estimada más baja

        nodo_actual = lista_abiertos.obtener_nodo_mas_cercano()

        # Si el nodo actual es el objetivo, termina el algoritmo

        if nodo_actual == nodo_objetivo:
            return nodo_actual.padre

        # Expande el nodo actual

        for nodo_vecino in mapa.obtener_vecinos(nodo_actual):
            # Calcula la distancia estimada hasta el nodo objetivo

            costo_estimado = nodo_actual.costo + nodo_vecino.costo

            # Si el nodo vecino no está en la lista de cerrados

            if not lista_cerrados.contiene(nodo_vecino):
                # Agrega el nodo vecino a la lista de abiertos

                lista_abiertos.agregar(nodo_vecino)

                # Actualiza la distancia estimada del nodo vecino

                nodo_vecino.costo = costo_estimado