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

1次阅读

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

Y 迷宫看起来简单，但它有几个特点让路径规划变得棘手。首先是那个分叉点——你得决定往左还是往右走。更麻烦的是，如果算法没设计好，可能会在岔路口来回转圈，永远找不到出口。

传统暴力搜索（比如随意尝试所有方向）在这种结构下特别容易卡住。我就吃过亏——曾经写了个算法在 10×10 的迷宫里转了 2000 多步还没找到出口，其实出口就在起点旁边！

先看三种常用算法的核心区别：

算法	时间复杂度	空间复杂度	是否最优解	适用场景
BFS	O(b^d)	O(b^d)	是	最短路径
DFS	O(b^m)	O(bm)	否	内存有限
A*	O(b^d)	O(b^d)	是	有启发信息

注：b 是分支因子，d 是解深度，m 是最大深度

我们先构建迷宫的基础表示。用二维数组最直观，0 表示通路，1 表示墙壁：

# 典型的 Y 迷宫结构示例
maze = [[0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
start = (0, 0)
goal = (4, 4)

宽度优先搜索就像水波纹扩散，保证找到最短路径：

from collections import deque

def bfs(maze, start, goal):
    queue = deque([start])
    visited = set([start])
    parent = {}

    while queue:
        current = queue.popleft()

        if current == goal:
            path = []
            while current in parent:
                path.append(current)
                current = parent[current]
            return path[::-1]

        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            x, y = current[0] + dx, current[1] + dy
            if (0 <= x < len(maze) and 0 <= y < len(maze[0]) 
                and maze[x][y] == 0 and (x,y) not in visited):
                visited.add((x,y))
                parent[(x,y)] = current
                queue.append((x,y))
    return None

深度优先搜索像走迷宫时用手摸着墙走，可能绕远路但内存消耗少：

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

    while stack:
        (x, y), path = stack.pop()

        if (x,y) == goal:
            return path

        if len(path) >= max_depth:  # 防止无限递归
            continue

        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx, ny = x + dx, y + dy
            if (0 <= nx < len(maze) and 0 <= ny < len(maze[0]) 
                and maze[nx][ny] == 0 and (nx,ny) not in visited):
                visited.add((nx,ny))
                stack.append(((nx,ny), path + [(nx,ny)]))
    return None

A* 结合了 BFS 和启发式思想，用预估成本指导搜索方向：

import heapq

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

def astar(maze, start, goal):
    open_set = []
    heapq.heappush(open_set, (0 + heuristic(start, goal), start))
    came_from = {}
    g_score = {start: 0}

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]

        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            x, y = current[0] + dx, current[1] + dy
            if not (0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0):
                continue

            tentative_g = g_score[current] + 1
            if (x,y) not in g_score or tentative_g < g_score[(x,y)]:
                came_from[(x,y)] = current
                g_score[(x,y)] = tentative_g
                f_score = tentative_g + heuristic((x,y), goal)
                heapq.heappush(open_set, (f_score, (x,y)))
    return None

我在三种迷宫规模下测试了各算法的表现（单位：秒）：