algorithm - 当网格图中有多个目标时，如何设计 A* 的启发式？

Question

我面临一个问题，我必须使用 A* 来搜索地图，并且此地图中有多个目标要达到。我的目标是扩展地图中的最少节点，关于如何设计此 A* 算法的启发式有任何想法吗？谢谢

Answer 1

假设“多个目标”意味着您想要达到任何一个目标，只需采取所有启发式方法中的最小值即可。假设您的启发式是一致的，这仍然是一个一致的启发式。

相反，如果您试图触及所有这些问题，这本质上是旅行商问题，即 NP-Complete。