Introducción al algoritmo de búsqueda de haz

Introducción:
una técnica heurística es un conjunto de criterios para determinar cuál de las múltiples opciones será la más efectiva para lograr un objetivo en particular. Esta estrategia aumenta la eficiencia de un proceso de búsqueda al rendir reclamos de sistematicidad e integridad de los mejores.
Podemos esperar lograr una buena solución a problemas difíciles (como el problema del viajante de comercio) en menos de un tiempo exponencial si usamos las heurísticas apropiadas. 

Beam Search:
un algoritmo de búsqueda heurística que examina un gráfico extendiendo el Node más prometedor en un conjunto limitado se conoce como beam search. 
Beam search es una técnica de búsqueda heurística que siempre expande el número W de los mejores Nodes en cada nivel. Progresa nivel por nivel y se mueve hacia abajo solo desde los mejores Nodes W en cada nivel. Beam Search utiliza la búsqueda primero en amplitud para construir su árbol de búsqueda. Beam Search construye su árbol de búsqueda utilizando la búsqueda en amplitud. Genera todos los sucesores del estado del nivel actual en cada nivel del árbol. Sin embargo, en cada nivel, solo evalúa un número W de estados. Otros Nodes no se tienen en cuenta. 
El costo heurístico asociado con el Node se usa para elegir los mejores Nodes. El ancho de la búsqueda del haz se denota por W. Si B es el factor de ramificación, en cada profundidad, siempre habrá W × B Nodes en consideración, pero solo se elegirá W. Se recortan más estados cuando se reduce el ancho del haz. 
Cuando W = 1, la búsqueda se convierte en una búsqueda de escalada en la que siempre se elige el mejor Node de los Nodes sucesores. No se eliminan estados si el ancho del haz es ilimitado y la búsqueda del haz se identifica como una búsqueda en anchura. 
El ancho de haz limita la cantidad de memoria necesaria para completar la búsqueda, pero tiene el costo de la integridad y la optimización (posiblemente que no encuentre la mejor solución). La razón de este peligro es que el estado deseado podría haber sido podado. 
Ejemplo: el árbol de búsqueda generado con este algoritmo con W = 2 y B = 3 se muestra a continuación:

Los Nodes negros se seleccionan en función de sus valores heurísticos para una mayor expansión.

El algoritmo para la búsqueda de haz se da como:

Entrada: Estados de inicio y objetivo.
Variables locales: OPEN, NODE, SUCCS, W_OPEN, FOUND
Salida: Sí o No (sí si la búsqueda se realiza con éxito)

Start 
Take the inputs 
NODE = Root_Node & Found = False
If : Node is the Goal Node,
     Then Found = True, 
Else : 
     Find SUCCs of NODE if any, with its estimated cost&
     store it in OPEN List 
While (Found == false & not able to proceed further), do
{
     Sort OPEN List
     Select top W elements from OPEN list and put it in
     W_OPEN list and empty the OPEN list.
     for each NODE from W_OPEN list
     {
         if NODE = Goal,
             then FOUND = true 
         else
             Find SUCCs of NODE. If any with its estimated
             cost & Store it in OPEN list
     }
}
If FOUND = True,
    then return Yes
else
    return No
Stop