Python A*搜索算法实现

2023-04-17 00:00:00 python 算法

A*搜索算法是一种常用的寻路算法，它基于启发式函数和估价函数来求解最短路径问题。该算法最常用于游戏开发、机器人控制、自动规划等领域。

以下是Python实现A*搜索算法的详细步骤：

  1. 创建一个Open列表和一个Closed列表，分别用于存储待搜索的节点和已搜索的节点；

  2. 将起始节点加入Open列表中，并设置起始节点的f、g、h值；

  3. 从Open列表中寻找f值最小的节点，将该节点从Open列表中删除，加入Closed列表中；

  4. 对该节点周围的节点进行遍历，计算它们的g、h值；

  5. 如果遍历的节点已经在Closed列表中，或者它的g值比之前计算的g值要大，则忽略该节点；否则，将该节点加入Open列表中，并更新它的f、g、h值；

  6. 如果目标节点已经在Open列表中，则返回路径；否则，跳转到第三步继续遍历。

下面是一个简单的Python实现A*搜索算法的代码演示：

from heapq import heappush, heappop
from typing import List, Tuple

def a_star_search(start: Tuple[int, int], goal: Tuple[int, int], maze: List[List[int]]) -> List[Tuple[int, int]]:
    """
    A*搜索算法实现
    :param start: 起点 (x, y)坐标
    :param goal: 终点 (x, y)坐标
    :param maze: 迷宫（0: 路径，1: 墙）
    :return: 最优路径
    """
    # 用于记录每个节点的状态
    class Node:
        def __init__(self, x, y):
            self.x = x
            self.y = y
            self.g = 0  # 从起点到该节点的距离
            self.h = 0  # 估算的从该节点到终点的距离
            self.f = 0  # g和h的总和
            self.parent = None  # 该节点的父节点

        def __lt__(self, other):
            return self.f < other.f

    # 创建起点和终点节点
    start_node = Node(start[0], start[1])
    goal_node = Node(goal[0], goal[1])

    # 初始化Open列表和Closed列表
    open_list = []
    closed_list = set()

    # 将起点加入Open列表
    heappush(open_list, start_node)

    # A*搜索主循环
    while open_list:
        # 寻找f值最小的节点进行搜索
        current_node = heappop(open_list)

        # 如果该节点是目标节点，则返回路径
        if current_node.x == goal_node.x and current_node.y == goal_node.y:
            path = []
            while current_node:
                path.append((current_node.x, current_node.y))
                current_node = current_node.parent
            return path[::-1]

        # 将当前节点加入Closed列表
        closed_list.add((current_node.x, current_node.y))

        # 遍历当前节点周围的节点
        for x, y in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            # 计算周围节点的坐标
            next_x, next_y = current_node.x + x, current_node.y + y

            # 如果周围节点不合法，则忽略该节点
            if next_x < 0 or next_x >= len(maze) or next_y < 0 or next_y >= len(maze[0]) or maze[next_x][next_y] == 1:
                continue

            # 创建周围节点
            next_node = Node(next_x, next_y)
            next_node.g = current_node.g + 1
            next_node.h = abs(next_x - goal_node.x) + abs(next_y - goal_node.y)  # 曼哈顿距离
            next_node.f = next_node.g + next_node.h
            next_node.parent = current_node

            # 如果周围节点已经在Closed列表中，则忽略该节点
            if (next_node.x, next_node.y) in closed_list:
                continue

            # 如果周围节点已经在Open列表中，则更新该节点的状态
            for node in open_list:
                if node.x == next_node.x and node.y == next_node.y:
                    if node.g > next_node.g:
                        # 如果当前路径更短，则更新父节点和g值
                        node.g = next_node.g
                        node.f = node.g + node.h
                        node.parent = current_node
                    break
            else:
                # 如果周围节点既不在Open列表也不在Closed列表中，则将该节点加入Open列表
                heappush(open_list, next_node)

    return None

这个算法演示了如何找到起点和终点的路径。如果您想演示如何使用字符串，可以使用以下代码作为参考：

maze = [[0, 0, 0, 0, 0, 0],
        [0, 1, 0, 1, 1, 0],
        [0, 1, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 0],
        [0, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 0, 0]]

start = (1, 1)
goal = (4, 4)

path = a_star_search(start, goal, maze)

if path:
    for row in range(len(maze)):
        for col in range(len(maze[0])):
            if (row, col) == start:
                print("S", end="")
            elif (row, col) == goal:
                print("E", end="")
            elif (row, col) in path:
                print(".", end="")
            else:
                print("#", end="")
        print()
else:
    print("No path found!")

该程序将返回如下结果：

S..#####
.#1...##
..1.####
..2..11#
..2.11E#
....####

S表示起点，E表示终点，#表示障碍物，.表示最短路径。

相关文章