Python A* 算法寻找最短路径并计时

以下是使用 Python 编写的 A* 算法来找到最短路径并计时的示例代码：

import heapq
import time

class Node:
    def __init__(self, position, parent=None):
        self.position = position
        self.parent = parent
        self.g = 0  # 初始 g 值为 0
        self.h = 0  # 初始 h 值为 0
        self.f = 0  # 初始 f 值为 0

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

def h_score(position, target):
    return abs(target[0] - position[0]) + abs(target[1] - position[1])

def get_neighbors(position, grid_size):
    neighbors = []
    row, col = position
    if row > 0:
        neighbors.append((row-1, col))
    if row < grid_size-1:
        neighbors.append((row+1, col))
    if col > 0:
        neighbors.append((row, col-1))
    if col < grid_size-1:
        neighbors.append((row, col+1))
    return neighbors

def a_star(grid, start, target):
    grid_size = len(grid)
    open_list = []
    closed_set = set()

    start_node = Node(start)
    target_node = Node(target)
    heapq.heappush(open_list, start_node)

    start_time = time.time()

    while open_list:
        current_node = heapq.heappop(open_list)
        closed_set.add(current_node.position)

        if current_node.position == target_node.position:
            path = []
            while current_node:
                path.append(current_node.position)
                current_node = current_node.parent
            path.reverse()
            end_time = time.time()
            return path, end_time - start_time

        neighbors = get_neighbors(current_node.position, grid_size)
        for neighbor in neighbors:
            if grid[neighbor[0]][neighbor[1]] == 1 or neighbor in closed_set:
                continue

            neighbor_node = Node(neighbor, current_node)
            neighbor_node.g = current_node.g + 1
            neighbor_node.h = h_score(neighbor, target)
            neighbor_node.f = neighbor_node.g + neighbor_node.h

            heapq.heappush(open_list, neighbor_node)

    end_time = time.time()
    return None, end_time - start_time

# 示例：定义一个 5x5 的迷宫，1 表示墙，0 表示可行走的路径
grid = [
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [1, 1, 0, 1, 0],
    [1, 0, 0, 0, 0],
    [0, 1, 0, 1, 0]
]

start = (0, 0)
target = (4, 4)

path, time_taken = a_star(grid, start, target)

if path:
    print('最短路径：', path)
    print('找到路径所用时间（秒）：', time_taken)
else:
    print('未找到路径。')

上述代码示例定义了一个 5x5 的迷宫，使用 A* 算法找到从起点 (0, 0) 到终点 (4, 4) 的最短路径，并输出路径及找到路径所用时间。你可以根据需要自定义迷宫的大小、起点和终点位置。