路径规划中的 AI 算法：从传统 Dijkstra 到强化学习的演进

路径规划中的 AI 算法从传统 Dijkstra 到强化学习的演进一、深度引言与场景痛点现实世界的路网不是静态图大二学数据结构时Dijkstra 算法给人的印象是最短路径问题已被完美解决。但走进真实的物流和出行场景后才发现课本上的 Dijkstra 假设了一个极度理想化的世界道路权重是静态的、节点数在可控范围内、不存在实时变化。现实路网的复杂度远超课本一条 30 公里的主干道在早高峰和午夜通过时间可能相差 3 倍红绿灯、交通事故、临时封路让路网权重持续变化。更重要的是商业路径规划不只是求最短路径还有多目标优化同时考虑距离、时间、通行费用、司机偏好等多个维度。本文从传统图算法到现代 AI 方法梳理路径规划技术的演进脉络。二、底层机制与原理深度剖析Dijkstra 的局限与改进方向Dijkstra 算法基于贪心策略每次选择离起点最近的未访问节点。它的两个核心假设边权重是静态且已知的全局信息获取无成本而实际场景中这两条都不成立。以下是一个简要的演进关系A* 算法的启发式改进A* 在 Dijkstra 的基础上引入启发式函数 h(n)从节点 n 到终点的估计距离。搜索代价 f(n) g(n) h(n)其中 g(n) 是起点到 n 的实际代价。关键在于 h(n) 的选择h(n) 0 → 等价于 Dijkstrah(n) ≤ 实际距离 → 保证找到最优解h(n) 越接近实际距离 → 搜索效率越高在路网场景中h(n) 通常取欧几里得距离或大圆距离这在开放空间中是最优启发式。三、生产级代码实现与最佳实践# A* 算法在路网中的应用 —— 使用 OSMnx 加载真实路网 import heapq from geopy.distance import geodesic class RoadNetworkPathPlanner: 基于真实路网的路径规划器 使用 A* 算法启发式函数为 Haversine 距离。 适用于 OpenStreetMap 导出的路网数据。 def __init__(self, graph): 初始化路网图 Args: graph: OSMnx 格式的路网图节点是经纬度坐标 边包含长度、道路等级、是否单行等属性 self.graph graph def a_star(self, origin_node, destination_node, weight_fieldlength) - list: A* 路径搜索 与课本上的 Dijkstra 的区别 1. 使用真实的地理距离作为启发式Haversine 距离 2. 边权重从 OSM 数据中提取道路长度、速度限制等 3. 返回的是路网节点序列而非抽象顶点 # 获取终点坐标用于计算启发式距离 dest_lat self.graph.nodes[destination_node][y] dest_lon self.graph.nodes[destination_node][x] # 优先队列(f_score, counter, node) # counter 用于打破平局Python 的 tuple 比较要求元素可比 open_set [] counter 0 heapq.heappush(open_set, (0, counter, origin_node)) # 追踪信息 came_from {} g_score {origin_node: 0} while open_set: _, _, current heapq.heappop(open_set) if current destination_node: return self._reconstruct_path(came_from, current) # 遍历当前节点的所有邻居 for _, neighbor, edge_data in self.graph.edges( current, dataTrue ): # 获取边的权重 —— 道路长度 # 如果考虑多目标优化这里会使用加权公式 edge_weight edge_data.get(weight_field, 0) tentative_g g_score[current] edge_weight if neighbor not in g_score or \ tentative_g g_score[neighbor]: # 更新路径记录 came_from[neighbor] current g_score[neighbor] tentative_g # 计算启发式估计 —— Haversine 距离 neighbor_lat self.graph.nodes[neighbor][y] neighbor_lon self.graph.nodes[neighbor][x] h self._haversine( neighbor_lat, neighbor_lon, dest_lat, dest_lon ) f_score tentative_g h counter 1 heapq.heappush( open_set, (f_score, counter, neighbor) ) return [] # 无法到达 def _haversine(self, lat1, lon1, lat2, lon2) - float: 计算两点之间的 Haversine 距离米 这个函数是 A* 启发式的核心。 越准确的启发式估计A* 搜索效率越高。 但计算复杂度也会增加——需要在精度和速度之间权衡。 from math import radians, sin, cos, sqrt, atan2 R 6371000 # 地球半径米 lat1, lon1 radians(lat1), radians(lon1) lat2, lon2 radians(lat2), radians(lon2) dlat lat2 - lat1 dlon lon2 - lon1 a sin(dlat/2)**2 cos(lat1) * cos(lat2) * sin(dlon/2)**2 c 2 * atan2(sqrt(a), sqrt(1-a)) return R * c def _reconstruct_path(self, came_from, current) - list: 从 came_from 字典重建路径 path [current] while current in came_from: current came_from[current] path.append(current) return path[::-1] def multi_objective_path( self, origin, destination, weights: dict ) - list: 多目标路径规划 将多个优化目标距离、时间、成本融合为综合权重。 Args: weights: 各目标的权重如 {length: 0.4, travel_time: 0.5, toll: 0.1} # 创建综合权重的自定义字段 # 这个方法需要在 graph 中预计算每条边的综合权重 # 然后使用单目标 A* 进行搜索 for u, v, data in self.graph.edges(dataTrue): combined 0 for field, weight in weights.items(): # 对每个目标字段进行归一化防止量纲差异 raw_value data.get(field, 0) if field length: combined weight * raw_value / 1000 # 归一化为千米 elif field travel_time: combined weight * raw_value / 60 # 归一化为分钟 else: combined weight * raw_value data[combined_weight] combined return self.a_star(origin, destination, combined_weight)# 强化学习在路径规划中的简化实现 Q-learning 在网格世界中的路径规划示例。 这是 RL 在路径规划中最基础的演示。 实际路网的 SotA 方案使用 DQN 图神经网络的组合。 import numpy as np class QLearningNavigator: Q-learning 导航器 —— 简化示例用于理解 RL 的基本思想 RL 相比传统算法的优势 - 不需要精确的路网模型 - 可以从历史数据中学习偏好 - 能处理动态变化的交通状况 def __init__(self, grid_size: int): self.size grid_size # Q 表状态(位置) × 动作(上下左右) self.q_table np.zeros((grid_size * grid_size, 4)) def train(self, episodes: int 1000, alpha: float 0.1, gamma: float 0.9, epsilon: float 0.1): 训练 Q-learning 代理 Args: alpha: 学习率 gamma: 折扣因子未来奖励的重要性 epsilon: 探索率随机选择动作的概率 for episode in range(episodes): state (0, 0) # 起点 done False steps 0 while not done and steps self.size * 4: steps 1 state_idx self._state_to_idx(state) # ε-greedy 策略探索 vs 利用 if np.random.random() epsilon: action np.random.randint(4) # 探索 else: action np.argmax(self.q_table[state_idx]) # 利用 # 执行动作 next_state self._move(state, action) reward self._get_reward(next_state) next_idx self._state_to_idx(next_state) # Q-learning 更新规则 # 核心思想当前状态的价值 # 当前奖励 折扣后的未来最大价值 best_next np.max(self.q_table[next_idx]) self.q_table[state_idx][action] alpha * ( reward gamma * best_next - self.q_table[state_idx][action] ) state next_state if state (self.size - 1, self.size - 1): done True def find_path(self, start: tuple, goal: tuple) - list: 使用训练好的 Q 表找到路径 state start path [state] for _ in range(self.size * 4): state_idx self._state_to_idx(state) action np.argmax(self.q_table[state_idx]) state self._move(state, action) path.append(state) if state goal: break return path def _state_to_idx(self, state: tuple) - int: return state[0] * self.size state[1] def _move(self, state, action) - tuple: r, c state if action 0: r max(0, r - 1) # 上 elif action 1: r min(self.size - 1, r 1) # 下 elif action 2: c max(0, c - 1) # 左 elif action 3: c min(self.size - 1, c 1) # 右 return (r, c) def _get_reward(self, state) - float: 奖励函数设计 —— RL 中最关键的部分 r, c state if state (self.size - 1, self.size - 1): return 100.0 # 到达终点的正向奖励 # 越靠近目标奖励越大引导代理向目标移动 # 这个 reward shaping 可以大大加速训练收敛 return -1.0 (r c) * 0.1四、边界分析与架构权衡何时使用传统算法 vs ML 方法场景推荐方法原因简单路网、静态权重A* / CH结果确定、可解释性强时变路网TDSP / 时变 A*需要历史交通数据超大规模百万节点Contraction Hierarchies预处理后查询极快需学习用户偏好强化学习从历史轨迹中学偏好实时动态变化D* Lite ML 增强增量更新 预测工程项目中的取舍在实际产品中很少单独使用纯 ML 方法来做路径规划。主流的方案是用 ML 模型预测各路段在特定时间段的旅行时间将这些预测值作为 A* 算法的边权重A* 负责找到最优路径ML 负责让边权重更准确这种ML 预测 图搜索的组合既有 ML 的预测能力又有图算法的可解释性。五、总结路径规划算法从 Dijkstra 到 A* 再到 RL 的演进本质上是在解决两个核心矛盾计算效率 vs 解的最优性如何在有限时间内找到足够好的解静态假设 vs 动态现实如何让算法适应持续变化的路网在工业实践中ML 预测 图算法求解是当前最实用的组合方案。ML 提供对未来状态的预测哪条路会堵图算法在预测值的基础上寻找最优路径。这是一个好的融合范式——让 ML 做它擅长的事预测让图算法做它擅长的事搜索。对于后端实习生来说理解传统图算法仍然是最重要的基础。即使未来有更先进的 ML 方法A* 和 Dijkstra 这些基础算法所蕴含的贪心 启发式思想会在很多分布式系统的路由和调度设计中反复出现。