人工智能实验（四）-A*算法求解迷宫寻路问题实验

零、A*算法学习参考资料

1.讲解视频

A*寻路算法详解 #A星 #启发式搜索_哔哩哔哩_bilibili

2.A*算法学习网站

A* 算法简介

一、实验目的

熟悉和掌握A*算法实现迷宫寻路功能，要求掌握启发式函数的编写以及各类启发式函数效果的比较。

二、实验要求

同课本 附录B 实验指导书 实验五的指导要求和实验报告要求：

1.画出用A*算法求解迷宫最短路径的流程图。

2.设置不同的地图，以及不同的初始状态和目标状态，记录A*算法的求解结果，包括最短路径、扩展节点数、生成结点数和算法运行时间。

3.对于相同的初始状态和目标状态，设计不同的启发式函数，比较不同启发式函数对迷宫寻路速度的提升效果，包括扩展节点数、生成结点数和算法运行时间。

实验内容

迷宫问题是在以方格表示的地图场景中，对于给定的起点、终点和障碍物，如何找到一条从起点开始避开障碍物到达终点的最短路径。 假设在一个n*m的迷宫里，入口坐标和出口坐标分别为(1,1)和(5,5)，每一个坐标点有两种可能：0和1，其中0表示该位置允许通过，1表示该位置不允许通过。

三、实验材料

A*算法的基本原理：

A*算法在搜索过程中，考虑了每个节点到起点的实际代价（g(n)）和从该节点到目标的估算代价（h(n)）。它使用以下公式来计算每个节点的评估代价：

f(n)=g(n)+h(n)

g(n)：从起点到节点n的实际代价，通常是路径长度或其他度量。

h(n)：从节点n到目标节点的估算代价，通常通过启发式方法来计算。常见的启发式函数包括曼哈顿距离、欧几里得距离等。

f(n)：节点n的总代价，它是g(n)和h(n)的和。A*算法会优先选择具有最小f值的节点进行扩展。

A*算法的步骤：

1. 初始化：将起点加入开放列表（Open List），并设置其g和h值。起点的f值为g + h。

2. 循环搜索：

3. 目标找到：当目标节点被加入闭合列表时，路径搜索结束。此时，可以从目标节点回溯到起点，得到最短路径。

4. 结束：如果开放列表为空，表示没有路径可达目标。

特点：

启发式：A*算法通过启发式函数来引导搜索过程，使得搜索在达到目标时更为高效。

最优性：只要启发式函数是可接受的（即不高估到目标的代价），A*算法可以保证找到最短路径。可接受的启发式函数通常需要满足一致性或单调性条件。

启发式函数的选择：

启发式函数h(n)的选择对A*算法的性能和效率有重要影响。常见的启发式函数包括：

曼哈顿距离：适用于格子状地图，只能横向或纵向移动。

欧几里得距离：适用于平面上的直线距离。

四、实验步骤

1.画出A*算法求解迷宫最短路径问题的流程图。

2.分析不同启发式函数h(n)对迷宫寻路求解的速度提升效果。

3.分析A*算法求解不同规模迷宫最短路径问题的性能。

4.提交源程序。

5.总结实验心得体会。

五、思考与问答

问：A*算法如何处理迷宫中的障碍物？

答：在A*算法中，每次扩展节点时，都需要检查其邻居节点是否为障碍物。如果邻居是障碍物，算法就会跳过这个邻居，不将其加入开放列表。障碍物被认为是无法通过的区域，因此它们在路径搜索过程中是不可达的。

问：A*算法保证找到最短路径吗？

答：是的，只要启发式函数是“可接受的”，即不高估从当前节点到目标节点的实际代价，A算法就能保证找到最短路径。对于迷宫问题，常见的启发式函数（如曼哈顿距离、欧几里得距离等）是可接受的，因此A可以找到从起点到终点的最短路径。

问：A*算法的效率如何？如何应对大规模迷宫？

答：A算法的效率取决于迷宫的复杂度和启发式函数的设计。在大规模迷宫中，A算法的时间复杂度和空间复杂度可能很高，因为需要维护开放列表和闭合列表。在这种情况下，可以采取以下优化策略：

- 启发式函数优化：选择合适的启发式函数，如曼哈顿距离、欧几里得距离等，以缩小搜索范围。

- 迭代加深A*（IDA*）：通过限制搜索深度，减少内存消耗。

