🌸 1.8.2 ALGORITMO A*

 

   Fundamento teórico

El algoritmo A* (A estrella) es un algoritmo de búsqueda heurística utilizado para encontrar la ruta más corta o la solución óptima entre un punto inicial y un objetivo final.

Es ampliamente utilizado en Artificial Intelligence, robótica, videojuegos, navegación y sistemas de optimización, debido a su capacidad para encontrar soluciones eficientes combinando costo real y estimación heurística.

Su principal característica es que evalúa diferentes rutas y selecciona la más prometedora para llegar al objetivo

1. Teoría de búsqueda en grafos

El algoritmo A* trabaja sobre una estructura llamada grafo, formada por:

• Nodos: representan estados o ubicaciones
• Aristas: representan conexiones entre nodos
• Costo: valor asociado al desplazamiento entre nodos

👉 El objetivo es encontrar el camino óptimo entre dos nodos.

2. Búsqueda heurística

A* utiliza una función heurística para estimar qué tan cerca está un nodo de la meta.

Esto le permite:

• Priorizar rutas prometedoras
• Reducir exploraciones innecesarias
• Mejorar eficiencia

👉 Usa inteligencia predictiva para optimizar la búsqueda.

3. Función de evaluación

El algoritmo utiliza la fórmula:

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

Donde:

• f(n): costo total estimado
• g(n): costo real desde el inicio hasta el nodo actual
• h(n): estimación del costo restante hasta la meta

👉 Selecciona el nodo con menor costo total estimado.

4. Optimalidad y completitud

Según los estudios de Peter Hart, Nils Nilsson y Bertram Raphael, A* garantiza encontrar la mejor solución si la heurística es admisible.

Una heurística es admisible cuando nunca sobreestima el costo real.

👉 Esto asegura precisión.

Funcionamiento básico

El algoritmo sigue estos pasos:

1. Inicia en el nodo inicial
2. Evalúa nodos vecinos
3. Calcula su costo
4. Selecciona el nodo con menor valor
5. Repite hasta llegar al objetivo

 Componentes principales

Lista abierta

Contiene nodos pendientes por explorar.

Lista cerrada

Contiene nodos ya evaluados.

Función heurística

Estima la distancia restante.

 Ventajas

• Encuentra rutas óptimas
• Reduce tiempo de búsqueda
• Es eficiente
• Muy usado en navegación inteligente

Desventajas

• Consume memoria en problemas grandes
• Depende de una buena heurística
• Puede volverse costoso en espacios extensos

 Aplicaciones

• Sistemas GPS
• Videojuegos
• Robots autónomos
• Planeación logística
• Redes de transporte

Video explicativo:

Practica: 

Actividad: Ruta más corta en una cuadrícula

Procedimiento:

1. Dibujar una cuadrícula 5x5
2. Definir inicio y meta
3. Colocar obstáculos
4. Aplicar A*

Calcular:

• Distancia recorrida
• Distancia estimada
• Valor total

  📄 Ver práctica en PDF

Evaluacion:

¿Qué significa A*?

¿Qué representa g(n)?

¿Qué representa h(n)?

¿Para qué se utiliza?

¿Por qué es eficiente?

Conclusion:

El algoritmo A* es un método de búsqueda heurística que combina costo real y estimación futura para encontrar la mejor ruta posible, siendo una herramienta fundamental en inteligencia artificial y optimización.

Referencias APA 7

• Peter Hart, P. E., Nils Nilsson, N. J., & Bertram Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
• Stuart Russell, S., & Peter Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson.
• Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley.
• Nils Nilsson. (1998). Artificial intelligence: A new synthesis. Morgan Kaufmann.