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

罗马尼亚地图寻路实战Python实现四大经典搜索算法罗马尼亚地图寻路问题是人工智能和算法课程中的经典案例它生动展示了不同搜索策略在实际问题中的应用效果。对于刚接触算法或需要完成课程作业的Python开发者来说如何用代码实现这些算法往往是一个挑战。本文将手把手教你用Python实现贪婪搜索、A*搜索、广度优先搜索(BFS)和深度优先搜索(DFS)四种算法并提供完整的可运行代码。1. 地图数据结构与基础准备在开始实现算法前我们需要先定义罗马尼亚地图的数据结构。这里使用邻接表表示法将城市作为节点城市间的道路作为边并赋予实际距离作为权重。# 罗马尼亚城市地图的图结构表示 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} } # 各城市到布加勒斯特的直线距离(启发式函数h值) 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 queue import Queue def bfs_search(graph, start, goal): visited {} queue Queue() queue.put(start) visited[start] None while not queue.empty(): current queue.get() if current goal: break for neighbor in graph[current]: if neighbor not in visited: queue.put(neighbor) visited[neighbor] current # 重构路径 path [] current goal while current is not None: path.append(current) current visited[current] path.reverse() return path # 使用示例 start_city Arad goal_city Bucharest bfs_path bfs_search(romania_map, start_city, goal_city) print(fBFS找到的路径: { - .join(bfs_path)})BFS的特点使用队列数据结构(FIFO)按层次遍历图找到的路径是边数最少的时间和空间复杂度都是O(b^d)其中b是分支因子d是解的深度3. 深度优先搜索(DFS)实现DFS沿着一条路径尽可能深入地搜索直到到达末端节点然后回溯并尝试其他路径。DFS有两种实现方式递归和迭代。3.1 递归实现DFSdef dfs_recursive(graph, current, goal, visitedNone, pathNone): if visited is None: visited set() if path is None: path [] visited.add(current) path.append(current) if current goal: return path for neighbor in graph[current]: if neighbor not in visited: result dfs_recursive(graph, neighbor, goal, visited, path) if result is not None: return result path.pop() return None # 使用示例 dfs_path_recursive dfs_recursive(romania_map, start_city, goal_city) print(f递归DFS找到的路径: { - .join(dfs_path_recursive)})3.2 迭代实现DFSdef dfs_iterative(graph, start, goal): stack [(start, [start])] visited set() while stack: current, path stack.pop() if current goal: return path if current not in visited: visited.add(current) for neighbor in graph[current]: stack.append((neighbor, path [neighbor])) return None # 使用示例 dfs_path_iterative dfs_iterative(romania_map, start_city, goal_city) print(f迭代DFS找到的路径: { - .join(dfs_path_iterative)})DFS的特点使用栈数据结构(LIFO)不保证找到最短路径空间复杂度较低为O(bm)其中b是分支因子m是最大深度可能陷入深度无限的分支中4. 贪婪最佳优先搜索实现贪婪最佳优先搜索是一种启发式搜索算法它总是扩展看起来离目标最近的节点只使用启发式函数h(n)来评估节点。import heapq def greedy_best_first_search(graph, start, goal, heuristic): frontier [] heapq.heappush(frontier, (heuristic[start], start)) came_from {start: None} while frontier: _, current heapq.heappop(frontier) if current goal: break for neighbor in graph[current]: if neighbor not in came_from: priority heuristic[neighbor] heapq.heappush(frontier, (priority, neighbor)) came_from[neighbor] current # 重构路径 path [] current goal while current is not None: path.append(current) current came_from[current] path.reverse() return path # 使用示例 greedy_path greedy_best_first_search(romania_map, start_city, goal_city, heuristic) print(f贪婪搜索找到的路径: { - .join(greedy_path)})贪婪搜索的特点使用优先队列(通常用堆实现)只考虑启发式函数h(n)不保证找到最优解在最坏情况下时间复杂度与BFS相同5. A*搜索算法实现A*搜索结合了Dijkstra算法的保证最优性和贪婪搜索的高效性使用评估函数f(n) g(n) h(n)其中g(n)是从起点到n的实际成本h(n)是从n到目标的估计成本。def a_star_search(graph, start, goal, heuristic): frontier [] heapq.heappush(frontier, (0, start)) came_from {start: None} cost_so_far {start: 0} while frontier: _, current heapq.heappop(frontier) if current goal: break for neighbor, distance in graph[current].items(): new_cost cost_so_far[current] distance if neighbor not in cost_so_far or new_cost cost_so_far[neighbor]: cost_so_far[neighbor] new_cost priority new_cost heuristic[neighbor] heapq.heappush(frontier, (priority, neighbor)) came_from[neighbor] current # 重构路径 path [] current goal while current is not None: path.append(current) current came_from[current] path.reverse() return path, cost_so_far[goal] # 使用示例 a_star_path, total_cost a_star_search(romania_map, start_city, goal_city, heuristic) print(fA*搜索找到的路径: { - .join(a_star_path)}) print(f总距离: {total_cost} km)A*搜索的特点使用评估函数f(n) g(n) h(n)如果h(n)是可采纳的(不高估实际成本)则保证找到最优解如果h(n)是一致的则算法效率更高比Dijkstra算法更高效因为它使用启发式信息引导搜索6. 算法性能比较与选择建议为了比较这四种算法的性能我们可以从几个维度进行分析算法类型最优性保证时间复杂度空间复杂度适用场景BFS边数最少路径O(b^d)O(b^d)寻找最短边数路径DFS不保证最优O(b^m)O(bm)空间有限或解较深贪婪搜索不保证最优O(b^d)O(b^d)快速找到可行解A*搜索最优路径(若h可采纳)取决于h的质量O(b^d)寻找最优路径注意b是分支因子d是解的深度m是图的最大深度在实际项目中选择哪种算法取决于具体需求如果需要保证找到最优解A*通常是首选如果空间是主要限制DFS可能更合适如果只关心边数最少的路径BFS是理想选择当需要快速找到一个可行解而不一定是最优解时贪婪搜索可能足够7. 进阶优化与扩展思路7.1 启发式函数设计A*搜索的性能很大程度上取决于启发式函数h(n)的质量。一个好的启发式函数应该尽可能接近实际成本同时不能高估实际成本(即可采纳性)。我们可以尝试设计不同的启发式函数# 基于城市人口密度的启发式函数示例 city_population { Arad: 150000, Bucharest: 1800000, Sibiu: 120000, # 其他城市人口数据... } def population_based_heuristic(city, goal): # 假设人口密度越高交通越拥堵实际距离越长 density_ratio (city_population[city] city_population[goal]) / 2e6 return heuristic[city] * (1 density_ratio)7.2 双向搜索对于大型图可以考虑双向搜索策略即从起点和终点同时进行搜索直到两个搜索相遇def bidirectional_search(graph, start, goal): # 实现双向搜索 pass7.3 可视化路径使用Python的matplotlib或networkx库可以可视化搜索过程和结果路径import networkx as nx import matplotlib.pyplot as plt def visualize_path(graph, path): G nx.Graph() for city in graph: G.add_node(city) for neighbor, dist in graph[city].items(): G.add_edge(city, neighbor, weightdist) pos nx.spring_layout(G) nx.draw(G, pos, with_labelsTrue, node_colorlightblue) path_edges list(zip(path[:-1], path[1:])) nx.draw_networkx_nodes(G, pos, nodelistpath, node_colorr) nx.draw_networkx_edges(G, pos, edgelistpath_edges, edge_colorr, width2) plt.show() # 可视化A*搜索找到的路径 visualize_path(romania_map, a_star_path)7.4 性能测试与优化我们可以编写一个简单的性能测试函数来比较不同算法的运行时间import time def test_algorithm_performance(): algorithms { BFS: bfs_search, DFS: dfs_iterative, Greedy: greedy_best_first_search, A*: a_star_search } results {} for name, algorithm in algorithms.items(): start_time time.time() if name in [Greedy, A*]: path algorithm(romania_map, start_city, goal_city, heuristic) else: path algorithm(romania_map, start_city, goal_city) elapsed time.time() - start_time results[name] (len(path), elapsed) print(算法性能比较:) for name, (path_length, time_taken) in results.items(): print(f{name}: 路径长度 {path_length}, 耗时 {time_taken:.6f}秒) test_algorithm_performance()在实际开发中我发现A*搜索在大多数情况下都能在合理时间内找到最优解特别是当启发式函数设计得当时。而DFS在某些情况下可能会意外地快速找到解但结果质量不稳定。