Improve A star algorithm to search multiple goals in a maze

Question

If I have finished implementing the A* algorithm in a maze for finding the shortest path to a single goal(just like the pacman game), how should I improve my current heuristic(manhattan distance to the goal + traveling cost so far from the start) so that my algorithm will support multiple goals in a maze. Basically, I want to find the shortest path to travel through all goals in the maze. In order to make sure the path is optimal, the heuristic function needs to be admissible assuming we ignore consistency in the problem.

I know this is like the traveling salesman problem, but right now I am only dealing with a relatively small amount of data, so I want to keep using the A start algorithm.

Any thoughts are welcome. Thanks!

Answer 1

choose Dijkstra’s algorithm over A*. because A* algorithm cannot be applied to those graphs which have many target nodes. If you have many target nodes and you don't know which one is closest to the main one, A* is not very optimal. This is because it needs to be run several times (once per target node) in order to get to all of them.

ref to : How does Dijkstra's Algorithm and A-Star compare? - Intellipaat Community

Answer 2

A* finds a shortest path from one point to another.

You can't add constraints to allowable paths (e.g., must visit all of these nodes along the way) to A* and expect it to still produce shortest paths.

You can use A* to find the distances (and paths) between the goals and then solve the Travelling Salesman Problem between the goals (using those distances) to figure out the order to visit goals that gets you the shortest overall path.

Answer 3

You could use the distance to the closest goal not already visited; that way it would only become 0 when the last goal has been visited.