30. Mejorando el algoritmo A(estrella)

1. Control de Recursos mediante Cotas

El desempeño de A* depende directamente de la calidad de la heurística. Una heurística débil provoca un crecimiento exponencial en el consumo de memoria y tiempo. Para mitigar esto, se proponen dos tipos de límites:

• Cota de Costo (A acotado):* A diferencia de los algoritmos de búsqueda ciega que usan profundidad, en búsqueda informada se utiliza una cota de costo $f$ (donde $f = g + h$).

• Funcionamiento: Cualquier nodo cuyo costo estimado sea mayor que la cota establecida es ignorado y no se agrega a la agenda.

• Impacto en la memoria: El ahorro máximo de memoria se logra cuando la cota es exactamente igual a la profundidad de la meta. Sin embargo, si la cota es menor a la profundidad real, el algoritmo se vuelve incompleto (no encuentra la solución).

---

2. Manejo de Heurísticas No Monotónicas y No Admisibles

Cuando una heurística es "ruidosa" (sobreestima el costo o no cumple la desigualdad del triángulo), el algoritmo A* estándar puede fallar en encontrar la ruta óptima o procesar nodos de forma ineficiente. Para esto, se proponen cambios estructurales:

Uso de Tablas de Dispersión (Diccionarios)

En lugar de un conjunto simple de nodos expandidos, se utiliza una tabla de dispersión donde la llave es el estado y el valor es el costo acumulado ($g$).

• Re-expansión inteligente: Si un nodo ya fue expandido pero se encuentra nuevamente por una ruta con un costo menor, la entrada en el diccionario se actualiza y el nodo se vuelve a expandir. Esto garantiza que se sigan explorando mejoras potenciales.

El Algoritmo BBA Estrella (BBA*)

Este enfoque permite explotar heurísticas ruidosas para encontrar soluciones incluso si la primera encontrada es sub-óptima.

1. Búsqueda Continua: Al encontrar la primera solución (meta), el algoritmo no se detiene.

2. Cota Dinámica: El costo de la solución encontrada se convierte en la nueva cota de costo.

3. Refinamiento: El algoritmo continúa explorando los nodos restantes en la agenda. Si encuentra una nueva ruta a la meta con un costo menor a la cota actual, se actualiza la solución y se reduce la cota.

4. Finalización: El proceso termina cuando la agenda se vacía, garantizando que se devuelva la mejor ruta descubierta bajo esas condiciones.