基于DFS、BFS解决迷宫问题

前言

        分享一次算法分析的作业。

        深度优先搜索和广度优先搜索是两种常用的图搜索算法。深度优先搜索（DFS）是一种递归的搜索算法，其核心思想是沿着一个分支尽可能深入地搜索，直到达到最深的节点，然后再回溯到上一层，继续探索其他分支。广度优先搜索（BFS）则采用逐层扩展的方式，先访问当前节点的所有邻居节点，再逐层向外扩展。

        设计一个算法解决迷宫问题，通过深度优先搜索和广度优先搜索算法找到从起点到终点的路径。迷宫由空格和墙壁组成。用二维矩阵表示迷宫，0表示空格，1表示墙壁。

代码

测试时，请替换 maze 中的二维数组

BFS

import time
from collections import deque
from memory_profiler import profile

@profile
def bfs(maze, start, end):
    queue = deque([(start, [start])])
    visited = set()

    while queue:
        current, path = queue.popleft()

        if current == end:
            return path

        if current in visited:
            continue

        visited.add(current)

        neighbors = get_neighbors(maze, current)
        if neighbors is not None:
            for neighbor in neighbors:
                queue.append((neighbor, path + [neighbor]))

    return None


def get_neighbors(maze, current):
    row, col = current
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右、左、下、上

    neighbors = []
    for dr, dc in directions:
        nr, nc = row + dr, col + dc
        if 0 <= nr < len(maze) and 0 <= nc < len(maze[0]) and maze[nr][nc] == 0:
            neighbors.append((nr, nc))

    return neighbors

def create_path_matrix(maze, path):
    path_matrix = [[maze[row][col] if (row, col) not in path else 'P' for col in range(len(maze[0]))] for row in range(len(maze))]
    return path_matrix

  

if __name__ == "__main__":
    maze =[
      [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],

    ]





    start = (0, 0)
    end = (len(maze) - 1, len(maze[0]) - 1)

    start_time = time.time()
    result = bfs(maze, start, end)
    end_time = time.time()

    if result:
        path_matrix = create_path_matrix(maze, result)
        print("BFS Result: Path found")
        for row in path_matrix:
            print(' '.join(map(str, row)))
    else:
        print("BFS Result: No path found")

    print(f"BFS Time: {end_time - start_time} seconds")

# 新增的代码，用于格式化输出 memory_profiler 的结果
import re

def format_memory_profile_output(profile_output):
    lines = profile_output.split('\n')
    formatted_lines = []

    for line in lines:
        match = re.match(r'\s*(\d+)\s+(\d+\.\d+)\s+(\d+\.\d+)\s+(\d+)\s+(.+)', line)
        if match:
            formatted_lines.append(f"{match.group(1):>5} {match.group(2):>10} {match.group(3):>10} {match.group(4):>12} {match.group(5)}")

    return '\n'.join(formatted_lines)

# 重新运行脚本并格式化输出 memory_profiler 的结果
if __name__ == "__main__":
    from io import StringIO

    # 使用 StringIO 捕获 print 的输出
    output_buffer = StringIO()
    profile(print_stats=output_buffer)(bfs)(maze, start, end)

    # 获取捕获的输出，并进行格式化
    formatted_output = format_memory_profile_output(output_buffer.getvalue())

    # 打印格式化后的输出
    print("Formatted Memory Profile Output:")
    print(formatted_output)

DFS

import time
from memory_profiler import profile

@profile
def dfs(maze, start, end):
    stack = [(start, [start])]
    visited = set()

    while stack:
        current, path = stack.pop()

        if current == end:
            return path

        if current in visited:
            continue

        visited.add(current)

        neighbors = get_neighbors(maze, current)
        if neighbors is not None:
            for neighbor in neighbors:
                stack.append((neighbor, path + [neighbor]))

    return []


def get_neighbors(maze, current):
    row, col = current
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右、左、下、上

    neighbors = []
    for dr, dc in directions:
        nr, nc = row + dr, col + dc
        if 0 <= nr < len(maze) and 0 <= nc < len(maze[0]) and maze[nr][nc] == 0:
            neighbors.append((nr, nc))

    return neighbors


def create_path_matrix(maze, path):
    path_matrix = [[maze[row][col] if (row, col) not in path else 'P' for col in range(len(maze[0]))] for row in range(len(maze))]
    return path_matrix

    return path_matrix

if __name__ == "__main__":
    maze = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],

]



    start = (0, 0)
    end = (len(maze) - 1, len(maze[0]) - 1)

    start_time = time.time()
    result = dfs(maze, start, end)
    end_time = time.time()

    if result:
        path_matrix = create_path_matrix(maze, result)
        print("DFS Result: Path found")
        for row in path_matrix:
            print(' '.join(map(str, row)))
    else:
        print("DFS Result: No path found")

    print(f"DFS Time: {end_time - start_time} seconds")