5
\$\begingroup\$

I am currently working on an algorithm that solves a path through the maze. So far I have implemented a Manhattan and Pythagorean Heuristic. I was wondering what makes a heuristic monotonic and how would one go about making a heuristic non-monotonic.

\$\endgroup\$
3

1 Answer 1

2
\$\begingroup\$

A heuristic \$h\$ is monotonic when, in addition to being admissible (meaning the estimate is always equal or lesser to the actual minimum cost) the heuristic satisfies the relation:

$$h(x) <= d(x,y) + h(y)$$

fo all adjacent nodes \$x\$ and \$y\$, where \$d(x,y)\$ is the distance from node \$x\$ to node \$y\$.

More can be found here.

Update: (thanks to ilmari-karonen):
An even better link here:

Consistent (aka *monotonic) heuristics are usually preferred because as each node is reached, consistency guarantees that the path length to that point is equal to the minimal path-length from the start node. This means that a closed-set can be used to avoid expanding nodes more than once.

The most common use of an admissible but not consistent heuristic is when using a bidirectional A*; however in this instance each branch is self-consistent, and so it suffices to expand each node once from each branch.

\$\endgroup\$
4
  • \$\begingroup\$ ...or better yet, here. \$\endgroup\$ Sep 5, 2013 at 22:20
  • \$\begingroup\$ @IlmariKaronen: Comments being intended as temporary, I have incorporated your link in my answers. Thank you. \$\endgroup\$ Sep 5, 2013 at 22:25
  • \$\begingroup\$ I suggest two improvements to this answer: how to make an admissible heuristic monotonic (using pathmax for example), and reason why we want heuristics to be monotonic. \$\endgroup\$ Sep 6, 2013 at 0:13
  • 1
    \$\begingroup\$ "is monotonic when, in addition to being admissible..." - Usually the definition of 'consistent' is given to be just your h(x) <= d(x,y) + h(y) constraint, plus the constraint that h(goal) = 0. Then the heuristic is provably admissible; this form is given because, when proving consistency, it's much easier to show that h(goal) = 0 than it is to show that the heuristic is admissible :) \$\endgroup\$ Sep 6, 2013 at 5:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .