CODEWITHSUNDEEP
algorithmartificial-intelligencea-starheuristics
photosynthesis
photosynthesis

Reputation: 2890

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

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

Upvotes: 3

Views: 1080

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

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.

Upvotes: 8

Related Questions