7.2 Búsqueda en Profundidad

DFS (Depth-First Search, Búsqueda en Profundidad) es un método utilizado para recorrer o buscar estructuras de datos de árboles o grafos. El algoritmo funciona comenzando en un nodo raíz y recorriendo el grafo lo más lejos posible a lo largo de cada rama antes de retroceder. Este proceso continúa hasta que se hayan explorado todos los nodos.

Para ilustrar este concepto, imagínate en un laberinto. Si decides utilizar el enfoque DFS, elegirías una dirección y la seguirías todo lo que puedas. Si llegas a un callejón sin salida, retrocederías y elegirías una nueva dirección para explorar. Este proceso se repetiría hasta que hayas explorado todos los caminos posibles en el laberinto.

El algoritmo DFS se utiliza comúnmente en diversas aplicaciones, como determinar la conectividad de un grafo, encontrar un camino entre dos nodos e identificar ciclos en un grafo. Es un algoritmo simple pero poderoso que se puede utilizar para resolver una amplia variedad de problemas relacionados con la teoría de grafos y las estructuras de datos.

Aquí tienes una explicación más detallada:

Inicialización: Para empezar, debes seleccionar un nodo del grafo que se considerará el nodo 'fuente' y luego marcarlo como visitado. Este es un primer paso importante ya que sienta las bases para el resto del recorrido del grafo. Es importante considerar cuidadosamente qué nodo seleccionas como nodo fuente, ya que puede afectar en gran medida la eficiencia general del recorrido. Una vez que el nodo se ha seleccionado y marcado como visitado, puedes comenzar el proceso de recorrido del grafo.
Exploración: Un aspecto importante del nodo actual es su 'frontera', que está formada por todos los nodos que se pueden alcanzar directamente desde él. Al examinar esta frontera, podemos obtener una mejor comprensión de los posibles caminos que se pueden tomar y los resultados potenciales que pueden surgir. Además, al explorar cada uno de estos nodos y analizar la información contenida en ellos, podemos tomar decisiones más informadas sobre qué dirección tomar y qué acciones seguir. Este proceso de exploración y análisis es esencial para lograr el éxito en cualquier empresa y es un componente clave de la toma de decisiones efectiva.
Recursión: La recursión es un proceso en el que una función se llama a sí misma una y otra vez hasta que se cumple cierta condición. En el contexto del algoritmo de Búsqueda en Profundidad, para cada nodo en la frontera, el algoritmo verifica si ha sido visitado o no. Si no ha sido visitado, el algoritmo aplicará recursivamente el algoritmo de Búsqueda en Profundidad a él, lo que significa que llamará a la función una y otra vez hasta que se hayan visitado todos los nodos y se cumpla la condición. Este proceso de llamar a la función una y otra vez se llama recursión. Es un concepto importante en la informática y la programación, y se utiliza en muchos algoritmos para resolver problemas complejos de manera eficiente.

Utilicemos código en Python para ilustrar DFS en un grafo:

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.append(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
dfs(visited, graph, 'A')

En este programa en Python, 'A' es el nodo fuente. Desde 'A', DFS primero va a 'B', luego a 'D' porque 'B' y 'D' son los primeros nodos en sus respectivas listas. Una vez que llega a 'D', que no tiene vecinos, retrocede a 'B' y visita 'E', luego 'F'. Finalmente, retrocede hasta 'A' y visita 'C' y su vecino 'F'. Sin embargo, 'F' ya está marcado como visitado, por lo que DFS termina.

En resumen, DFS, o Búsqueda en Profundidad, explora cada rama de un grafo lo más lejos posible antes de retroceder. Este enfoque hace que DFS sea altamente eficiente para ciertas tareas, como encontrar componentes conectados o encontrar un camino de un nodo a otro. También es una excelente opción para la ordenación topológica de un grafo. Sin embargo, para tareas como encontrar el camino más corto, DFS puede que no sea el algoritmo más adecuado. En tales casos, la Búsqueda en Amplitud o el algoritmo de Dijkstra pueden ser más apropiados.

Es importante recordar que los algoritmos son como herramientas: diferentes herramientas son apropiadas para diferentes tareas. Elegir el algoritmo adecuado para una tarea puede marcar la diferencia en la eficiencia del programa o del sistema. En conclusión, aunque DFS puede que no sea la mejor opción para todas las tareas, es una herramienta invaluable para ciertos tipos de problemas y debería incluirse en el arsenal de todo programador.

Nos gustaría adentrarnos un poco más en una de las técnicas fundamentales asociadas con DFS: el backtracking. El backtracking es un enfoque algorítmico ampliamente utilizado para resolver problemas computacionales que requieren una secuencia de pasos o un conjunto de opciones.

Básicamente, el algoritmo explora todas las opciones o pasos posibles para encontrar la solución. Si una opción no da el resultado deseado, el algoritmo retrocede y elige la siguiente opción. Este método se usa muy comúnmente para resolver rompecabezas como Sudoku o laberintos.

Para ilustrar este concepto más a fondo, tomemos el ejemplo de usar DFS con backtracking para resolver un laberinto simple. Imagina una cuadrícula 2D que representa un laberinto donde 1 representa paredes y 0 representa un camino abierto. El objetivo es navegar desde la esquina superior izquierda hasta la esquina inferior derecha. Al usar DFS con backtracking, el algoritmo explora todos los caminos posibles y retrocede cada vez que llega a un callejón sin salida. Esto permite que el algoritmo encuentre el camino óptimo y resuelva el laberinto de manera eficiente.

Así es como podrías implementarlo en Python:

def solveMaze(maze):
    # Creating a solution matrix of same size as maze
    solution = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]

    # Function to solve the maze
    # Using backtracking to find the path
    def solveMazeUtil(maze, x, y, solution):
        # if x, y is the finish return True
        if x == len(maze) - 1 and y == len(maze[0]) - 1:
            solution[x][y] = 1
            return True

        # Check if maze[x][y] is valid
        if x >= 0 and x < len(maze) and y >= 0 and y < len(maze[0]) and maze[x][y] == 0:
            # Mark x, y as part of solution path
            solution[x][y] = 1

            # Move forward in x direction
            if solveMazeUtil(maze, x + 1, y, solution):
                return True

            # If moving in x direction doesn't give solution
            # then Move down in y direction
            if solveMazeUtil(maze, x, y + 1, solution):
                return True

            # If none of the above movements work then
            # BACKTRACK: unmark x, y as part of solution path
            solution[x][y] = 0
            return False

        return False

    # If a path is found in the maze then solution will hold that path
    # otherwise no solution exists
    if solveMazeUtil(maze, 0, 0, solution) is False:
        print("No path exists")
        return False

    # Printing the path
    for i in solution:
        print(i)
    return True

# Driver code
maze = [[0, 1, 0, 1, 1],
        [0, 0, 0, 0, 0],
        [1, 1, 1, 1, 0],
        [1, 1, 1, 1, 0],
        [1, 1, 1, 0, 0]]

solveMaze(maze)

La salida del programa anterior proporcionará el camino desde la primera celda hasta la última celda en el laberinto.

Este es un ejemplo de cómo DFS puede ser utilizado para resolver problemas complejos con la ayuda de backtracking. Espero que esto ayude a profundizar aún más tu comprensión del tema.