Inteligencia Artificial: Beam Search (BS)

El algoritmo de Beam Search (BS) es un derivado de un branch-and-bound que utiliza la búsqueda de primero en anchura, e incorpora una heurística para escoger en cada nivel solo los mejores β nodos. Los mejores nodos se guarnan en lo que llama el bear, y β suele denominarse bear width. Este método sacrifica completitud a cambio de un enfoque heurístico muy efectivo.

Los mejores β nodos son seleccionador por funciones de evaluación de un paso, las cuales estiman el costo de expandir la solución actual. Note se que los nodos en el vean representan soluciones parciales (evita el problema de la explosión combinatoria de búsqueda en amplitud por primera ez por ampliar solo los β nodos más prometedores en cada nivel. Una heurística se utiliza para predecir cuales nodos son propensos a ser el mas cerca a la meta o goal).

Algoritmo 1

1. Formar una cola de un elemento Q que consiste en el nodo raíz

2. Hasta que Q está vacío o el objetivo se ha llegado a determinar si alguno de los elementos de Q es el objetivo.

a. Si es así, no hacen nada

b. Si no es así, quitar los elementos de Q y añadir a sus hijos, en su caso, la parte posterior de Q.

c. Ordenar Q por heurística.

d. Quite todos, pero los primeros p nodos de Q

3. Si el objetivo es alcanzado, éxito, si no fracaso

Algoritmo 2

COLA <- la ruta solo contiene al padre;

While COLA no está vacía and nodo destino no encontrado

do	/ Borrar todos las turas contenidas en la COLA; \| Crear nuevas rutas de todos sus hijos; \| Ordena nueva lista de menor a mayor según los \| valores heurística del último nodo; \ Añadir las nuevas “beam” rutas al final de la COLA;

If nodo destino encontrado

Then return (éxito);

Else return (fracaso);

Evaluación

Si hay más de un nodo objetivo, siempre coger el más cercano al nodo en generaciones. Esto tiene un valor si el árbol está desequilibrado, pero inútil si los nodos meta se encuentran en niveles similares.

Esta es una búsqueda incompleta. Existe el peligro de que un objetivo encontrar la ruta será removido de Q antes de que pueda ser explorado. Esto puede llevar a no encontrar ningún objetivo en absoluto.