AI - Heuristic function requirements

3
votes

I have a question about Huristic function in Artificial Intelligence (AI). I know that we should look for monotonic and admissible heuristic function.

I have two questions:

  1. Why is it required that the function will be admissible?

  2. What are the advantages of monotonic heuristic functions?

Thank you!

2
algorithmfunctionsearchartificial-intelligenceheuristics
You're talking about A* specifically, right? - user395760
@ziggystar - Thank you for your "help". - zeevblu
@delnan - Yes. I'm talking about A* - zeevblu
@zeevblu Have you read the wiki page en.wikipedia.org/wiki/Admissible_heuristic? There's also en.wikipedia.org/wiki/Consistent_heuristic. - ziggystar

2 Answers

8
votes

An admissible heuristic is one that provides a lower bound estimate to the goal state.

A monotonic (also known as consistent) heuristic will allow you to implement an optimal A* search efficiently. It guarantees optimality if you visit each state only once.

3
votes

For the admissibility - it gives you a lower bound for the optimal solution.