next up previous
Next: 2.3.6 Mejor Solución Up: 2.3 Búsqueda con Información Previous: 2.3.4 Híbridos

2.3.5 Beam-Search

Otra alternativa, que está entre hill-climbing y best-first es beam-search. En esta estrategia, se mantienen las $k$ mejores alternativas.


Tabla 2.9: Algoritmo beam-search
\begin{table} \begin{tabbing} 12\=123\=123\= \kill \> Crea una agenda de un elem... ...\> selecciona los $k$ mejores (elimina los dem\a'{a}s) \end{tabbing}\end{table}


Si $k = 1$ es como hill-climbing, si $k$ es tan grande para considerar todos los nodos de la agenda es como best-first.

Figura 2.8: Búsqueda Beam search con $k = 2$.
\begin{figure}\vspace*{0.5cm} \centerline{\hbox{ \psfig{figure=/home/emorales/Cu... .../emorales/Cursos/Busqueda/LaTeX/Imagenes/beam6.PS,height=4.5cm} }}\end{figure}


Eduardo Morales Manzanares 2004-11-02