La búsqueda en amplitud o breadth first search en inglés, es una estrategia de búsqueda no informada o ciega.
Este tipo de búsqueda, donde se evalúan los estados siguientes sin conocer si el estado a evaluar es mejor o peor que el estado anterior. Otro tipo de búsqueda no informada sería la búsqueda en profundidad o Depth First Search (DFS), la cual hablaremos de ella en futuros post.
Tabla de contenidos
Escenario
En machine learning existe un problema habitual, que consiste en encontrar un estado concreto dentro de un espacio de estados.
Por ejemplo, nosotros tenemos el array: {‘l‘,’o‘,’a‘,’h‘} y queremos obtener, dentro de nuestro espacio de estados: {‘h‘,’o‘,’l‘,’a‘}. Con lo cual nos decidimos por usar un algoritmo no informado cómo es el BFS, obviamente para poder ilustrar este post.
Cómo funciona
Creando nuestro espacio de estados
Pare crear nuestro espacio de estados, utilizaremos un grafo, en forma de árbol, donde cada nodo de nuestro árbol, sera un estado en nuestro espacio. Este árbol tendrá un nodo root o estado inicial, en este caso es {‘l‘,’o‘,’a‘,’h‘}.
Estableceremos unas normas o limitaciones, para la generación de los nodos hijos. Por ejemplo, en este caso, hemos decidido generar tres nodos hijos por nodo padre, de tal forma que intercambiaremos las posiciones del array, generando un estado nuevo.Por ejemplo:
- Nodo padre: {‘l‘,’o‘,’a‘,’h‘} donde las posiciones de nuestro array son 0,1,2,3
- Nodo hijos izquierda: intercambiamos las posiciones 0 y 1 {‘o‘,’l‘,’a‘,’h‘}
- Nodo hijo central: intercambiamos las posiciones 1 y 2 {‘l‘,’a‘,’o‘,’h‘}
- Nodo hijo derecha: intercambiamos las posiciones 2 y 3 {‘l‘,’o‘,’h‘,’a‘}
Mientras generamos los hijos comprobamos si el estado obtenido es el deseado
Orden de creación
Para poder generar el árbol adecuadamente, usaremos una lista. Podéis consultar la implementación al final del post.
El algoritmo de búsqueda en amplitud, tiene varias variaciones que hacen este algoritmo más eficiente y también se pueden aplicar restricciones en su profundidad, para no entrar en una búsqueda demasiado cara.
Cómo hacer la búsqueda
Cómo podéis ver la imagen anterior, la cual he obtenido de la web , la búsqueda en amplitud:
- Empezamos con el estado inicial.
- Se generar los hijos y se comprueban si alguno de ellos es el estado esperado
- Si es el estado esperado, hemos acabado, en caso contrario se continua generando los nodos, de los vertices en ese momento
Implementación
