La búsqueda en profundidad o Depth 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 breadth first search (BFS), donde ya he hablado en otro post.
ESCENARIO
Usaremos el mismo escenario que en breadth first search (BFS): 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 DFS, obviamente para poder ilustrar este post.
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 CREACION
Para poder generar el árbol adecuadamente, usaremos un Stack (LIFO). Podéis consultar la implementación al final del post.
El algoritmo de búsqueda en amplitud, tiene varias variaciones qué 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.
COMO 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 usando la cola LIFO, para obtener el siguiente
Como podéis ver la única diferencia entra DFS y breadth first search (BFS) es la implementación que contiene nuestros vertices y cómo son recuperados: LIFO para DFS y FIFO para BFS.
Si comparáis las implementaciones lo veréis más claro
OBSERVACIONES
A simple vista podemos ver que el resultado de este tipo de búsquedas es peor, menos optimo que el anterior. Otro problema es cuando la búsqueda no esta limitada en profundidad, podemos no salir de la primera rama, sin encontrar un resultado esperado
IMPLEMENTACIÓN
