En informática , la búsqueda de haz es un algoritmo de búsqueda heurística que explora un grafo expandiendo el nodo más prometedor en un conjunto limitado. La búsqueda de haz es una modificación de la búsqueda de mejor primero que reduce sus requisitos de memoria. La búsqueda de mejor primero es una búsqueda de grafo que ordena todas las soluciones parciales (estados) según alguna heurística. Pero en la búsqueda de haz, solo se mantiene como candidata una cantidad predeterminada de las mejores soluciones parciales. [1] Por lo tanto, es un algoritmo voraz .
La búsqueda de haz utiliza una búsqueda en amplitud para construir su árbol de búsqueda . En cada nivel del árbol, genera todos los sucesores de los estados en el nivel actual, ordenándolos en orden creciente de costo heurístico. [2] Sin embargo, solo almacena un número predeterminado, , de mejores estados en cada nivel (llamado ancho del haz). Solo esos estados se expanden a continuación. Cuanto mayor sea el ancho del haz, menos estados se podan. Con un ancho de haz infinito, no se podan estados y la búsqueda de haz es idéntica a la búsqueda de mejor primero . [3] Por el contrario, un ancho de haz de 1 corresponde a un algoritmo de escalada de colinas . [3] El ancho del haz limita la memoria necesaria para realizar la búsqueda. Dado que un estado objetivo podría potencialmente podarse, la búsqueda de haz sacrifica la completitud (la garantía de que un algoritmo terminará con una solución, si existe una). La búsqueda de haz no es óptima (es decir, no hay garantía de que encuentre la mejor solución).
La búsqueda por haz se utiliza con mayor frecuencia para mantener la manejabilidad en sistemas grandes con una cantidad insuficiente de memoria para almacenar todo el árbol de búsqueda. [4] Por ejemplo, se ha utilizado en muchos sistemas de traducción automática . [5] (El estado del arte ahora utiliza principalmente métodos basados en traducción automática neuronal , especialmente modelos de lenguaje grandes ). Para seleccionar la mejor traducción, se procesa cada parte y aparecen muchas formas diferentes de traducir las palabras. Las mejores traducciones según sus estructuras de oración se conservan y el resto se descarta. Luego, el traductor evalúa las traducciones según un criterio dado, eligiendo la traducción que mejor se ajusta a los objetivos.
El sistema de reconocimiento de voz Harpy (presentado en una tesis de 1976 [6] ) fue el primer uso de lo que se conocería como búsqueda de haz. [7] Si bien el procedimiento se denominó originalmente "modelo de búsqueda de locus", el término "búsqueda de haz" ya se utilizaba en 1977. [8]
La búsqueda de haces se ha completado al combinarla con la búsqueda en profundidad , lo que da como resultado la búsqueda de pila de haces [9] y la búsqueda de haces en profundidad [4] , y con la búsqueda de discrepancia limitada [4] , lo que da como resultado la búsqueda de haces utilizando un retroceso de discrepancia limitada [4] (BULB). Los algoritmos de búsqueda resultantes son algoritmos en cualquier momento que encuentran soluciones buenas pero probablemente subóptimas rápidamente, como la búsqueda de haces, luego retroceden y continúan encontrando soluciones mejoradas hasta la convergencia a una solución óptima.
En el contexto de una búsqueda local , llamamos búsqueda de haz local a un algoritmo específico que comienza seleccionando estados generados aleatoriamente y luego, para cada nivel del árbol de búsqueda, siempre considera nuevos estados entre todos los posibles sucesores de los actuales, hasta que llega a una meta. [10] [11]
Dado que la búsqueda de haces locales suele terminar en máximos locales, una solución común es elegir los siguientes estados de manera aleatoria, con una probabilidad que depende de la evaluación heurística de los estados. Este tipo de búsqueda se denomina búsqueda de haces estocástica . [12]
Otras variantes son la búsqueda de haz flexible y la búsqueda de haz de recuperación . [11]
