Un algoritmo heurístico de búsqueda en grafo/árbol que explora el espacio de búsqueda manteniendo solo un número fijo (ancho del haz) de las soluciones parciales mejor clasificadas en cada profundidad, podando alternativas de menor rango para limitar el coste computacional mientras sacrifica completitud u optimalidad según el tamaño del haz y la heurística de puntuación.

Principio

En cada nivel de expansión, puntuar candidatos parciales por una heurística o la probabilidad del modelo, retener los B mejores candidatos (haz), expandirlos para el siguiente nivel y repetir; esta estrategia de amplitud limitada intercambia exploración exhaustiva por un control manejable de la expansión usando un criterio de ranking.

Demostración

En decodificación de secuencias (p. ej. traducción automática), beam search mantiene en cada paso temporal las B secuencias parciales más probables según las probabilidades condicionales del modelo; produce salidas plausibles de forma eficiente pero puede perder secuencias globalmente óptimas debido a poda temprana o mal scoring.

Aplicación incorrecta

Usar un haz demasiado pequeño para tareas con dependencias de largo alcance, confiar en un scoring local ingenuo que favorezca prefijos cortos o de alta probabilidad, o asumir que beam search produce salidas óptimas o diversas sin ajustes (p. ej. normalización de longitud, heurísticas para promover diversidad).

Consecuencia

Permite decodificación y búsqueda prácticas en grandes espacios combinatorios controlando la ramificación con el ancho del haz; los resultados son más rápidos y a menudo de alta calidad en la práctica, pero pueden sesgarse por el scoring, infrarepresentar rutas de baja probabilidad pero globalmente buenas, y carecer de garantías de completitud salvo que el haz sea ilimitado.

Inversión

La búsqueda exhaustiva o por amplitud completa (ancho del haz igual al frente completo) es la inversión: restaura completitud y optimalidad a costa de mucho mayor coste computacional y de memoria.

Límite

Aplicable cuando las soluciones parciales pueden puntuarse y compararse de forma significativa; no apropiado cuando el scoring es poco fiable, cuando se requiere completitud, o cuando la memoria/haz debe ser extremadamente pequeño respecto al factor de ramificación; se necesitan ajustes para entornos estocásticos o adversariales.

Tensión semántica

A menudo se equipara con búsqueda codiciosa o best‑first; beam search generaliza lo codicioso conservando múltiples candidatos por nivel (B>1), siendo lo codicioso el caso B=1, mientras que best‑first puede expandir según puntuación global de la frontera en lugar de niveles fijos.

Síntesis

Beam search es una heurística por niveles limitada por haz que retiene un número fijo de soluciones parciales mejor clasificadas para mantener la búsqueda manejable: una aproximación eficiente cuyo valor depende críticamente de la calidad del scoring y del ancho del haz, equilibrando velocidad y memoria frente a completitud y optimalidad.