- 跳跃搜索：在某些情况下，通过跳过某些中间步骤，减少计算量。

六、源代码

'''from queue import PriorityQueue

def a_star_search(graph,start,goal):
    """
    使用 A* 搜索算法在图中寻找从起点到终点的路径。

    参数:
        graph (Graph): 要搜索的图。
        start: 搜索的起点。
        goal: 搜索的终点。

    返回:
        tuple: 包含came_from和cost_so_far的元组。
            came_from (dict): 一个字典，存储了每个节点的前一个节点，用于回溯路径。
            cost_so_far (dict): 一个字典，存储了到每个节点的当前最小代价。
    """
    # 使用优先级队列 frontier 来存储待探索的节点，优先级由估计的总代价决定
    frontier = PriorityQueue()
    # 将起点 start 放入 frontier 中，其优先级为 0
    frontier.put(start, 0)

    # 创建 came_from 字典，用于记录每个节点的前一个节点
    came_from = dict()
    # 创建 cost_so_far 字典，用于记录到每个节点的当前最小代价
    cost_so_far = dict()

    # 将起点 start 的前一个节点设置为 None，并将其代价设置为 0
    came_from[start] = None
    cost_so_far[start] = 0

    # 当 frontier 不为空时，循环执行以下操作
    while not frontier.empty():
        # 从 frontier 中取出具有最小代价的节点 current
        current = frontier.get()

        # 如果 current 节点等于目标节点 goal，则搜索结束
        if current == goal:
            break

        # 遍历 current 节点的所有邻居节点 next
        for next in graph.neighbors(current):
            # 计算从起点到 next 节点的新代价 new_cost
            new_cost = cost_so_far[current] + graph.cost(current, next)
            # 如果 next 节点没有被访问过，或者通过 current 节点到达 next 节点的代价更小
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                # 更新到 next 节点的代价为 new_cost
                cost_so_far[next] = new_cost
                # 计算从起点到 next 节点的估计总代价 priority
                priority = new_cost + heuristic(goal, next)
                # 将 next 节点及其估计总代价 priority 放入 frontier 中
                frontier.put(next, priority)
                # 将 next 节点的前一个节点设置为 current
                came_from[next] = current

    # 返回 came_from 和 cost_so_far 字典，用于回溯路径和计算总代价
    return came_from, cost_so_far


def heuristic(a, b):
    """
    计算两个点 a 和 b 之间的曼哈顿距离。

    参数:
        a (tuple): 第一个点的坐标，格式为 (x1, y1)。
        b (tuple): 第二个点的坐标，格式为 (x2, y2)。

    返回:
        int: 两点之间的曼哈顿距离。
    """
    # 解包元组 a 得到 x1 和 y1
    (x1, y1) = a
    # 解包元组 b 得到 x2 和 y2
    (x2, y2) = b
    # 计算 x 坐标之差的绝对值
    x_diff = abs(x1 - x2)
    # 计算 y 坐标之差的绝对值
    y_diff = abs(y1 - y2)
    # 返回曼哈顿距离，即 x 和 y 坐标之差的绝对值之和
    return x_diff + y_diff


'''
# A* 算法代码

from queue import PriorityQueue
import time
import math

class MazeGraph:
    """
    迷宫图的表示类，包含迷宫的行列数据，以及获取邻居节点和路径代价的方法。
    """

    def __init__(self, maze):
        """
        初始化 MazeGraph 对象。

        参数:
            maze (list of lists): 二维列表，代表迷宫的布局。

        返回:
            None
        """
        # 将传入的迷宫赋值给实例变量 self.maze
        self.maze = maze
        # 获取迷宫的行数，并赋值给实例变量 self.rows
        self.rows = len(maze)
        # 获取迷宫的列数，并赋值给实例变量 self.cols
        self.cols = len(maze[0])


    def neighbors(self, node):
        """返回当前节点的所有邻居节点"""
        # 获取节点的 x 和 y 坐标
        x, y = node
        # 初始化邻居节点列表
        neighbors = []
        # 定义四个方向的偏移量：左、右、上、下
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        # 遍历每个方向
        for dx, dy in directions:
            # 计算邻居节点的坐标
            nx, ny = x + dx, y + dy
            # 检查邻居节点是否在迷宫范围内，并且不是墙壁（值为 0）
            if 0 <= nx < self.rows and 0 <= ny < self.cols and self.maze[nx][ny] == 0:
                # 如果是有效邻居节点，则将其添加到列表中
                neighbors.append((nx, ny))
        # 返回所有有效的邻居节点
        return neighbors


    def cost(self, from_node, to_node):
        """
        返回从 from_node 到 to_node 的路径代价，这里代价为 1（单位代价）

        参数:
            from_node (tuple): 起点坐标。
            to_node (tuple): 终点坐标。

        解释：
            行走每一个格子的代价为 1（单位代价）
        """
        return 1



