Búsqueda de haz - Beam search

En informática , la búsqueda de haces es un algoritmo de búsqueda heurística que explora un gráfico al expandir el nodo más prometedor en un conjunto limitado. Beam search es una optimización de la mejor búsqueda que reduce los requisitos de memoria. La búsqueda mejor primero es una búsqueda gráfica que ordena todas las soluciones parciales (estados) de acuerdo con alguna heurística. Pero en la búsqueda de haces, solo un número predeterminado de mejores soluciones parciales se mantienen como candidatos. Por tanto, es un algoritmo codicioso .

El término "búsqueda de haz" fue acuñado por Raj Reddy de la Universidad Carnegie Mellon en 1977.

Detalles

Beam search 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. Sin embargo, solo almacena un número predeterminado de mejores estados en cada nivel (llamado ancho de haz). Solo esos estados se expanden a continuación. Cuanto mayor sea el ancho de la viga, menos estados se podarán. Con un ancho de haz infinito, no se poda ningún estado y la búsqueda del haz es idéntica a la búsqueda en amplitud . 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 haces sacrifica la integridad (la garantía de que un algoritmo terminará con una solución, si existe). La búsqueda de haces no es óptima (es decir, no hay garantía de que encontrará la mejor solución). . ${\ Displaystyle \ beta}$

Usos

Una búsqueda de haz se usa con mayor frecuencia para mantener la capacidad de manejo en sistemas grandes con una cantidad de memoria insuficiente para almacenar todo el árbol de búsqueda. Por ejemplo, se ha utilizado en muchos sistemas de traducción automática . (El estado de la técnica ahora utiliza principalmente métodos basados ​​en la traducción automática neuronal ). 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 las oraciones y el resto se descartan. A continuación, el traductor evalúa las traducciones según un criterio determinado, eligiendo la traducción que mejor se ajusta a los objetivos. El primer uso de una búsqueda por haz fue en el Harpy Speech Recognition System, CMU 1976.

Variantes

La búsqueda de haces se ha completado combinándola con la búsqueda de profundidad primero , lo que da como resultado la búsqueda de pila de haces y la búsqueda de haz de profundidad primero , y con la búsqueda de discrepancia limitada, lo que da como resultado la búsqueda de haz con retroceso de discrepancia limitada (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 alcanza una meta. ${\ Displaystyle \ beta}$${\ Displaystyle \ beta}$

Dado que la búsqueda de haces locales 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 denomina búsqueda de haz estocástico . ${\ Displaystyle \ beta}$

Otras variantes son búsqueda de haz flexible y búsqueda de haz de recuperación .

Referencias