El Escape Inteligente
Implementación del Algoritmo A* en Laberintos

En el campo de la Inteligencia Artificial y el desarrollo de videojuegos, la navegación eficiente de un punto a otro es un desafío fundamental. Los algoritmos de búsqueda ciega suelen ser ineficientes al explorar rutas innecesarias. Aquí es donde intervienen las heurísticas: estimaciones matemáticas que guían al algoritmo hacia la meta.
Esta práctica se centra en el algoritmo A*, el cual combina el costo real de llegar a un nodo con el costo estimado (heurística) para llegar al objetivo, logrando una búsqueda óptima y rápida.
Objetivo General
El estudiante logrará comprender y programar un algoritmo de búsqueda informada (A*) en un entorno de cuadrícula discreto, integrando una función heurística para optimizar la búsqueda del camino más corto entre un punto de inicio y una meta.
Materiales o Recursos Necesarios:
- Computadora con un entorno de desarrollo de Python (se recomienda Google Colab, Jupyter Notebook o VS Code).
- Intérprete de Python 3.8 o superior.
- Conocimientos básicos de estructuras de datos (listas, diccionarios, colas de prioridad).
Generación de Insumos Prácticos
El estudiante utilizará el siguiente código base, el cual contiene la estructura del laberinto (donde 0 es un camino libre y 1 es un obstáculo) y la clase Nodo. El objetivo del estudiante será completar la función heurística y la lógica principal del algoritmo.
Instrucciones Paso a Paso
- Analizar el entorno de trabajo: El estudiante debe examinar la matriz
laberinto, identificando las coordenadas de inicio(0, 0)y la meta(9, 9). Se debe comprender ¿cómo los unos (1) representan barreras intransitables? - Implementar la función heurística: El estudiante debe programar la función
calcular_heuristicautilizando la fórmula de la “Distancia Manhattan”: ∣x1−x2∣+∣y1−y2∣. Esta función orientará la búsqueda. - Inicializar las estructuras de control: Dentro de la función
busqueda_a_estrella, se debe instanciar el nodo inicial y crear una lista abierta (preferiblemente una cola de prioridad usandoheapq) y un conjunto o lista cerrada para los nodos ya visitados. - Desarrollar el ciclo de expansión: El estudiante debe programar un bucle
whileque extraiga el nodo con el menor valor defde la lista abierta. Si es la meta, se reconstruirá el camino hacia atrás utilizando el atributopadrede los nodos. - Generar los vecinos: Por cada nodo extraído, se deben generar sus posiciones adyacentes (arriba, abajo, izquierda,derecha). Se debe verificar que no sean paredes y calcular sus valores
g,hyfantes de añadirlos a la lista abierta si aportan un camino más barato. - Ejecutar y validar: El código debe ejecutarse para imprimir la lista de coordenadas (tuplas) que conforman el camino más corto encontrado.
Recomendaciones
- Leer detenidamente la estructura de la clase
Nodoantes de empezar a programar la lógica, entendiendo para qué sirve el atributopadre. - Recordar que las matrices en Python se indexan como
matriz[y][x], nomatriz[x][y]. Las posiciones son pares(fila, columna). - Imprimir el valor del nodo actual en cada iteración del bucle
while(de manera temporal) para depurar y visualizar cómo se expande la búsqueda en tiempo real. - Asegurarse de no añadir nodos a la lista abierta si ya se encuentran en la lista cerrada con un costo
fmenor, para evitar cálculos redundantes.
Posible Problema y Solución Rápida
- Problema: El programa entra en un ciclo infinito y eventualmente arroja un error de falta de memoria o límite de recursión, evaluando repetidamente los mismos cuadros vacíos.
- Solución Rápida: El problema se debe a que no se está utilizando correctamente una lista cerrada (
closed_list).El estudiante debe asegurar que la posición(x, y)del nodo actual se agregue al conjunto de visitados tan pronto como sea extraído de la lista abierta, e incluir una condiciónif vecino_posicion in visitados: continueantes de procesar cualquier vecino.