路径规划 | 图解A*、Dijkstra、GBFS算法的异同(附C++/Python/Matlab仿真)

路径规划是人工智能领域的一个重要问题，尤其在机器人导航、游戏开发和网络路由等应用场景中，寻找最优路径具有极大的意义。在众多路径规划算法中，A*、Dijkstra和贪婪最佳优先搜索（GBFS）是最经典的三种算法。下面将对它们的原理、优缺点以及代码示例进行详细的分析。

1. Dijkstra算法

原理： Dijkstra算法是一种广度优先的搜索策略，适用于求解加权图中单源最短路径的问题。它从起点开始，以最小的路径代价逐步扩展到其它节点，直到达到终点。

优缺点： - 优点：可以处理带权图，保证找到最优路径。 - 缺点：当图较大时，时间复杂度为O(V²)（使用邻接矩阵时），在稀疏图中，利用优先队列可以优化到O((V + E) log V)，效率较低。

代码示例（Python）：

import heapq

def dijkstra(graph, start):
    queue = []
    heapq.heappush(queue, (0, start))  # (cost, node)
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    while queue:
        current_distance, current_vertex = heapq.heappop(queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# 示例图定义
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))

2. A* 算法

原理： A*算法结合了Dijkstra算法的全局搜索和GBFS的启发式搜索，使用启发式函数（如曼哈顿距离或欧几里得距离）来评估从起点到终点的潜在距离。每次选择f(n) = g(n) + h(n)最小的节点进行扩展，其中g(n)是起点到当前节点的确切代价，h(n)是当前节点到目标节点的估计代价。

优缺点： - 优点：兼具Dijkstra和GBFS的优点，通常比Dijkstra更快。 - 缺点：需要选择一个合适的启发式函数，若选择不当可能会导致性能降低。

代码示例（Python）：

def a_star(graph, start, goal, h):
    open_set = {start}
    came_from = {}
    g_score = {node: float('infinity') for node in graph}
    g_score[start] = 0
    f_score = {node: float('infinity') for node in graph}
    f_score[start] = h(start, goal)

    while open_set:
        current = min(open_set, key=lambda node: f_score[node])

        if current == goal:
            return reconstruct_path(came_from, current)

        open_set.remove(current)

        for neighbor, weight in graph[current].items():
            tentative_g_score = g_score[current] + weight

            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + h(neighbor, goal)
                open_set.add(neighbor)

    return False

def reconstruct_path(came_from, current):
    total_path = [current]
    while current in came_from:
        current = came_from[current]
        total_path.append(current)
    return total_path[::-1]

# 启发式函数
def heuristic(a, b):
    return abs(ord(a) - ord(b))  # 简单的启发式函数，用字母的差值

print(a_star(graph, 'A', 'D', heuristic))

3. 贪婪最佳优先搜索（GBFS）

原理： GBFS只考虑启发式函数h(n)，在每一轮中选择当前预计最接近目标的节点进行扩展，忽略已走过的路径代价。

优缺点： - 优点：简单且通常速度快。 - 缺点：不保证找到最优路径，可能陷入局部最优。

代码示例（Python）：

def gbfs(graph, start, goal, h):
    open_set = {start}
    came_from = {}

    while open_set:
        current = min(open_set, key=lambda node: h(node, goal))

        if current == goal:
            return reconstruct_path(came_from, current)

        open_set.remove(current)

        for neighbor in graph[current].keys():
            if neighbor not in came_from:  # 避免重复访问
                came_from[neighbor] = current
                open_set.add(neighbor)

    return False

print(gbfs(graph, 'A', 'D', heuristic))

总结

• Dijkstra算法适合解单源最短路径问题，确保最优解，但效率较低。
• A*算法在Dijkstra的基础上引入了启发式函数，提高了搜索效率，能找到最优解。
• GBFS是一种快速的搜索算法，但不保证最优性，只依赖启发式函数进行搜索。

这三种算法各有特点，选择合适的算法需结合具体问题的特点与需求。在实际应用中，路径规划问题往往涉及大量的数据与复杂的环境，因此对算法进行优化与改进也是研究的热点。