1
A* 算法是一种启发式搜索算法，常用于在图中寻找从起始节点到目标节点的最短路径。它结合了 Dijkstra 算法（保证能找到最优解的广度优先搜索拓展）的特点以及启发式函数来引导搜索方向，以减少搜索空间。
2
算法维护两个集合，一个是已探索的节点集合，另一个是待探索的节点集合（通常用优先队列实现，按照节点的评估函数值排序）。每个节点都有一个评估函数 `f(n)`，它由两部分组成：从起始节点到当前节点 `n` 的实际代价 `g(n)`（类似 Dijkstra 算法中的距离度量），以及从当前节点 `n` 到目标节点的预估代价 `h(n)`（启发式函数），即 `f(n) = g(n) + h(n)`。
3
在搜索过程中，每次从待探索集合中取出 `f(n)` 值最小的节点进行扩展，直到找到目标节点或者待探索集合为空。启发式函数 `h(n)` 需要满足一定的条件（可采纳性，即 `h(n)` 始终小于等于节点 `n` 到目标节点的实际最短距离），这样才能保证 A* 算法最终找到的是最优解。

1
```python
2

3
import heapq
4

5
# 定义四个方向的移动向量（上下左右）
6
dx = [-1, 1, 0, 0]
7
dy = [0, 0, -1, 1]
8

9
def heuristic(a, b):
10
    """
11
    启发式函数，这里使用曼哈顿距离（在二维网格中常用），计算两点之间的预估距离
12
    """
13
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
14

15
def a_star(grid, start, goal):
16
    """
17
    A* 算法实现
18
    """
19
    rows = len(grid)
20
    cols = len(grid[0])
21
    # 初始化 g 值，初始设为无穷大
22
    g_scores = [[float('inf')] * cols for _ in range(rows)]
23
    g_scores[start[0]][start[1]] = 0
24
    # 初始化 f 值，初始设为无穷大
25
    f_scores = [[float('inf')] * cols for _ in range(rows)]
26
    f_scores[start[0]][start[1]] = heuristic(start, goal)
27
    # 优先队列，存储待探索的节点，元素为 (f值, (x坐标, y坐标))
28
    open_set = [(f_scores[start[0]][start[1]], start)]
29
    came_from = {}
30
    while open_set:
31
        _, current = heapq.heappop(open_set)
32
        if current == goal:
33
            path = []
34
            while current in came_from:
35
                path.append(current)
36
                current = came_from[current]
37
            path.append(start)
38
            return path[::-1]
39
        for i in range(4):
40
            new_x = current[0] + dx[i]
41
            new_y = current[1] + dy[i]
42
            if 0 <= new_x < rows and 0 <= new_y < cols and grid[new_x][new_y] == 0:
43
                tentative_g_score = g_scores[current[0]][current[1]] + 1
44
                if tentative_g_score < g_scores[new_x][new_y]:
45
                    came_from[(new_x, new_y)] = current
46
                    g_scores[new_x][new_y] = tentative_g_score
47
                    f_scores[new_x][new_y] = tentative_g_score + heuristic((new_x, new_y), goal)
48
                    heapq.heappush(open_set, (f_scores[new_x][new_y], (new_x, new_y)))
49
    return None
50
```

1
```python
2

3
# 示例地图
4
grid = [
5
    [0, 0, 0, 0],
6
    [0, 1, 0, 0],
7
    [0, 0, 0, 0],
8
    [0, 0, 0, 0]
9
]
10
start = (0, 0)
11
goal = (3, 3)
12
path = a_star(grid, start, goal)
13
print(path)
14

15
```