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

Question

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

Answer 1

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

相反，如果你试图接触到所有这些人，这本质上是旅行推销员的问题，这是NP-Complete。