01
A*算法概述
路径规划问题定义 · A*历史与地位 · 启发式搜索核心思想 · 与Dijkstra、贪心最佳优先对比
基础对比
02
地图建模
栅格地图构建 · 障碍物表示 · 八邻域/四邻域移动代价 · 地图数据结构设计
栅格数据结构
03
启发函数
曼哈顿 · 欧几里得 · 切比雪夫 · 对角线距离 · 数学定义与适用场景
距离启发式
04
核心数据结构
开放列表/关闭列表 · Node类设计 · F=G+H 代价函数详解
Open/CloseFGH
05
算法主循环
初始化 · 循环终止条件 · 节点扩展流程 · 路径回溯(Backtracking)
流程回溯
06
伪代码与流程图
标准伪代码 · 流程图绘制 · 关键步骤代码实现思路
伪代码图解
07
Python实现 (基础版)
Node类 · AStar框架 · get_neighbors · heuristic · search主方法
Python基础
08
Python实现 (可视化)
Pygame/Matplotlib绘制栅格 · 动态搜索过程 · 路径高亮
可视化Pygame
09
性能优化 (一)
heapq优先队列优化Open List · 降低时间复杂度 · 避免重复计算
堆优化
10
性能优化 (二)
打破平局(Tie-breaking) · 权重启发式(Weighted A*) · 双向A*简介
Tie-breaking双向
11
动态障碍物
重新规划策略(D* Lite思想) · 增量式搜索 · 实际处理技巧
动态D* Lite
12
跳点搜索 (JPS)
强迫邻居/跳点核心规则 · JPS vs A* 性能对比 · 适用场景
JPS加速
13
分层A* (Hierarchical A*)
抽象图构建 · 高层/底层规划 · 游戏AI应用
分层游戏AI
14
时间依赖A* (Time-dependent A*)
时间窗口 · 动态代价函数 · 交通导航应用
时间依赖导航
15
多目标A*
多目标优化 · Pareto最优 · NAMOA*变种
多目标Pareto
16
机器人领域应用
ROS导航栈 · 全局/局部规划 · 与DWA配合
ROS机器人
17
游戏AI应用
RTS寻路 · MMO大地图 · NavMesh与A*结合
游戏NavMesh
18
自动驾驶应用
行为/运动规划层 · Lattice Planner结合 · 安全约束
自动驾驶Lattice
19
物流仓储应用
多AGV路径规划 · 冲突解决(预留时间表) · 仓库地图建模
AGV仓储
20
A*的数学基础
图论基础(节点/边/有向/无向) · 搜索树/搜索图 · 可采纳性与一致性
图论可采纳性
21
可采纳启发式
可采纳性定义 · 构造可采纳启发式 · 松弛问题法(Relaxation)
可采纳松弛
22
一致性(单调性)启发式
一致性定义 · 对效率影响 · 三角不等式
一致性单调
23
A*变种 (一)
ARA* · D* · LPA* (Anytime / Dynamic / Lifelong)
ARA*D*LPA*
24
A*变种 (二)
Theta* · Field D* · ANYA (任意角度寻路)
Theta*Field D*
25
A*的局限性
状态空间爆炸 · 内存消耗 · 连续空间不足 · 对启发式依赖
局限挑战
26
A*与其他算法融合
A*+蚁群 · A*+遗传 · A*+强化学习(初步思路)
融合混合
27
工程实践 (一)
大规模地图预处理 · 路径平滑(B样条/贝塞尔) · 路径后处理
平滑后处理
28
工程实践 (二)
多线程寻路 · 缓存机制 · 路径复用 · 性能基准测试
多线程缓存
29
A*调试与测试
单元测试 · 可视化调试 · 常见Bug排查(死循环/非最优)
调试测试
30
课程总结与展望
知识体系回顾 · 未来方向(学习型启发式/神经A*) · 推荐资源
总结展望