路径规划中的 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 → 等价于 Dijkstra
• h(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_field='length') -> 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, data=True
):
# 获取边的权重 —— 道路长度
# 如果考虑多目标优化，这里会使用加权公式
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(data=True):
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 方法

工程项目中的取舍

在实际产品中，很少单独使用纯 ML 方法来做路径规划。主流的方案是：

• 用 ML 模型预测各路段在特定时间段的旅行时间
• 将这些预测值作为 A* 算法的边权重
• A* 负责找到最优路径，ML 负责让边权重更准确

这种"ML 预测 + 图搜索"的组合，既有 ML 的预测能力，又有图算法的可解释性。

五、总结

路径规划算法从 Dijkstra 到 A* 再到 RL 的演进，本质上是在解决两个核心矛盾：

在工业实践中，"ML 预测 + 图算法求解"是当前最实用的组合方案。ML 提供对未来状态的预测（哪条路会堵），图算法在预测值的基础上寻找最优路径。这是一个好的融合范式——让 ML 做它擅长的事（预测），让图算法做它擅长的事（搜索）。

对于后端实习生来说，理解传统图算法仍然是最重要的基础。即使未来有更先进的 ML 方法，A* 和 Dijkstra 这些基础算法所蕴含的"贪心 + 启发式"思想，会在很多分布式系统的路由和调度设计中反复出现。