Solution

The correct answer is It always finds the solution with the lowest total cost if the heuristic 'h' is admissible. 

Key Points

• A* is a popular algorithm used in pathfinding and graph traversal, which is the process of finding a path between multiple points, called "nodes". It was introduced by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968.
• The main advantage of A* is its ability to dynamically prioritize nodes that seem most likely to lead to the goal, rather than exploring all possible nodes. This is done through a combination of two cost functions, g(n) and h(n):
  • g(n) is the exact cost of the path from the starting point to any node n.
  • h(n) is the heuristic function that estimates the cost from node n to the goal.
• In the context of the A* algorithm, a heuristic is considered admissible if it never overestimates the cost to reach the goal.
• Suppose we are at a particular node and we want to decide which neighbouring node to visit next. A* does this by minimizing f(n) = g(n) + h(n) for the neighboring nodes. g(n) is the actual cost from the start node to the current node and h(n) is the estimated cost from the current node to the goal based on the heuristic.
• The A* algorithm is guaranteed to return the shortest path to the goal if the heuristic it uses satisfies two conditions:
  • It is admissible - that is, it never overestimates the actual cost to get to the goal. This is crucial because if the heuristic overestimates, A* might skip over the optimal path, making it not find the real shortest path.
  • It is consistent (or monotonic) - this means that for every node n and for every successor n' of n, the estimated cost of reaching the goal from n is no greater than the cost of getting to n' plus the estimated cost of reaching the goal from n'. If the heuristic is both consistent and admissible, then A* is guaranteed to find an optimal solution while expanding the fewest nodes possible.

Therefore, the answer to your initial question is that A* is optimal when it always finds the solution with the lowest total cost if the heuristic 'h' is admissible. The other options are not necessarily true.