课程设计做网格迷宫寻路，用广度优先搜索一层层往外扩，1000 个格子几乎全搜了一遍才碰到终点。换上 A 星之后，搜索像被拽着往终点方向走，扩展的节点少了一大半，差别就在启发式搜索的评估函数上。

给每个节点打个分

启发式搜索的核心是给每个待扩展的节点算一个分值，每次挑分值最优的先走，分值一更新就重新排序，永远先走最有希望的分支。最常用的是 A 星公式：f 等于 g 加 h。g 是从起点走到当前格子的实际代价，h 是当前格子到终点的估计代价，也就是启发函数。

网格地图上，h 常用曼哈顿距离，就是横向格数加纵向格数；允许斜着走就用对角距离或欧氏距离。估价越贴近真实距离，搜索走得越准，展开的节点越少。

h 不高估，结果就是最优

A 星有个好性质：只要 h 不高估真实代价，四方向网格里的曼哈顿距离就满足这一点，找到的第一条路径就是最优路径。要是故意把 h 调大来加快搜索，速度是快了，但不再保证最优，实时性要求高的游戏寻路常这么换。

除了寻路还能干什么

  • 八数码、华容道这类智力题求解，估函数常用错位数
  • 地图导航：路段距离加估计时间做综合评分
  • 游戏 NPC 的移动决策，配合导航网格一起用

和它的对立面比一下更清楚：广度优先、深度优先属于盲目搜索，不利用任何目标方向的信息；启发式搜索把离终点大概还有多远这个经验写进 h，用一点计算换掉了大量无谓的扩展。

实际判断：小地图随便什么搜索都够用；格子数上万、又要频繁重算路径时，直接上 A 星，h 选曼哈顿或对角距离，基本是性价比最高的起点。