迷宫自动寻路算法python

迷宫自动寻路算法是一种常见的路径搜索问题解决方案，在Python中可以使用各种算法来解决，如深度优先搜索（Depth First Search, DFS）、广度优先搜索（Breadth First Search, BFS）以及A*算法等。

**深度优先搜索 (DFS)**:
这是一种递归的方式，从起点开始，尽可能深地搜索每个分支，直到找到终点或无法前进为止。在Python中，你可以使用递归函数实现。

def dfs(maze, start, end):
    stack = [start]
    while stack:
        node = stack.pop()
        if node == end:
            return True
        for neighbor in maze[node]:
            stack.append(neighbor)
    return False

**广度优先搜索 (BFS):**
这种方法按照节点的距离逐层遍历，通常用于查找最短路径。Python中可以利用队列数据结构：

from collections import deque

def bfs(maze, start, end):
    queue = deque([start])
    visited = set()
    while queue:
        node = queue.popleft()
        if node == end:
            return True
        if node not in visited:
            visited.add(node)
            for neighbor in maze[node]:
                queue.append(neighbor)
    return False

**A*算法:**
更适用于复杂环境，结合了启发式信息（如曼哈顿距离、欧几里得距离等）。它寻找从起点到目标的最优路径，并考虑到每个节点到目标的实际距离和预计距离。

import heapq

def astar_search(maze, start, end, heuristic):
    frontier = [(0, start)]
    came_from = {}
    cost_so_far = {start: 0}
    
    while frontier:
        _, current = heapq.heappop(frontier)
        
        if current == end:
            break
        
        for next_node in maze.neighbors(current):
            new_cost = cost_so_far[current] + 1
            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                cost_so_far[next_node] = new_cost
                priority = new_cost + heuristic(next_node, end)
                heapq.heappush(frontier, (priority, next_node))
                came_from[next_node] = current
                
    path = []
    while current != start:
        path.append(current)
        current = came_from[current]
    path.append(start)  # 添加起始点
    path.reverse()  # 反转路径顺序
    return path[::-1]  # 返回路径