Búsqueda focal probabilística: aceleración de la búsqueda con suboptimalidad limitada mediante avance de límite inferior

La búsqueda subóptima con límite busca obtener una solución cuya calidad no supere un factor w respecto a la óptima, mientras intenta minimizar el trabajo computacional. El método tradicional llamado Focal Search (FS) selecciona los nodos a expandir dentro de un conjunto llamado FOCAL, que agrupa los estados cuya función f no excede w · f min. Sin embargo, la política determinista de FS a menudo mantiene constante el valor mínimo de f, lo que retrasa la incorporación de nuevos nodos al foco y, por ende, el hallazgo de soluciones factibles.

Para superar esa limitación, los autores proponen Probabilistic Focal Search (PFS). En cada paso, con una probabilidad p se sigue la elección guiada por FS; con probabilidad 1 – p se expande el nodo de menor f disponible en la lista OPEN. Esta segunda opción impulsa la actualización del límite inferior f min, ampliando el conjunto FOCAL y permitiendo que nodos potencialmente útiles ingresen antes. El equilibrio entre la guía heurística y el avance del límite inferior reduce el número de expansiones necesarias cuando la progresión de f min se estanca.

Los experimentos comparan PFS con FS en problemas clásicos como el N‑Puzzle, el ordenamiento de panqueques y el viajante de comercio, además de una variante “anytime” evaluada en el TSP cubriente generalizado. Los resultados indican reducciones de hasta un 90 % en la cantidad de nodos expandidos en los casos donde la meseta de f min es prolongada; en dominios donde FS ya avanza rápidamente, el beneficio es menor. Un experimento adicional traslada el mismo esquema probabilístico a Dynamic Potential Search, creando Probabilistic Dynamic Potential Search (PDPS), cuyo desempeño también depende del dominio y del factor w.

Esta investigación es relevante porque muestra cómo introducir aleatoriedad controlada puede acelerar búsquedas que, de otro modo, quedarían atrapadas en cuellos de botella, ofreciendo una herramienta potencialmente útil para optimizar algoritmos de planificación y resolución de problemas en IA.

Leer artículo original en arXiv cs.AI

Este resumen es una síntesis informativa elaborada por dataqbs.com. Todos los derechos sobre el contenido original pertenecen a su autor y al medio de comunicación citado. Nosotros solo actuamos como curadores de noticias tecnológicas, sin reclamar autoría alguna.