7.6 Problemas Prácticos

Sumergámonos en algunos problemas prácticos que pueden ayudarnos a entender mejor estos algoritmos de gráficos.

Problema 1: DFS en la Resolución de Laberintos

Comencemos con un problema fácil de resolver un laberinto usando DFS. En este problema, se nos da una cuadrícula (matriz 2D), y tenemos que encontrar un camino desde la posición de inicio hasta la posición objetivo. Podemos movernos hacia arriba, abajo, izquierda y derecha, pero no en diagonal.

Aquí tienes una implementación simple en Python usando DFS:

def dfs(maze, start, goal):
    stack = [(start, [start])]
    visited = set()

    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in get_neighbors(maze, vertex):
                stack.append((neighbor, path + [neighbor]))

def get_neighbors(maze, position):
    # Returns the valid neighbors of a position in the maze
    # We assume the maze to be a list of lists in Python

    i, j = position
    neighbors = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    valid_neighbors = []

    for x, y in neighbors:
        if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0: # 0 signifies a path, 1 is a wall
            valid_neighbors.append((x, y))

    return valid_neighbors

Puedes probar esto con un laberinto simple (una lista de listas donde 0 significa un camino y 1 es una pared).

Problema 2: Camino Más Corto en una Cuadrícula con BFS

Un ejemplo típico de BFS es encontrar el camino más corto en una cuadrícula (por ejemplo, desde la esquina superior izquierda hasta la esquina inferior derecha). Esto se debe a que BFS es un recorrido por niveles y visita todos los vértices en el mismo nivel antes de profundizar en el grafo. Intentemos resolver un problema usando BFS. La declaración del problema es similar al problema anterior, pero en lugar de DFS, usamos BFS para encontrar el camino más corto.

Adoptaremos un enfoque simple en Python para demostrar:

from collections import deque

def bfs(grid, start, goal):
    queue = deque([([start], 0)])  # [(path, cost)]
    seen = {start: 0}

    while queue:
        path, cost = queue.popleft()
        current = path[-1]

        if current == goal:
            return path, cost

        for neighbor in get_neighbors(grid, current):
            if neighbor not in seen or cost + 1 < seen[neighbor]:
                seen[neighbor] = cost + 1
                queue.append((path + [neighbor], cost + 1))

    return None  # No path found

# get_neighbors is same as in the previous example

Puedes probar esto con una cuadrícula simple para entender cómo funciona BFS.

Nota: Para resolver los problemas anteriores utilizando la búsqueda A*, el Algoritmo de Dijkstra u otros algoritmos de grafos, solo necesitamos modificar la forma en que exploramos los vecinos y posiblemente agregar una cola de prioridad.

¡Inténtalo con estos problemas y feliz resolución de problemas!