def a_star_search(graph, start, goal):
    """
    使用 A* 搜索算法在图中寻找从起点到终点的路径。

    参数:
        graph (MazeGraph): 迷宫图对象。
        start: 搜索的起点。
        goal: 搜索的终点。

    返回:
        tuple: 包含came_from和cost_so_far的元组。
            came_from (dict): 一个字典，存储了每个节点的前一个节点，用于回溯路径。
            cost_so_far (dict): 一个字典，存储了到每个节点的当前最小代价。
    """
    # 使用优先级队列 frontier 来存储待探索的节点，优先级由估计的总代价决定
    frontier = PriorityQueue()
    frontier.put((0, start))  # 将起点 start 放入 frontier 中，其优先级为 0

    # 创建 came_from 字典，用于记录每个节点的前一个节点
    came_from = dict()
    # 创建 cost_so_far 字典，用于记录到每个节点的当前最小代价
    cost_so_far = dict()

    # 将起点 start 的前一个节点设置为 None，并将其代价设置为 0
    came_from[start] = None
    cost_so_far[start] = 0

    # 记录扩展节点数和生成节点数
    expand_count = 0
    generate_count = 0

    # 记录起始时间
    start_time = time.time()

    while not frontier.empty():
        current_cost, current = frontier.get()
        expand_count += 1   # 扩展节点数加一

        # 如果 current 节点等于目标节点 goal，则搜索结束
        if current == goal:
            break

        # 遍历 current 节点的所有邻居节点 next
        for next in graph.neighbors(current):
            # 计算从起点到 next 节点的新代价 new_cost
            new_cost = cost_so_far[current] + graph.cost(current, next)
            # 如果 next 节点没有被访问过，或者通过 current 节点到达 next 节点的代价更小
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                # 更新到 next 节点的代价为 new_cost
                cost_so_far[next] = new_cost

                # 在这选择估价曼哈顿算法
                # heuristic = heuristic_manhattan(next, goal)

                # 在这选择估价欧几里得算法
                heuristic = heuristic_euclidean(next, goal)

                priority = new_cost + heuristic  # fn = gn + hn


                # 将 next 节点及其估计总代价 priority 放入 frontier 中
                frontier.put((priority, next))
                # 将当前结点更新在came_from中
                came_from[next] = current
                generate_count += 1 # 生成节点数

    # 计算运行时间
    end_time = time.time()
    execution_time = end_time - start_time

    return came_from, cost_so_far, expand_count, generate_count, execution_time


def heuristic_manhattan(a, b):
    """
    计算两个点 a 和 b 之间的曼哈顿距离。

    参数:
        a (tuple): 第一个点的坐标，格式为 (x1, y1)。
        b (tuple): 第二个点的坐标，格式为 (x2, y2)。

    返回:
        int: 两点之间的曼哈顿距离。
    """
    (x1, y1) = a
    (x2, y2) = b
    return abs(x1 - x2) + abs(y1 - y2)



def heuristic_euclidean(a, b):
    """
    计算两个点 a 和 b 之间的欧几里得距离。

    参数:
        a (tuple): 第一个点的坐标，格式为 (x1, y1)。
        b (tuple): 第二个点的坐标，格式为 (x2, y2)。

    返回:
        float: 两点之间的欧几里得距离。
    """
    (x1, y1) = a
    (x2, y2) = b
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)





def reconstruct_path(came_from, start, goal):
    """
    从 came_from 字典中回溯路径。

    参数:
        came_from (dict): 包含每个节点的前一个节点的字典。
        start: 起点。
        goal: 终点。

    返回:
        list: 从 start 到 goal 的路径。
    """
    # 初始化路径列表
    path = []
    # 将当前节点设置为终点
    current = goal
    # 当当前节点不等于起点时，循环执行以下操作
    while current!= start:
        # 将当前节点添加到路径中
        path.append(current)
        # 从 came_from 字典中获取当前节点的前一个节点，并更新当前节点
        current = came_from[current]
    # 将起点添加到路径中
    path.append(start)
    # 反转路径，使其从起点到终点
    path.reverse()
    # 返回重构的路径
    return path



