How to design the heuristic for A* when there are multiple goals in the grid map?

Question

I am facing a problem that I have to use A* to search through the map, and there are multiple goals in this map to reach. My aim is to expand the least nodes in the map, any idea on how to design the heuristic for this A* algorithm? thanks

Answer 1

Assuming by "multiple goals" you mean you want to reach any one, just take the minimum of all the heuristics. Assuming your heuristic is consistent, this is still a consistent heuristic.

If instead you're trying to reach all of them, this is essentially the traveling salesman problem, which is NP-Complete.