用Python玩转罗马尼亚地图寻路：手把手实现A*、贪婪、BFS、DFS四种算法（附完整代码）

用Python玩转罗马尼亚地图寻路：手把手实现A*、贪婪、BFS、DFS四种算法（附完整代码）

罗马尼亚地图寻路问题是人工智能和算法学习中的经典案例。通过这个项目，我们可以直观地比较不同搜索算法的表现，理解它们的优缺点。本文将带你从零开始，用Python实现四种常见搜索算法：A*、贪婪最佳优先搜索（GBFS）、广度优先搜索（BFS）和深度优先搜索（DFS）。

1. 准备工作：构建罗马尼亚地图

在开始算法实现前，我们需要先构建罗马尼亚城市间的连接关系。这里使用Python字典来表示图结构：

romania_map = { 'Arad': {'Zerind': 75, 'Sibiu': 140, 'Timisoara': 118}, 'Zerind': {'Arad': 75, 'Oradea': 71}, 'Sibiu': {'Arad': 140, 'Oradea': 151, 'Fagaras': 99, 'Rimnicu Vilcea': 80}, 'Timisoara': {'Arad': 118, 'Lugoj': 111}, 'Oradea': {'Zerind': 71, 'Sibiu': 151}, 'Fagaras': {'Sibiu': 99, 'Bucharest': 211}, 'Rimnicu Vilcea': {'Sibiu': 80, 'Pitesti': 97, 'Craiova': 146}, 'Lugoj': {'Timisoara': 111, 'Mehadia': 70}, 'Mehadia': {'Lugoj': 70, 'Drobeta': 75}, 'Drobeta': {'Mehadia': 75, 'Craiova': 120}, 'Craiova': {'Drobeta': 120, 'Rimnicu Vilcea': 146, 'Pitesti': 138}, 'Pitesti': {'Rimnicu Vilcea': 97, 'Craiova': 138, 'Bucharest': 101}, 'Bucharest': {'Fagaras': 211, 'Pitesti': 101, 'Giurgiu': 90, 'Urziceni': 85}, 'Giurgiu': {'Bucharest': 90}, 'Urziceni': {'Bucharest': 85, 'Hirsova': 98, 'Vaslui': 142}, 'Hirsova': {'Urziceni': 98, 'Eforie': 86}, 'Eforie': {'Hirsova': 86}, 'Vaslui': {'Urziceni': 142, 'Iasi': 92}, 'Iasi': {'Vaslui': 92, 'Neamt': 87}, 'Neamt': {'Iasi': 87} }

同时，我们需要定义各城市到目标城市Bucharest的直线距离（启发式函数值）：

heuristic = { 'Arad': 366, 'Zerind': 374, 'Sibiu': 253, 'Timisoara': 329, 'Oradea': 380, 'Fagaras': 176, 'Rimnicu Vilcea': 193, 'Lugoj': 244, 'Mehadia': 241, 'Drobeta': 242, 'Craiova': 160, 'Pitesti': 100, 'Bucharest': 0, 'Giurgiu': 77, 'Urziceni': 80, 'Hirsova': 151, 'Eforie': 161, 'Vaslui': 199, 'Iasi': 226, 'Neamt': 234 }

2. 广度优先搜索(BFS)实现

BFS是一种盲目搜索算法，它会先探索所有相邻节点，再逐层向外扩展。下面是BFS的实现代码：

from collections import deque def bfs(graph, start, goal): visited = set() queue = deque([(start, [start])]) while queue: current, path = queue.popleft() if current == goal: return path if current not in visited: visited.add(current) for neighbor in graph[current]: if neighbor not in visited: queue.append((neighbor, path + [neighbor])) return None

使用示例：

path = bfs(romania_map, 'Arad', 'Bucharest') print("BFS路径:", ' -> '.join(path))

BFS的特点：

• 总是能找到最短路径（按边数计算）
• 需要较多内存，因为要存储所有已访问节点
• 适用于寻找最短路径或探索所有可能状态

3. 深度优先搜索(DFS)实现

DFS会沿着一条路径尽可能深入，直到无法继续才回溯。下面是DFS的实现：

def dfs(graph, start, goal, path=None, visited=None): if path is None: path = [] if visited is None: visited = set() path = path + [start] visited.add(start) if start == goal: return path for neighbor in graph[start]: if neighbor not in visited: result = dfs(graph, neighbor, goal, path, visited) if result is not None: return result return None

使用示例：

path = dfs(romania_map, 'Arad', 'Bucharest') print("DFS路径:", ' -> '.join(path))

DFS的特点：

• 内存需求相对较小（只需存储当前路径）
• 不一定能找到最短路径
• 适用于存在多条解且路径长度不重要的情况

4. 贪婪最佳优先搜索(GBFS)实现

GBFS是一种启发式搜索算法，总是选择看起来最有希望的节点进行扩展：

import heapq def gbfs(graph, heuristic, start, goal): visited = set() heap = [(heuristic[start], start, [start])] while heap: _, current, path = heapq.heappop(heap) if current == goal: return path if current not in visited: visited.add(current) for neighbor in graph[current]: if neighbor not in visited: heapq.heappush(heap, (heuristic[neighbor], neighbor, path + [neighbor])) return None

