CODEWITHSUNDEEP
searchartificial-intelligencea-starheuristics
Brejuro
Brejuro

Reputation: 3541

How is the max of a set of admissible heuristics, a dominating heuristic?

If you have a set of admissible heuristics: h1,h2,h2,...,hn

How is h = max(h1,h2,h2,...,hn) an admissible heuristic that dominates them all?

Isn't a lower h(n) value better?

For A*, f = g + n, and the element with the lowest f will be removed from the list. So shouldn't taking the min give the dominating heuristic?

Upvotes: 0

Views: 3497

Answers (1)

Lars Kotthoff
Lars Kotthoff

Reputation: 109232

An admissible heuristic never overestimates the cost of reaching the goal state. That is, its estimate will be lower than the actual cost or exactly the actual cost, but never higher. This is required for greedy approaches like A* search to find the global best solution.

For example, imagine you found a solution with cost 10. The best solution has cost 8. You're not using an admissible heuristic, and the estimate of the heuristic for the solution that really has cost 8 is 12 (it's overestimating). As you already have a solution with cost 10, A* will never evaluation the best solution as it is estimated to be more expensive.

Ideally, your heuristic should be as accurate as possible, i.e. an admissible heuristic shouldn't underestimate the true cost too much. If it does, A* will still find the best solution eventually, but it may take a lot longer to do so because it tries a lot of solutions that look good according to your heuristic, but turn out to be bad.

This is where the answer for your question lies. Your heuristics h1, ..., hn are all admissible, therefore they estimate a cost equal to or less than the true cost. The maximum of this set of estimates is therefore by definition the estimate that is closest to the actual cost (remember that you'll never overestimate). In the ideal case, it will be the exact cost.

If you were to take the minimum value, you would end up with the estimate that is furthest away from the actual cost -- as outlined above, A* would still find the best solution, but in a much less efficient manner.

Upvotes: 2

Related Questions