En informática , la búsqueda de haces es un algoritmo de búsqueda heurística que explora un gráfico expandiendo el nodo más prometedor en un conjunto limitado. La búsqueda por haz es una modificación de la búsqueda "mejor primero" que reduce sus requisitos de memoria. La búsqueda del mejor primero es una búsqueda de gráficos que ordena todas las soluciones parciales (estados) de acuerdo con alguna heurística. Pero en la búsqueda por haces sólo se mantiene como candidatas un número predeterminado de mejores soluciones parciales. [1] Es, por tanto, un algoritmo codicioso .
La búsqueda por haz utiliza la 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, clasificándolos en orden creciente de costo heurístico. [2] Sin embargo, solo almacena un número predeterminado, de los mejores estados en cada nivel (llamado ancho del haz). Sólo esos estados se amplían a continuación. Cuanto mayor es el ancho del haz, menos estados se podan. Con un ancho de haz infinito, no se elimina ningún estado y la búsqueda del haz es idéntica a la búsqueda del mejor primero . [3] Por el contrario, un ancho de haz de 1 corresponde a un algoritmo de escalada . [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 por haz sacrifica la integridad (la garantía de que un algoritmo terminará con una solución, si existe). La búsqueda por haz no es óptima (es decir, no hay garantía de que encontrará la mejor solución).
Una búsqueda por haz se utiliza con mayor frecuencia para mantener la manejabilidad en sistemas grandes con una cantidad de memoria insuficiente 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 de la técnica 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. Se conservan las mejores traducciones según la estructura de sus oraciones y el resto se descarta. A continuación, el traductor evalúa las traducciones según un criterio determinado y elige la traducción que mejor cumple sus objetivos.
El sistema de reconocimiento de voz Harpy (introducido en una disertación de 1976 [6] ) fue el primer uso de lo que se conocería como búsqueda por haz. [7] Si bien el procedimiento se denominó originalmente "modelo de búsqueda de locus", el término "búsqueda por haz" ya estaba en uso en 1977. [8]
La búsqueda de haces se ha completado combinándola con la búsqueda en profundidad , lo que da como resultado una búsqueda en pila de haces [9] y una búsqueda de haces en profundidad , [4] y con una búsqueda de discrepancia limitada, [4] que da como resultado una búsqueda de haces usando un retroceso de discrepancia limitada [4] (BOMBILLA). Los algoritmos de búsqueda resultantes son algoritmos en cualquier momento que encuentran rápidamente soluciones buenas pero probablemente subóptimas, como la búsqueda por haz, 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 alcanza una meta. [10] [11]
Dado que la búsqueda de haz local a menudo termina en máximos locales, una solución común es elegir los siguientes estados de forma aleatoria, con una probabilidad que depende de la evaluación heurística de los estados. Este tipo de búsqueda se llama búsqueda de haz estocástico . [12]
Otras variantes son la búsqueda de haz flexible y la búsqueda de haz de recuperación . [11]
