CODEWITHSUNDEEP
algorithmsearchheuristics
Chris
Chris

Reputation: 3688

A* algorithm with multiple goals

Given a Graph with a set of 5 nodes, 2 of which are goal nodes.

By running the algorithm it finds goal-1 node with a cost of 7 and it terminates.
Although, there's another goal, goal-2, with a cost of 6.

Is, finding the goal-1 as first solution correct? Or the optimal solution is for the A* to find the goal-2 with the cost of 6?

Upvotes: 0

Views: 2870

Answers (1)

UmNyobe
UmNyobe

Reputation: 22890

Is, finding the goal-1 as first solution correct?

Yes correct but not optimal

Or the optimal solution is for the A* to find the goal-2 with the cost of 6?

Indeed

A* rely on a heuristic to perform the search. You should provide different heuristics depending on whether you are performing a "one goal" or "multiple goals" search. If you have an admissible heuristic for one goal it does not mean it is admissible for multiple goals.

Your initial heuristic is h(x) = somedistance(x,g).

The generalized version is h'(x) = min{ somedistance(x,gi), gi in GoalSet }.

Upvotes: 3

Related Questions