无距离信息时使用A*算法，应选择何种启发式函数？

要让A算法找到从X到Y的最短路径，核心要求是你选的启发式函数绝对不能高估任意节点到Y的实际最短路径长度（业内叫“可采纳性”），满足这个条件的A才能保证给出最优解。下面分场景给你具体方案：

• 只有邻接关系、无额外信息的普通图
  这种情况没什么额外数据可以用，最稳妥的就是设h(n)=0——这时候A*就退化成Dijkstra算法，虽然没启发加速，但肯定能找到最短路径。如果能从业务逻辑里抠出某个节点到Y的最小步数下界（比如明确知道节点n至少要走3步才能到Y，且这个数绝对不会比实际步数大），也可以用这个数当h(n)，能稍微加快搜索速度。

• 带坐标的图（比如网格、地理节点）
  如果每个节点有坐标信息，常用的靠谱启发式有这几种：

  • 曼哈顿距离：适合只能沿上下左右走的网格，公式是h(n) = |x_n - x_Y| + |y_n - y_Y|，算出来的距离肯定不会比实际路径长。
  • 欧几里得距离：适合能任意方向移动的场景（比如地图上的直线距离），公式是h(n) = sqrt((x_n - x_Y)^2 + (y_n - y_Y)^2)，同样不会高估实际路径长度。
  • 切比雪夫距离：适合能走对角线的网格，公式是h(n) = max(|x_n - x_Y|, |y_n - y_Y|)，符合可采纳性要求。

• 边带权重的图（不同路径消耗不一样）
  如果边的权重不是统一的，启发式要基于最小边权来算下界。比如所有边里最小的权重是w_min，那h(n)可以设成w_min * 节点n到Y的最少步数，这样算出来的h(n)肯定不会超过实际最短路径的总权重，满足可采纳性。

另外提一句：如果不在乎是不是最短路径，只想快点找到一条路径，可以用高估距离的启发式，但这样A*就没法保证最优解了。但你的目标是最短路径的话，一定要守住“不高估”这个底线。

内容的提问来源于stack exchange，提问作者Gil Kor