📚 课程目录第3章高频面试题之搜索算法

第三章搜索算法：A*、Dijkstra、RRT、Lattice Planner 对比与选型

面试高频度：★★★★★｜核心能力：路径搜索理论 + 工程选型思维 + 应用场景判断

自动驾驶规划系统中的搜索算法是面试必考模块。面试官关注你是否理解各算法的本质差异、适用场景和工程化取舍。本章从“算法原理—短板—选型依据”三个层次拆解。

面试官考察点	基础算法理解深度、评判指标（完备性、最优性、效率）以及工程环境约束。
回答框架	1. 共性：都是图搜索，都保证最优性（Dijkstra无启发，A有启发）。2. 差异：Dijkstra无偏搜索，A利用启发函数加速收敛。3. 选型主要看地图规模和场景：地图大但障碍稳定 → A*；需要精确最优或无成本启发 → Dijkstra。
简短示例回答	“高速公路场景常用A，因为路网拓扑清晰，曼哈顿或欧式距离作为启发足够高效；泊车/园区复杂障碍我会选Dijkstra确保最优避免死胡同。此外，如果内存受限且地图小，Dijkstra实现更简单，A的启发函数需要额外调参。”
可能追问	① 如果启发函数高估了真实成本会怎样？ ② 你如何设计一个可采纳的启发函数？ ③ 对动态障碍你如何调整？
避坑提醒	不要只背“A更快”。面试官希望你理解启发函数的“可采纳性”和“一致性”以及反例（如高估导致非最优）。并联系实际：A用在泊车路径时，转弯代价需精确建模。

面试官考察点	概率完备性理解、随机采样算法的工程应用、与A*融合思维。
回答框架	1. 核心：随机采样→生长树→避障。2. 优点：不受状态空间维度限制、无网格依赖、适合乱停/越野等复杂场景。3. 缺点：路径不平滑、非最优、收敛慢。4. 改进：RRT、Informed RRT、用B样条后处理。
简短示例回答	“去年在园区无人配送项目中，我们用RRT做全局粗路径，再用B样条平滑。因为多辆乱停放车辆造成网格建图困难，而RRT只需碰撞检测，快速找到可行走廊，后续交给A*做精细调整。”
可能追问	① RRT*如何改进最优性？ ② 你如何设置采样偏置？ ③ 多个RRT并行搜索会有什么问题？
避坑提醒	避免说“RRT完全不用地图”，它依赖障碍物碰撞检测函数。回答中要体现“概率完备”而非“完备”的精度差异。并主动提及后处理（平滑/剪枝）来弥补路径锯齿。

面试官考察点	运动规划基础、对结构化/非结构化场景的定义、算法设计取舍。
回答框架	1. Lattice 本质：在Frenet坐标系中沿参考线生成横向+纵向候选轨迹，按代价（舒适、效率、安全）排序。2. 与RRT的区别：Lattice有固定模式（采样而非随机），适合车道线清晰的环境；RRT随机生长，更适合任意形状障碍。3. 工程中常结合：全局用A*/Dijkstra，局部用Lattice做轨迹优化。
简短示例回答	“在高速领航项目中，我们用Lattice做局部规划。纵向按速度采样，横向按偏移采样，选出代价最小的轨迹。相比RRT，Lattice每次规划120条候选轨迹，计算量可控且输出轨迹自带速度曲线，后处理少。”
可能追问	① 如何保证Lattice生成的轨迹是可行且避障的？ ② Frenet和Cartesian的转换你如何处理？ ③ 如果参考线曲率突变怎么办？
避坑提醒	不要简单说“Lattice就是撒点”。要讲清Frenet坐标系、候选轨迹生成库、代价函数设计。面试官会追问“横向偏移步长如何定？纵向速度分辨率多少？”体现工程细节。

项目名称	城市开放道路自主泊车/低速行驶混合规划系统
业务背景	园区无人配送车需在车辆乱停、行人穿行的区域自主规划。道路有车道线但常被占用，需要兼顾结构化行驶与随机避障。
规模指标	场景面积 2km²；路径长度 ≤500m；规划频率 20Hz；成功避障率 > 99%；平均规划耗时 < 15ms（Intel i7-8700）。
技术栈	C++17、ROS2、Eigen、Boost、自定义A全局规划、RRT + B样条、Lattice Planner（Frenet采样）。
核心难点	① 如何同时保持结构化道路的礼让规则与随机避障能力；② RRT与Lattice之间的切换时机和势能场代价一致性。
面试高频追问	① 你如何量化“结构化/非结构化”阈值？② 两种算法并存时的冲突仲裁策略？③ 如果Lattice输出的轨迹与RRT输出的轨迹方向相反，你怎么做？
可迁移回答话术	“我们在全局层用A生成方向走廊，局部层根据附近障碍物密度动态选择规划器：若横向可用空间>车道宽70%→Lattice，否则切换到RRT。两个规划器共享碰撞检测层，并输出相同格式的轨迹，上层做一次安全再验证。”

🌱 面试进阶指南
本章算法经常以“设计题”出现：给你一个场景（如校园、高速、越野），让你自主选择算法并说明理由。你需要在回答中体现 场景特征（结构化程度、动态性、维度）、算法特性（最优性、完备性、计算开销）、工程组合（哪层用哪个）。多练“混搭方案”的描述。

第三章 搜索算法：A*、Dijkstra、RRT、Lattice Planner 对比与选型