Búsqueda en profundidad

Búsqueda en profundidad

Para descubrir cómo atravesar un laberinto a través del código, primero debemos comprender qué es la búsqueda en profundidad. La búsqueda en profundidad (a veces denominada en este artículo como DFS) es un algoritmo de recorrido de gráfico / árbol que sigue una ruta lo más lejos posible hasta que alcanza la meta o no tiene a dónde ir. Es casi como correr lo más lejos que puedas en una dirección hasta chocar contra una pared. Es de esperar que esa analogía ayude a aclarar cualquier confusión persistente. ¡Incluso podría estar comenzando a ver cómo podemos usar la búsqueda en profundidad para resolver un laberinto!

Antes de sumergirnos en el algoritmo en sí, hay algunas cosas que debemos comprender sobre la búsqueda en profundidad primero. Hay muchos enfoques y estilos para implementar un algoritmo de búsqueda en profundidad y muchas de esas opciones de implementación dependerán por completo del problema que esté tratando de resolver. Primero definamos algunas suposiciones. Estas suposiciones pueden parecer muy sencillas, pero son realmente importantes para ayudarnos a encontrar una solución para resolver nuestro laberinto.

Supuestos

Cada laberinto tiene un punto de partida y un punto final.

Esta suposición es principalmente por simplicidad. Podríamos manejar casos extremos todo el día. Como que puede que no haya ningún camino que conduzca a una salida en el laberinto, pero ese no es el objetivo de este artículo. En cambio, vamos a mantener nuestras limitaciones lo más cerca posible de un laberinto real. Seguramente un laberinto real tendría una salida. :)

Los laberintos se componen de muros.

Estos muros se considerarán intransitables. Esto significa que, desafortunadamente, no podemos codificar nuestra solución de una manera que pase por alto los muros. Entonces, a menos que recientemente hayamos encontrado una manera de analizar la materia, hemos definido una restricción. Por lo tanto, necesitamos encontrar alguna forma de alertar a la computadora sobre dónde existen las paredes o, más bien, qué caminos están disponibles en cualquier punto del laberinto.

Solo nos preocupamos por encontrar el primer camino disponible a través del laberinto.

Esta tercera y última suposición que estamos haciendo puede parecer un poco impactante, pero es importante entender que en nuestra implementación de DFS no nos preocupa encontrar el camino más corto. Solo nos importa que haya una ruta y que podamos regresar.

Pasos de la búsqueda en profundidad

¡Bien! Ahora que tenemos nuestras suposiciones claramente escritas, ¡comencemos con un ejemplo de DFS![pic 1]

Figura 2: nodos, bordes y una pila de llamadas vacía.

La estructura de la figura 2 es una forma de representar un gráfico. Hay muchas formas de representar gráficos, pero para este ejemplo, solo nos preocupa el hecho de que nuestro gráfico contiene nodos y bordes.

Los nodos, que se muestran como cuadrados grises con números, contienen todos los datos que nos interesan. Los números en los nodos representan ID, estos ID son poderosos ya que son únicos para cada nodo y brindan mucha utilidad que usaremos para resolver nuestro laberinto. La propiedad visitada define una forma en que podemos determinar si ya hemos visto un nodo. De esa manera, no atravesamos los nodos varias veces.

Los bordes son los que unen los nodos. Si no hay borde entre dos nodos como en la instancia del nodo 3 - nodo 5, podemos volver a nuestra segunda suposición (los laberintos tienen paredes) y no usar ningún borde como una indicación de que no podemos viajar en esa dirección, también conocido como un muro. ¡ahí!

La pila de llamadas, representada como ese rectángulo alargado en el diagrama, es una estructura debajo del capó. La pila apila llamadas a funciones, en nuestro caso llamadas a nodos, y nos muestra en qué punto estamos en la ejecución del programa. ¡La pila es también lo que finalmente nos dará el poder de devolver una ruta desde el gráfico!

Atravesar

¡Esa fue mucha terminología! ¿Aún conmigo? Ahora comencemos a ejecutar la búsqueda en profundidad y recorramos nuestro gráfico. ¿Recuerda la primera suposición? Los gráficos generalmente no tienen un punto de partida designado, pero para realizar DFS, tenemos que comenzar en algún lugar, así que comenzaremos con el Nodo 1 .

Paso 1

[pic 2]

Figura 3: el verde indica el nodo que estamos evaluando activamente.

Lo que sucede en la figura 3 es que llamamos a DFS en el nodo 1, que lo coloca en la pila de llamadas. Marcamos el Nodo 1 como visitado para no volver a evaluar accidentalmente el nodo, ya que eso podría llevarnos a no encontrar nunca una ruta. Luego verificamos si el Nodo 1 es igual al nodo que estamos buscando ( Nodo 6 ). No lo es, así que pasamos a la lista de adyacencia del Nodo 1. Cada nodo contiene una lista de referencias a todos los nodos a los que están conectados. ¡Entonces vemos que el Nodo 2 está conectado al Nodo 1 y pasamos al siguiente paso!

Paso 2

Después de mirar la lista de adyacencia del Nodo 1 , terminamos evaluando el Nodo 2. Los pasos son similares, marcamos el nodo como visitado y luego verificamos si es igual al nodo que estamos buscando. No es así que llamemos a DFS en el nodo 2 para profundizar aún más en el gráfico.

[pic 3]

Figura 4: el azul indica un nodo ya evaluado (visitado).

Ahora miramos la lista de adyacencia del Nodo 2 . Visualmente, podemos ver que el nodo 2 está conectado al nodo 1, 0, 3 y 4. Son cuatro bordes, lo que significa cuatro caminos diferentes que podemos tomar. Entonces, ¿cómo elegimos? Bueno, honestamente, el nodo real que elijamos no importa. El orden depende completamente de cómo almacenamos nuestros nodos en la lista de adyacencia. En aras de la integridad, mostraré cómo funciona para todos ellos. Ya hemos visitado el nodo 1, así que eso está fuera de la mesa. Comencemos con el nodo 0.

...