使用示例：

path = gbfs(romania_map, heuristic, 'Arad', 'Bucharest') print("GBFS路径:", ' -> '.join(path))

GBFS的特点：

• 速度快，但不保证找到最优解
• 完全依赖启发式函数的质量
• 适用于启发式函数能提供良好估计的情况

5. A*搜索算法实现

A*结合了GBFS和Dijkstra算法的优点，既考虑已走路径的成本，也考虑剩余路径的估计：

def astar(graph, heuristic, start, goal): open_set = [] heapq.heappush(open_set, (0 + heuristic[start], 0, start, [start])) visited = set() while open_set: _, g, current, path = heapq.heappop(open_set) if current == goal: return path if current not in visited: visited.add(current) for neighbor, cost in graph[current].items(): if neighbor not in visited: new_g = g + cost heapq.heappush(open_set, (new_g + heuristic[neighbor], new_g, neighbor, path + [neighbor])) return None

使用示例：

path = astar(romania_map, heuristic, 'Arad', 'Bucharest') print("A*路径:", ' -> '.join(path))

A*的特点：

• 保证找到最优解（如果启发式函数是可采纳的）
• 比纯BFS更高效
• 广泛应用于路径规划和游戏AI

6. 算法性能比较

让我们比较四种算法的表现：

实现性能测试：

import time def test_algorithm(algorithm, *args): start_time = time.time() path = algorithm(*args) end_time = time.time() return path, end_time - start_time # 测试所有算法 algorithms = { 'BFS': bfs, 'DFS': dfs, 'GBFS': gbfs, 'A*': astar } for name, algo in algorithms.items(): if name == 'GBFS' or name == 'A*': path, time_taken = test_algorithm(algo, romania_map, heuristic, 'Arad', 'Bucharest') else: path, time_taken = test_algorithm(algo, romania_map, 'Arad', 'Bucharest') print(f"{name}: 路径长度={len(path)-1}, 耗时={time_taken:.6f}秒")

7. 可视化结果

为了更直观地展示算法差异，我们可以使用matplotlib绘制搜索路径：

import matplotlib.pyplot as plt import networkx as nx def draw_path(graph, path, title): G = nx.Graph() for city in graph: G.add_node(city) for neighbor, cost in graph[city].items(): G.add_edge(city, neighbor, weight=cost) pos = nx.spring_layout(G) nx.draw(G, pos, with_labels=True, node_color='lightblue') path_edges = list(zip(path[:-1], path[1:])) nx.draw_networkx_nodes(G, pos, nodelist=path, node_color='red') nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2) plt.title(title) plt.show() # 获取各算法的路径 bfs_path = bfs(romania_map, 'Arad', 'Bucharest') dfs_path = dfs(romania_map, 'Arad', 'Bucharest') gbfs_path = gbfs(romania_map, heuristic, 'Arad', 'Bucharest') astar_path = astar(romania_map, heuristic, 'Arad', 'Bucharest') # 绘制路径 draw_path(romania_map, bfs_path, 'BFS搜索路径') draw_path(romania_map, dfs_path, 'DFS搜索路径') draw_path(romania_map, gbfs_path, 'GBFS搜索路径') draw_path(romania_map, astar_path, 'A*搜索路径')

8. 进阶优化与思考

在实际项目中，我们可以对基础算法进行多种优化：

1. 启发式函数改进：

   • 考虑更多因素（如交通状况、地形）
   • 使用机器学习方法学习更好的启发式

2. 内存优化：

   • 使用迭代加深的深度优先搜索(IDDFS)
   • 实现双向搜索

3. 并行化：

   • 多线程/多进程实现
   • GPU加速

4. 实时应用：

   • 动态调整路径（如遇到障碍）
   • 增量式搜索

# 双向BFS示例 def bidirectional_bfs(graph, start, goal): forward_visited = {start: [start]} backward_visited = {goal: [goal]} forward_queue = deque([start]) backward_queue = deque([goal]) while forward_queue and backward_queue: # 前向搜索 current = forward_queue.popleft() for neighbor in graph[current]: if neighbor not in forward_visited: forward_visited[neighbor] = forward_visited[current] + [neighbor] forward_queue.append(neighbor) if neighbor in backward_visited: return forward_visited[neighbor][:-1] + backward_visited[neighbor][::-1] # 后向搜索 current = backward_queue.popleft() for neighbor in graph[current]: if neighbor not in backward_visited: backward_visited[neighbor] = backward_visited[current] + [neighbor] backward_queue.append(neighbor) if neighbor in forward_visited: return forward_visited[neighbor][:-1] + backward_visited[neighbor][::-1] return None

通过这个罗马尼亚地图寻路项目，我们不仅实现了四种基础搜索算法，还深入理解了它们的适用场景和性能特点。在实际应用中，根据具体需求选择合适的算法或组合多种算法，往往能获得更好的效果。