AI人工智能T迷宫：从零构建路径规划算法的实战指南

1次阅读

没有评论

共计 3994 个字符，预计需要花费 10 分钟才能阅读完成。

刚开始接触迷宫问题时，我尝试用暴力搜索方法（比如随机走）来解决。但在 10×10 以上的迷宫就遇到严重性能问题——程序经常陷入死循环，或者要花几分钟才能找到出口。这是因为暴力搜索没有方向性，就像在陌生城市没有地图乱闯。

传统方法的瓶颈主要体现在：

时间复杂度高 ：最坏情况下要遍历所有可能的路径
内存消耗大 ：需要保存大量中间状态
缺乏智能性 ：无法利用已知信息做决策

这促使我研究更高效的路径规划算法。通过实践对比，发现 DFS 和 A * 这两种算法最适合初学者入门，既能理解基础原理，又能看到明显的性能差异。

先整理四种常见算法的特性对比：

算法	时间复杂度	空间复杂度	是否最优解	适用场景
DFS	O(b^m)	O(bm)	否	快速验证路径存在性
BFS	O(b^d)	O(b^d)	是	找最短路径（无权图）
Dijkstra	O((V+E)logV)	O(V)	是	带权图中的最短路径
A*	O(b^d)	O(b^d)	是 *	有启发信息的路径搜索

（注：b- 分支因子，d- 解深度，m- 最大深度，V- 顶点数，E- 边数；* 需启发函数可采纳）

先用 Python 实现可配置的迷宫生成，核心是用随机深度优先搜索构建：

import numpy as np
def generate_maze(width=10, height=10, obstacle_density=0.2):
    """
    生成随机迷宫
    :param width: 迷宫宽度
    :param height: 迷宫高度
    :param obstacle_density: 障碍物密度 (0~1)
    :return: 二维数组表示的迷宫 (0- 路，1- 墙)
    """
    maze = np.zeros((height, width))
    # 设置外围墙
    maze[0, :] = maze[-1, :] = 1
    maze[:, 0] = maze[:, -1] = 1
    # 随机障碍物
    mask = np.random.random((height-2, width-2)) < obstacle_density
    maze[1:-1, 1:-1] = mask.astype(int)
    # 确保起点和终点畅通
    maze[1,1] = 0
    maze[-2,-2] = 0
    return maze

深度优先搜索像走迷宫时始终右手扶墙的策略：

def dfs(maze, start=(1,1), end=None):
    """
    DFS 路径搜索
    :param maze: 迷宫矩阵
    :param start: 起点坐标
    :param end: 终点坐标
    :return: 路径坐标列表
    """
    if not end:
        end = (len(maze)-2, len(maze[0])-2)  # 默认右下角

    stack = [(start, [start])]
    visited = set()

    while stack:
        (x, y), path = stack.pop()
        if (x, y) in visited:
            continue

        visited.add((x, y))

        # 到达终点
        if (x, y) == end:
            return path

        # 探索四个方向 (上右下左)
        for dx, dy in [(-1,0),(0,1),(1,0),(0,-1)]:
            nx, ny = x + dx, y + dy
            if maze[nx][ny] == 0 and (nx, ny) not in visited:
                stack.append(((nx, ny), path + [(nx, ny)]))

    return None  # 无解

A* 通过启发函数引导搜索方向，这里用曼哈顿距离作为启发式：

def astar(maze, start=(1,1), end=None):
    """
    A* 路径搜索
    :param maze: 迷宫矩阵
    :param start: 起点坐标
    :param end: 终点坐标
    :return: 路径坐标列表
    """
    if not end:
        end = (len(maze)-2, len(maze[0])-2)

    def heuristic(a, b):
        # 曼哈顿距离
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    open_set = {start}
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, end)}

    while open_set:
        current = min(open_set, key=lambda pos: f_score[pos])

        if current == end:
            # 路径回溯
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        open_set.remove(current)

        for dx, dy in [(-1,0),(0,1),(1,0),(0,-1)]:
            neighbor = (current[0] + dx, current[1] + dy)

            # 检查边界和障碍
            if (0 <= neighbor[0] < len(maze) and 
                0 <= neighbor[1] < len(maze[0]) and 
                maze[neighbor[0]][neighbor[1]] == 0):

                tentative_g = g_score[current] + 1

                if (neighbor not in g_score or 
                    tentative_g < g_score[neighbor]):

                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g
                    f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, end)
                    open_set.add(neighbor)

    return None  # 无解

用 Matplotlib 让搜索结果一目了然：

import matplotlib.pyplot as plt
import matplotlib.colors as mcolors

def plot_maze(maze, path=None, explored=None):
    """
    可视化迷宫和路径
    :param maze: 迷宫矩阵
    :param path: 最终路径
    :param explored: 已探索区域
    """cmap = mcolors.ListedColormap(['white','black','red','green','blue'])
    plot_maze = maze.copy()

    if explored:
        for pos in explored:
            if plot_maze[pos[0]][pos[1]] == 0:
                plot_maze[pos[0]][pos[1]] = 2  # 已探索

    if path:
        for pos in path:
            plot_maze[pos[0]][pos[1]] = 3  # 路径

    # 标记起点和终点
    plot_maze[1][1] = 4
    plot_maze[-2][-2] = 4

    plt.figure(figsize=(8, 8))
    plt.imshow(plot_maze, cmap=cmap, norm=mcolors.BoundaryNorm([-0.5,0.5,1.5,2.5,3.5,4.5], cmap.N))
    plt.xticks([])
    plt.yticks([])
    plt.show()

在 10×10 到 100×100 的迷宫上测试两种算法：

import time

sizes = range(10, 101, 10)
dfs_times = []
astar_times = []

for size in sizes:
    maze = generate_maze(size, size, 0.2)

    start_time = time.time()
    dfs(maze)
    dfs_times.append(time.time() - start_time)

    start_time = time.time()
    astar(maze)
    astar_times.append(time.time() - start_time)

绘制执行时间对比图：

plt.plot(sizes, dfs_times, label='DFS')
plt.plot(sizes, astar_times, label='A*')
plt.xlabel('Maze Size')
plt.ylabel('Execution Time (s)')
plt.title('Algorithm Performance Comparison')
plt.legend()
plt.grid()
plt.show()

在 DFS 中如果不记录已访问节点，环形迷宫会导致无限循环。解决方案：

使用集合存储 visited 节点
限制最大递归深度

A* 的性能高度依赖启发函数：

曼哈顿距离：适合只能四方向移动
欧式距离：适合可斜向移动
对角线距离：平衡上述两种情况

调整启发函数权重（加权 A *）：

def heuristic(a, b, w=1.0):
    return w * (abs(a[0]-b[0]) + abs(a[1]-b[1]))

对于大型迷宫：

使用优先队列替代普通队列
实现二叉堆优化
考虑迭代深化 DFS（IDDFS）

三维迷宫 ：扩展坐标到 (x,y,z)，启发函数改用 3D 距离
动态障碍 ：实现 D * Lite 等增量搜索算法
多智能体 ：引入冲突检测和路径重规划

维度	DFS	A*
路径质量	不一定最短	保证最短路径
时间复杂度	较高	较低
内存使用	线性	较高
适用场景	简单迷宫 / 快速验证	复杂迷宫 / 需要最优解