A* 搜索算法：图形搜索算法的 Python 实现

A* 搜索算法是一种图形搜索算法，用于从给定起点到给定终点计算出最优路径。它使用一种启发式估算来为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A* 搜索算法是最佳优先搜索的范例。

Python 实现

以下是 Python 实现 A* 搜索算法的示例代码：

import heapq

# 定义节点类
class Node:
    def __init__(self, position=None, parent=None, g=0, h=0):
        self.position = position
        self.parent = parent
        self.g = g  # 从起点到当前节点的代价
        self.h = h  # 从当前节点到终点的估计代价
        self.f = self.g + self.h  # f = g + h

    # 定义小于运算符，用于堆排序
    def __lt__(self, other):
        return self.f < other.f

# 定义 A* 搜索函数
def astar_search(start, goal, graph):
    # 初始化起点和终点节点
    start_node = Node(start, None, 0, 0)
    goal_node = Node(goal, None, 0, 0)

    # 初始化 open 和 closed 列表
    open_list = []
    closed_list = []

    # 将起点放入 open 列表
    heapq.heappush(open_list, start_node)

    # 开始搜索
    while len(open_list) > 0:
        # 取出 f 值最小的节点
        current_node = heapq.heappop(open_list)

        # 如果当前节点是终点，则返回路径
        if current_node.position == goal_node.position:
            path = []
            while current_node is not None:
                path.append(current_node.position)
                current_node = current_node.parent
            return path[::-1]

        # 将当前节点加入 closed 列表
        closed_list.append(current_node)

        # 遍历当前节点的邻居
        for neighbor in graph[current_node.position]:
            # 如果邻居已经在 closed 列表中，则跳过
            if any(neighbor.position == node.position for node in closed_list):
                continue

            # 计算从起点到邻居节点的代价
            new_g = current_node.g + neighbor.cost

            # 如果邻居节点不在 open 列表中，则加入
            new_node = Node(neighbor.position, current_node, new_g, 0)
            if any(neighbor.position == node.position for node in open_list):
                node = next(node for node in open_list if neighbor.position == node.position)
                if new_node.g < node.g:
                    node.g = new_node.g
                    node.f = node.g + node.h
                    node.parent = new_node.parent
            else:
                new_node.h = heuristic(neighbor.position, goal_node.position)
                new_node.f = new_node.g + new_node.h
                heapq.heappush(open_list, new_node)

    # 如果 open 列表为空且没有找到路径，则返回空列表
    return []

# 定义启发函数，这里使用曼哈顿距离
def heuristic(a, b):
    return abs(b[0] - a[0]) + abs(b[1] - a[1])

# 定义图形，这里使用二维列表表示
graph = [
    [Node((0, 0), None, 0, 0), Node((0, 1), None, 0, 0), Node((0, 2), None, 0, 0), Node((0, 3), None, 0, 0)],
    [Node((1, 0), None, 0, 0), Node((1, 1), None, 0, 0), Node((1, 2), None, 0, 0), Node((1, 3), None, 0, 0)],
    [Node((2, 0), None, 0, 0), Node((2, 1), None, 0, 0), Node((2, 2), None, 0, 0), Node((2, 3), None, 0, 0)],
    [Node((3, 0), None, 0, 0), Node((3, 1), None, 0, 0), Node((3, 2), None, 0, 0), Node((3, 3), None, 0, 0)]
]

# 设置起点和终点
start = (0, 0)
goal = (3, 3)

# 设置节点代价
graph[0][1].cost = 1
graph[1][0].cost = 1
graph[1][2].cost = 1
graph[2][1].cost = 1
graph[2][3].cost = 1
graph[3][2].cost = 1

# 进行搜索
path = astar_search(start, goal, graph)

# 输出路径
print(path)

代码解释

节点类 Node
- position：节点的位置
- parent：节点的父节点
- g：从起点到当前节点的代价
- h：从当前节点到终点的估计代价
- f：总代价，等于 g + h
A 搜索函数 astar_search*
- 初始化起点和终点节点
- 初始化 open 和 closed 列表，分别用来存储待访问节点和已访问节点
- 将起点加入 open 列表
- 循环访问 open 列表，直到找到终点或 open 列表为空
  - 取出 open 列表中 f 值最小的节点，作为当前节点
  - 如果当前节点是终点，则返回路径
  - 将当前节点加入 closed 列表
  - 遍历当前节点的邻居节点，并判断是否满足以下条件：
    - 邻居节点不在 closed 列表中
    - 计算从起点到邻居节点的代价 new_g
    - 如果邻居节点不在 open 列表中，则加入 open 列表
    - 如果邻居节点已经在 open 列表中，且 new_g 小于其当前 g 值，则更新 open 列表中该节点的 g 值、f 值和父节点
启发函数 heuristic
- 该示例代码使用曼哈顿距离作为启发函数，即两个节点在水平和垂直方向上的距离之和
图形表示
- 该示例代码使用二维列表来表示图形，每个元素代表一个节点
设置节点代价、起点和终点
- 代码中设置了每个节点的代价以及起点和终点
进行搜索和输出路径
- 代码调用 astar_search 函数进行搜索，并输出找到的路径

总结

该代码示例展示了如何使用 Python 实现 A* 搜索算法。通过定义节点类、启发函数和图形表示，并实现搜索函数，我们可以使用 A* 搜索算法来找到图形中从起点到终点的最优路径。A* 搜索算法在路径规划、游戏 AI 等领域都有广泛的应用。