27. Algoritmo de búsqueda informada
Un algoritmo de búsqueda informada es un tipo de algoritmo que, además de explorar estados posibles para resolver un problema, usa información extra (heurísticas) para decidir qué camino es más prometedor y así llegar a la solución más rápido y de forma más eficiente.
¿Qué es una heurística?
Una heurística es una función que:
- No garantiza exactitud
- Pero orienta la búsqueda
- Reduce tiempo y espacio de exploración
"Las heurísticas son criterios, métodos, o principios para decidir cuál entre mútiples alternativas de lineas de acción promete ser la más efectiva para alcanzar una meta. Representan un balance entre dos requerimientos: la necesidad de hacer los criterios simples y, al mismo tiempo, el deseo de que discriminen correctamente entre elecciones buenas y malas."
Algoritmo A*
El algoritmo A es una técnica utilizada para encontrar la ruta más corta en un grafo, que es una estructura compuesta por nodos y conexiones entre ellos. Este algoritmo fue desarrollado en 1968 y se ha convertido en uno de los más populares para resolver problemas de búsqueda de rutas, como en juegos o sistemas de navegación. A combina dos enfoques: el costo acumulado desde el punto de inicio hasta un nodo, que llamamos "g(n)", y una estimación del costo desde ese nodo hasta el destino, conocida como "h(n)". La suma de estos dos valores nos da "f(n)", que es la función que A* utiliza para decidir qué nodo explorar a continuación.
Imagina que estás en una ciudad y quieres llegar a un parque. Tienes un mapa que te muestra las distancias entre las calles (esto sería "g(n)"). Además, tienes una idea de cuán lejos está el parque desde tu ubicación actual (esto sería "h(n)"). A* te ayuda a elegir la mejor ruta al considerar tanto la distancia que ya has recorrido como la que te queda por recorrer. Así, puedes llegar al parque de la manera más eficiente posible.
Características
- Memoria.
- Tiempo.
- Calidad. Solución óptima.
- Completez. Completo.
Representación
relatedInteligencia Artificial