算法札记：A*算法适用的问题
A*算法是一种基于启发式函数的最优路径搜索算法，广泛应用于信息学竞赛中的状态空间搜索问题。其核心在于通过评估函数f(n)=g(n)+h(n)动态权衡已知代价与预估剩余代价，从而高效逼近最优解。
适用问题类型
网格/图结构最短路径
在二维网格或带权图中寻找起点到终点的最小代价路径，如地图导航、迷宫求解。启发函数h(n)常用曼哈顿距离或欧几里得距离，满足可采纳性（admissible）与一致性（consistent）时可保证最优性。滑块拼图类问题（如八数码、十五数码）
每个状态为一个棋盘布局，动作为空格移动。状态空间庞大，BFS效率低，A*通过启发函数（如错位方块数、曼哈顿距离和）显著减少搜索节点数，是OI竞赛经典题型。游戏AI中的角色寻路
在RTS或RPG游戏中，NPC需在复杂地形中避障移动。A*结合预处理地图（如分层ABM）可实现实时高效寻路，是算法工程化落地的典型场景。机器人路径规划
在已知环境地图中，机器人需避开障碍物到达目标点。A*可与栅格化地图结合，适用于离散化环境下的全局路径规划。状态空间搜索问题（状态转移明确、目标可识别）
任何满足以下条件的问题均可建模为A*适用场景：- 状态空间有限或可枚举
- 存在明确的初始状态与目标状态
- 可定义合法操作（边权非负）
- 可构造可采纳且启发性强的 h(n)h(n)
关键约束条件
表格
| 条件 | 说明 | OI竞赛中的体现 |
|---|---|---|
| 可采纳性（Admissible） | h(n)≤h∗(n)，即启发值不超过真实最优代价 | 使用“错位格子数”作为八数码启发函数是可采纳的 |
| 一致性（Consistent） | 对任意节点 n 与后继 n′，有 h(n)≤c(n,n′)+h(n′) | 若 h(n) 满足三角不等式，则无需重复扩展节点，提升效率 |
| 非负边权 | 所有状态转移代价 c(n,n′)≥0 | 所有OI题均默认满足此条件 |
典型竞赛题型示例
NOIP/NOI 历年真题
- 2010年NOIP提高组《运输计划》（部分子任务可用A*优化状态枚举）
- 2015年NOI模拟题《数字迷宫》（带权重的八数码变种）
- 2020年CSP-S模拟题《星际穿越》（多维状态空间+启发剪枝）
常见优化技巧
- 使用优先队列（堆）维护开放列表（Open List）
- 用哈希表记录已访问状态（Closed List）避免重复
- 启发函数设计：优先选择信息量高、计算快的函数（如曼哈顿距离优于欧氏距离，因无需开方）
与BFS/DFS/Dijkstra对比
表格
| 算法 | 是否最优 | 是否高效 | 适用场景 |
|---|---|---|---|
| BFS | 是（无权图） | 低（指数级节点） | 小规模无权图 |
| DFS | 否 | 高（内存少） | 探索性搜索 |
| Dijkstra | 是（有权图） | 中（无启发） | 全图最短路 |
| A* | 是（h可采纳） | 高（有启发） | 状态空间大、有良好启发函数 |
在OI竞赛中，A*常用于状态空间爆炸但启发函数明确的问题，是平衡正确性与效率的黄金选择。
注意事项
- 启发函数设计不当（如高估）会导致非最优解，竞赛中易失分。
- 状态表示需紧凑（如用整数编码棋盘状态），避免内存超限。
- 若状态空间过大（如2048游戏），需结合迭代加深A*（IDA*）降低空间复杂度。
A*算法在OI中不仅是工具，更是建模能力与启发思维的综合体现。掌握其适用边界，是冲击省队乃至国家队的关键技能之一。