课程导论：路径规划问题定义、A*与Dijkstra算法对比、应用场景介绍
大家好，欢迎来到《路径规划：A*与Dijkstra算法实战》的第一课。
我是这门课的主讲。做了十几年路径规划，从机器人导航到游戏AI，从物流调度到自动驾驶，我踩过的坑比走过的路还多（笑）。今天咱们先聊聊基础，把地基打牢。
什么是路径规划？
说白了，路径规划就是解决一个问题：给定起点和终点，找出一条能走的路，并且这条路在某些方面是「最好」的。
你想想看，这其实是个很朴素的需求。你从家去公司，打开地图App，它给你推荐三条路线——最快的、最短的、避开收费站的。这就是路径规划。
但在工程领域，问题要复杂得多。我当年刚入行时，接到的第一个任务就是给仓库里的AGV小车规划路径。当时我想，这不就是找条路嘛，简单。结果一上手就懵了——地图是动态的，货架会移动，小车还要避让其他小车。嗯，这里要注意，现实世界中的路径规划，从来不是单纯的「找路」。
一个完整的路径规划问题，通常包含三个要素：
- 环境表示：地图怎么建？栅格图、拓扑图、路网图？
- 约束条件：不能穿墙、不能逆行、转弯半径限制？
- 优化目标：最短距离？最短时间？最安全？还是综合评分？
核心观点：路径规划的本质，是在约束条件下寻找最优解。没有约束的路径规划，就像没有规则的比赛——谁都能赢，但谁都不服。
Dijkstra算法：稳扎稳打的「老黄牛」
Dijkstra算法，1956年诞生，经典中的经典。我个人习惯把它叫做「地毯式搜索」——从起点开始，一层一层往外扩，直到覆盖终点。
它的核心思想很简单：每次选择当前距离起点最近且未访问过的节点，更新它的邻居距离。
我在项目中遇到过一个问题：用Dijkstra给无人机规划航线，地图有几千个节点。算法跑是能跑，但速度慢得让人抓狂。为什么？因为它太「老实」了——它不知道终点在哪，只能傻傻地往所有方向扩展。
来看一段最简化的伪代码：
function Dijkstra(Graph, start, end):
dist[start] = 0
queue = priority_queue([(0, start)])
while queue not empty:
current_dist, current = queue.pop()
if current == end:
return reconstruct_path()
for neighbor in Graph.neighbors(current):
new_dist = current_dist + Graph.weight(current, neighbor)
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
queue.push((new_dist, neighbor))
return None # 没找到路径你看，它没有「方向感」。但好处是——它一定能找到最短路径。这是数学上证明了的。
个人经验：如果你的地图规模不大（几百个节点以内），或者你要求绝对最优解，Dijkstra是首选。我曾经用它做城市路网规划，虽然慢了点，但结果无可挑剔。
A*算法：带「指南针」的Dijkstra
A*算法，1968年提出，是Dijkstra的「升级版」。它多了一个东西——启发式函数。
说白了，A*在扩展节点时，不光看「已经走了多远」，还估算「到终点还有多远」。这样它就能朝着终点方向优先搜索，而不是像Dijkstra那样四面开花。
你想想看，这就像你去一个陌生城市找一家餐厅。Dijkstra的做法是：从酒店出发，每条街都走一遍，直到找到那家餐厅。A*的做法是：打开手机地图，先看餐厅大概在哪个方向，然后朝那个方向走。
A*的核心公式就一个：
f(n) = g(n) + h(n)
- g(n)：从起点到当前节点n的实际代价
- h(n)：从节点n到终点的估计代价（启发式函数）
- f(n)：综合评分，A*每次选f(n)最小的节点扩展
这里有个关键点：h(n)的设计决定了A*的性能和正确性。
我曾经踩过一个坑。做游戏AI时，我用了曼哈顿距离作为启发式函数，结果角色在复杂地形里绕来绕去，就是找不到近路。为什么？因为曼哈顿距离假设可以横平竖直地走，但地图里有障碍物，实际路径比估计的长得多。嗯，这里要注意，如果h(n)低估了实际代价，A*能找到最优解但效率低；如果高估了，效率高但可能找不到最优解。
避坑指南：我曾经在一个物流项目中，为了追求速度，把h(n)设得特别大。结果算法跑得飞快，但给出的路径明显不是最短的。后来排查了一整天，才发现是启发式函数「过度乐观」了。记住：h(n)必须满足「可采纳性」——不能高估到终点的实际代价。
Dijkstra vs A*：一张表说清楚
| 对比维度 | Dijkstra | A* |
|---|---|---|
| 搜索策略 | 广度优先，无方向 | 启发式引导，有方向 |
| 最优性 | 保证全局最优 | 保证最优（h(n)可采纳时） |
| 时间复杂度 | O(V²) 或 O((V+E)logV) | 通常比Dijkstra快，但取决于h(n) |
| 空间复杂度 | 较高，需存储所有节点 | 与Dijkstra相当 |
| 适用场景 | 小规模地图、要求绝对最优 | 大规模地图、实时性要求高 |
| 实现难度 | 简单 | 中等（需设计h(n)） |
我个人习惯这样选：如果地图节点少于1000，或者路径必须绝对最优，用Dijkstra。如果地图很大，或者需要实时响应，用A*。
应用场景：它们都在哪里发光？
这两个算法，几乎无处不在。我随便列几个：
- 游戏AI：角色寻路、NPC移动。A*是绝对主力，我做过的一款MMO游戏，同时有几百个角色在用A*寻路。
- 机器人导航：扫地机器人、仓库AGV、无人机。Dijkstra常用于全局路径规划，A*用于局部动态避障。
- 地图导航：高德、百度地图。底层用的是A*的变种，结合实时交通数据。
- 网络路由：OSPF协议用的就是Dijkstra算法，计算数据包的最优路径。
- 电路设计：芯片布线时，要在几亿个节点中找到最短连接路径，A*的变种是标配。
一句话总结：Dijkstra是「稳」，A*是「快」。没有谁更好，只有谁更适合。就像我常跟团队说的——选对工具，比用好工具更重要。
课程预告
这一章我们只是开了个头。接下来，我们会一步步深入：
- 第2章：手写Dijkstra，从零实现
- 第3章：手写A*，理解启发式函数的魔力
- 第4章：对比实验，看两种算法在真实地图上的表现
- ……一直到第30章：多机器人协同路径规划
每一章我都会带着代码，带着我踩过的坑，带着实战经验。你跟着我走完这30章，不敢说成为专家，但至少遇到路径规划问题，你能知道「该用什么、怎么用、为什么这么用」。
好，第一章就到这里。下一章我们开始写代码——用Python手撸一个Dijkstra算法。到时候见。