1.8.2 Algoritmo A*

Introducción

¿Cómo podemos encontrar el camino más corto entre dos puntos de un mapa?

Presentar el problema de búsqueda del camino más corto:

La imagen 2 El problema del viajero, también conocido como el problema del viajante de comercio, plantea el desafío de encontrar la ruta más eficiente para que un viajero visite todas las ciudades en un mapa, regresando al punto de partida, minimizando el costo total del viaje. Por ejemplo, comenzando en Atlanta, el viajero debe planificar su ruta para visitar ciudades como Boston, Chicago, Denver y así sucesivamente, considerando los costos asociados a cada movimiento entre ciudades.

Figura 2

Problema del viajero:

Este problema ilustra la importancia de contar con algoritmos eficientes para su resolución. Aquí es donde entra en juego el algoritmo A*, una poderosa herramienta en el campo de la inteligencia artificial. El algoritmo A* se define como un método de búsqueda heurística diseñado para encontrar la ruta más corta entre dos puntos en un espacio de búsqueda. Lo que lo hace particularmente efectivo es su capacidad para combinar la búsqueda en anchura con una función de evaluación heurística. Es una herramienta poderosa que se aplica en diversos campos como la robótica, la inteligencia artificial, la planificación de rutas y los videojuegos.

En términos simples, el algoritmo A* utiliza información heurística para estimar qué tan prometedores son los nodos en el espacio de búsqueda, lo que le permite priorizar la exploración de aquellos que tienen más probabilidades de conducir a la solución óptima. Esta combinación de búsqueda exhaustiva y heurística lo convierte en una herramienta poderosa para resolver problemas como el del viajero de comercio de manera eficiente y efectiva.

Algoritmo A*

Principales Conceptos de Funcionamiento

A* funciona evaluando dos valores para cada nodo del espacio de búsqueda:

g(n):

Utilizan reglas más simples y se aplican a problemas bien definidos y menos complejos.

h(n):

La distancia estimada desde el nodo actual hasta el nodo final. Esta distancia se calcula utilizando una función heurística.

El algoritmo A* elige el siguiente nodo a explorar en función de la función de evaluación.

				
					f(n) = g(n) + h(n).

Ejemplo Aplicado

Imagina que queremos encontrar el camino más corto entre dos ciudades en un mapa. El espacio de búsqueda está formado por todas las ciudades y las carreteras que las conectan.

Ejemplo:

g(n):

Utilizan reglas más simples y se aplican a problemas bien definidos y menos complejos.

h(n):

La distancia estimada desde el nodo actual hasta el nodo final. Esta distancia se calcula utilizando una función heurística.

Proceso:

g(n):

Utilizan reglas más simples y se aplican a problemas bien definidos y menos complejos.

h(n):

La distancia estimada desde el nodo actual hasta el nodo final. Esta distancia se calcula utilizando una función heurística.

Desglose del Algoritmo A*

Entradas:

Salida:

1. Inicializar:

2. Mientras Cola no este vació.

				
					f(n) = g(n) + h(n).

4. No se ha encontrado el camino.

5. Fin.

Práctica 1

Implementación del algoritmo A* en Lenguaje Python para el juego Pacman de la universidad de Berkeley: http://ai.berkeley.edu/search.html

Objetivos, saberes y habilidades por desarrollar

Materiales:

Código fuente del juego Pacman de la Universidad de Berkeley (disponible en línea: http://ai.berkeley.edu/search.html).

Duración: 4 sesiones de 1 hora.

Introducción:

El algoritmo A* es un algoritmo de búsqueda que se utiliza para encontrar la ruta mas corta entre dos puntos, por ello se puede utilizar para la resolución de problemas en diferentes áreas como las rutas en mapas, planeación de rutas para robots,y búsqueda de soluciones en videojuegos. Por tal motivo en esta práctica veras como el algoritmo A* ayuda a Pacman a encontrar la ruta mas corta para comerse los puntitos, de tal forma que pondrás en práctica tus conocimientos del algoritmo, así como también tus conocimientos en programación.

Como hemos visto, el algoritmo considera un estado inicial, el cual debes considerar dependiendo el mapa que Pacman vaya a resolver. Dicho estado es el punto inicial dentro del plano cartesiano, en el siguiente apartado te explico como puedes obtener ese dato con una simple instrucción. De igual forma, considerarás que que hay una meta final, dicha meta es comerse todos los puntitos del mapa. He agregado video para facilitarte la comprensión del código y de las tareas que vas a realizar.

Metodología y guía para el profesor:

Específicamente los archivos Search.py y util.py

1. Implementación del algoritmo A*:

Guía a los estudiantes para que programen la función A* en Python dentro del código del juego Pacman.
Explica los pasos necesarios para adaptar el algoritmo A* al entorno del juego, incluyendo la definición de nodos, el uso de la función de evaluación y la actualización de la cola y la lista de Explorados.
Resuelve dudas y ofrece asistencia técnica durante el proceso de codificación. Pruebas y depuración:

2. Pruebas y depuración:

Entregables:

Entregarás el proceso funcionando y en base al código realizado, realiza un reporte que contenga bastos comentarios de cada elemento utilizado en la codificación. Y haz comentarios en caso de haber usado otras funciones que no hubieran funcionado adecuadamente o de alguna que crees que pudiera funcionar mejor.

Entregar el proceso completamente funcional, asegurándote de que cumpla con los objetivos establecidos.
Explica cada elemento utilizado en la codificación, indicando su propósito y funcionamiento.
Menciona las funciones que no hayan funcionado adecuadamente e incluye una explicación del problema.
Sugiere funciones alternativas que podrían haber funcionado mejor, con una breve justificación.

Se calificará base a la Rúbrica de Evaluación en el apartado de Recursos.

Esta actividad proporciona a los estudiantes la oportunidad de aplicar sus conocimientos en programación y algoritmos en un contexto práctico y divertido, al tiempo que fortalece su comprensión del algoritmo A* y su funcionamiento en la resolución de problemas de búsqueda de ruta.