第4章 经典路径规划算法面试问答
本章聚焦自动驾驶规划岗位面试中最高频的三大经典算法：A*、Dijkstra 与 RRT。通过结构化问答框架，帮助你在15分钟内清晰展现算法理解力、工程思维与表达能力。每道题均附评分权重、追问路径及常见陷阱，配合下方表达框架图，形成完整应答策略。
▲ 面试回答框架：按此顺序组织语言，加分效果最佳
面试问题 1：请解释 A* 算法及其在自动驾驶路径规划中的应用
面试官考察点：算法理解深度、启发式函数设计、实际工程结合能力。
回答框架：
- 一句话定位：A* 是启发式搜索，结合 Dijkstra 完备性与贪心效率。
- 核心公式：f(n)=g(n)+h(n)，g 为实际代价，h 为启发估计。
- 启发式选择：自动驾驶常用欧氏距离或曼哈顿距离，需满足可采纳性。
- 应用场景：全局路径规划，如 OpenDrive 地图上搜索车道级路径。
- 工程优化：跳点搜索（JPS）减少节点扩展、分层规划缩短搜索时间。
简短示例回答（85字）：
A* 结合了 Dijkstra 的完备性和贪心效率，通过 f = g + h 指导搜索。在自动驾驶中用于全局路径规划，例如从当前车道到目标车道的最优路线。常用欧氏距离作为启发函数，工程上采用 JPS 或分层规划加速，兼顾实时性与最优性。
A* 结合了 Dijkstra 的完备性和贪心效率，通过 f = g + h 指导搜索。在自动驾驶中用于全局路径规划，例如从当前车道到目标车道的最优路线。常用欧氏距离作为启发函数，工程上采用 JPS 或分层规划加速，兼顾实时性与最优性。
可能追问：
- h(n) 一定小于真实代价吗？不满足可采纳性会怎样？
- 在动态环境中如何调整 A*？
- 对比 Hybrid A* 与经典 A* 的区别。
避坑提醒：不要只背书遗忘讲工程落地；避免把 h(n) 单纯当作直线距离而不提可采纳性；切忌混淆 A* 与 Dijkstra 的终止条件。
面试问题 2：比较 Dijkstra 和 A* 算法的区别，何时使用 A*？
面试官考察点：算法对比意识、代价函数理解、场景决策能力。
回答框架：
- 共同点：都是图搜索，保证完备性与最优性（当启发式可采纳时）。
- 差异点：Dijkstra 仅使用实际代价 g，A* 增加启发式 h 加速搜索。
- 复杂度对比：Dijkstra 无偏向，A* 在良好启发下可减少扩展节点。
- 使用场景：搜索空间大、目标已知时用 A*；空间小或需严格最优且 h 不可靠时用 Dijkstra。
简短示例回答（90字）：
Dijkstra 无启发函数，逐层扩展直至终点，保证完备最优但效率低。A* 加入启发项 f = g + h，有方向性收敛，通常更快。在自动驾驶全局规划中，若启发式设计合理（如欧氏距离），首选 A*；若环境复杂或需要严格最优解，则回退到 Dijkstra。
Dijkstra 无启发函数，逐层扩展直至终点，保证完备最优但效率低。A* 加入启发项 f = g + h，有方向性收敛，通常更快。在自动驾驶全局规划中，若启发式设计合理（如欧氏距离），首选 A*；若环境复杂或需要严格最优解，则回退到 Dijkstra。
可能追问：
- 如果 h(n) 恒为 0，A* 退化为 Dijkstra，如何证明？
- 在网格地图中，两种算法的时间复杂度具体差距？
- 有没有同时使用两种算法的混合规划方式？
避坑提醒：不要只说“A* 更快”而不解释原因；避免忽视 Dijkstra 在权重图上的鲁棒性；切忌把 A* 说成“总是最优”（需满足可采纳性）。
面试问题 3：什么是 RRT 算法？在规划中的优缺点？
面试官考察点：采样算法理解、随机性与确定性平衡、实际工程局限。
回答框架：
- 原理：在状态空间中随机采样生成树，从根节点逐步扩展至目标区域。
- 优势：无需显式构建地图，高维空间有效；概率完备但非最优。
- 缺点：路径抖动、非最优、难处理狭窄通道。
- 改进版：RRT*（渐近最优）、Informed RRT*（缩小采样区域）。
- 自动驾驶适用：非结构化场景（停车场、越野）探索，常与平滑后处理结合。
简短示例回答（95字）：
RRT 通过随机采样构建搜索树，可快速探索高维空间，无需精确障碍建模。优点是概率完备且实现简单；缺点是路径质量差、非最优。在自动驾驶中常用于泊车、越野等非结构化场景，工程上需结合 RRT* 做渐近最优，并用 B-spline 平滑输出轨迹。
RRT 通过随机采样构建搜索树，可快速探索高维空间，无需精确障碍建模。优点是概率完备且实现简单；缺点是路径质量差、非最优。在自动驾驶中常用于泊车、越野等非结构化场景，工程上需结合 RRT* 做渐近最优，并用 B-spline 平滑输出轨迹。
可能追问：
- RRT* 如何实现渐近最优？
- 在狭窄通道中 RRT 失效如何改进？
- RRT 与 A* 相比，在什么场景下优劣势逆转？
避坑提醒：不要只讲优点不提工程痛点（如路径不平滑）；避免误认为 RRT 保证最优解；切忌忽略后处理平滑的必要性。
本章面试评分维度与自检清单
| 评分维度 | 权重 | 关键表现 |
|---|---|---|
| 算法理解 | 30% | 能清晰阐述核心公式、伪码逻辑、复杂度 |
| 工程实现 | 25% | 结合实际自动驾驶场景讲优化/修改 |
| 优化改进 | 20% | 提出变体或加速策略（JPS、RRT*） |
| 表达逻辑 | 15% | 结构清晰、分点、先总后分 |
| 应变能力 | 10% | 对追问的快速拆解与深入回答 |
自检清单（回答前逐项核对）：
- ✅ 是否先确认问题边界，避免答非所问？
- ✅ 核心概念是否用公式或伪码支撑？
- ✅ 是否主动对比其他算法（Dijkstra / RRT 等）？
- ✅ 时间/空间复杂度是否脱口而出？
- ✅ 是否提及工程痛点（实时性、狭窄通道、路径平滑）？
- ✅ 是否给出至少一种改进方案或变体？
- ✅ 回答中是否使用自动驾驶具体场景举例？
- ✅ 语气是否自信、无模糊表达（“可能”、“大概”）？
- ✅ 追问后是否能进一步展开而不重复？
- ✅ 结尾是否主动总结优缺点并扣题？