def print_map(maze):
    """
    打印迷宫地图。

    参数:
        maze (list of lists): 二维列表，代表迷宫的布局。

    返回:
        None
    """
    # 遍历迷宫的每一行
    for row in maze:
        # 使用 join 方法将每一行的单元格值连接成一个字符串，单元格之间用空格分隔
        print(" ".join(str(cell) for cell in row))


def mark_path_on_map(maze, path):
    """
    在迷宫中标记路径，使用字母 A, B, C 等。

    参数:
        maze (list of lists): 二维列表，代表迷宫的布局。
        path (list of tuples): 路径上的点的列表，每个点是一个 (x, y) 坐标对。

    返回:
        list of lists: 修改后的迷宫地图，其中路径上的点被标记为字母。
    """
    # 初始化字母为 'A'
    letter = 'A'
    # 遍历路径上的每个点
    for (x, y) in path:
        # 包括起点和终点
        maze[x][y] = letter
        # 更新字母到下一个
        letter = chr(ord(letter) + 1)
    # 返回标记路径后的迷宫地图
    return maze

import random

def generate_maze(rows, cols, obstacle_probability=0.3):
    # 初始化迷宫地图，所有单元格默认为可通行（0）
    maze = [[0 for _ in range(cols)] for _ in range(rows)]

    # 定义起点和终点
    start = (0, 0)
    end = (rows - 1, cols - 1)

    # 使用深度优先搜索生成从起点到终点的路径
    def dfs(x, y):
        stack = [(x, y)]
        visited = set()
        visited.add((x, y))
        while stack:
            cx, cy = stack.pop()
            # 随机打乱邻居顺序
            neighbors = [(cx + dx, cy + dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]]
            random.shuffle(neighbors)
            for nx, ny in neighbors:
                if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in visited:
                    if (nx, ny) == end or dfs(nx, ny):
                        maze[cx][cy] = 0
                        maze[nx][ny] = 0
                        return True
        return False

    # 生成路径
    dfs(*start)

    # 随机生成障碍物
    for i in range(rows):
        for j in range(cols):
            if (i, j) != start and (i, j) != end and maze[i][j] == 0:
                if random.random() < obstacle_probability:
                    maze[i][j] = 1

    return maze

def main():

    '''    # 定义迷宫地图，0 表示可通行，1 表示障碍物
    maze = [
        [0, 0, 0, 0, 0],
        [1, 0, 1, 0, 1],
        [0, 0, 1, 1, 1],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0]
    ]'''

    '''
    # 测试样例1：无解
    maze = [
    [0, 0, 0, 0, 0],
    [1, 1, 1, 0, 1],
    [0, 1, 1, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0]
]
'''

    '''
    # 测试样例2：
    maze = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]
'''
    '''
    # 测试样例3：
    maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
]
    
    '''
    maze = generate_maze(10, 10)

    # 设置起点和终点坐标
    start = (0, 0)  # 起点 (1,1)
    end = (9, 9)  # 终点 (5,5)

    # 创建迷宫图对象
    graph = MazeGraph(maze)

    # 调用 A* 搜索算法，返回 came_from 字典和 cost_so_far 字典
    came_from, cost_so_far, expand_count, generate_count, execution_time = a_star_search(graph, start, end)

    # 如果找到路径
    if end in came_from:
        # 重构路径
        path = reconstruct_path(came_from, start, end)
        # 打印最短路径
        print("最短路径: ", [f"({p[0] + 1},{p[1] + 1})" for p in path])

        # 在迷宫地图上标记路径
        marked_maze = mark_path_on_map([row[:] for row in maze], path)
        # 打印带路径标记的迷宫地图
        print("迷宫地图带路径标记：")
        print_map(marked_maze)

        # 输出扩展节点数、生成节点数、算法运行时间
        print(f"扩展节点数: {expand_count}")
        print(f"生成节点数: {generate_count}")
        print(f"算法运行时间: {execution_time:.30f} 秒")
    else:
        # 如果没有找到路径，打印提示信息
        print("没有找到路径")




if __name__ == "__main__":
    main()

七、结果