Heuristic Search – Búsqueda Heurística
La búsqueda heurística es un enfoque utilizado en inteligencia artificial y ciencias de la computación.
Para encontrar soluciones óptimas.
Aproximadas en problemas de búsqueda complejos.
Este método se basa en heurísticas.
Son reglas o estrategias diseñadas para guiar el proceso de búsqueda.
Hacia soluciones prometedoras.
Reduciendo significativamente el tiempo y el esfuerzo.
Necesarios en comparación con una búsqueda exhaustiva.
Características Principales
Uso de Heurísticas
Las heurísticas son funciones que proporcionan una estimación.
De la calidad de un estado.
De la proximidad de un estado a la solución objetivo.
No garantizan una solución óptima.
Suelen ser efectivas en problemas prácticos.
Reducción del Espacio de Búsqueda
En lugar de explorar todas las posibles soluciones.
La búsqueda heurística prioriza.
Aquellas que parecen más prometedoras.
Flexibilidad
Se puede adaptar a una variedad de problemas.
Juegos, planificación, enrutamiento y optimización.
Funcionamiento de la Búsqueda Heurística
Definición del Problema
Un problema de búsqueda se modela como un grafo.
Donde los nodos representan estados.
Las aristas representan transiciones entre estados.
Definición de la Función Heurística
La función heurística h(n) estima el costo.
La distancia desde un nodo n al objetivo.
Exploración Guiada
En lugar de buscar de manera exhaustiva.
El algoritmo evalúa nodos basándose en h(n)
Para decidir cuáles explorar primero.
Ejemplos de Algoritmos de Búsqueda Heurística
Greedy Best-First Search
Selecciona el nodo con el valor heurístico más bajo h(n).
Tratando de aproximarse rápidamente al objetivo.
Ventaja: Rápido en problemas bien definidos.
Desventaja: No garantiza una solución óptima.
A*
Utiliza una función combinada f(n) = g(n)+h(n), donde:
g(n) es el costo acumulado desde el inicio hasta el nodo actual.
h(n) es la estimación del costo restante al objetivo.
Ventaja:
Encuentra soluciones óptimas si h(n) es admisible (no sobreestima el costo).
Hill Climbing
Avanza hacia estados que mejoran continuamente la función heurística.
Desventaja:
Puede quedar atrapado en máximos locales o mesetas.
Simulated Annealing
Introduce un componente aleatorio para escapar de máximos locales.
Ajustando gradualmente la probabilidad de aceptar soluciones peores.
Beam Search
Explora un número fijo de caminos más prometedores en cada nivel.
Reduciendo significativamente el espacio de búsqueda.
Aplicaciones de la Búsqueda Heurística
Juegos
Evaluación de posibles movimientos en juegos como ajedrez o Go.
Ejemplo:
Uso de funciones heurísticas en motores.
De ajedrez para evaluar posiciones.
Planificación y Optimización
Resolución de problemas como planificación de rutas.
Asignación de recursos o secuenciación de tareas.
Ejemplo:
Algoritmos de navegación en mapas.
Google Maps utiliza variantes de A*.
Resolución de Rompecabezas
Problemas como el cubo de Rubik.
El juego de las torres de Hanoi o los rompecabezas deslizantes.
Visión por Computadora
Búsqueda de patrones o características específicas en imágenes.
Utilizando heurísticas para reducir el espacio de búsqueda.
Procesamiento de Lenguaje Natural
Optimización de trayectorias en árboles de análisis sintáctico o semántico.
Ventajas de la Búsqueda Heurística
Eficiencia
Reduce drásticamente el tiempo de búsqueda.
Al centrarse en las soluciones más prometedoras.
Escalabilidad
Puede manejar problemas grandes y complejos.
Serían inabordables con búsquedas exhaustivas.
Facilidad de Adaptación
Permite diseñar heurísticas específicas para problemas concretos.
Limitaciones de la Búsqueda Heurística
Dependencia de la Heurística
La calidad de la solución depende en gran medida.
De la función heurística elegida.
Óptimos Locales
Algunos algoritmos como Hill Climbing.
Pueden quedarse atrapados en soluciones subóptimas.
No Garantiza Completitud
Algunos métodos heurísticos pueden no explorar todas las posibles soluciones.
No garantizar que encuentren una solución, incluso si existe.
Costos Computacionales en Problemas Complejos
El cálculo de la heurística en problemas de alta dimensionalidad puede ser costoso.
Consideraciones para Diseñar una Función Heurística
Admisibilidad
h(n) no debe sobreestimar el costo real al objetivo.
Para garantizar soluciones óptimas en algoritmos como A*.
Consistencia (o Monotonicidad)
La estimación debe cumplir h(n) ≤ c(n,m) + h(m), donde c(n,m) es el costo de ir del nodo n al m.
Dominancia
Entre dos heurísticas la que proporciona estimaciones más altas.
Sin perder admisibilidad es preferible.
Con el aumento de la complejidad de los problemas en IA.
Las búsquedas heurísticas siguen evolucionando.
Para abordar aplicaciones como la robótica.
Los sistemas autónomos y el análisis de grandes volúmenes de datos.
Se están integrando con técnicas de aprendizaje automático.
Para diseñar heurísticas dinámicas y adaptativas.
Abriendo nuevas posibilidades en la resolución.
De problemas complejos.
Te puede interesar;
Curso de ChatGPT: Todo lo que debes saber
