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.
\$\begingroup\$
\$\endgroup\$
3
-
\$\begingroup\$ You could ask this on SO. \$\endgroup\$– ziggystarCommented Sep 5, 2013 at 11:41
-
\$\begingroup\$ possible duplicate of Is the Manhattan distance monotonic when used as heuristic function? \$\endgroup\$– BlueRaja - Danny PflughoeftCommented Sep 5, 2013 at 14:51
-
1\$\begingroup\$ May I ask why you want to know how to make a heuristic non-monotonic? Or is it the opposite you're after: how to make a heuristic monotonic? \$\endgroup\$– congusbongusCommented Sep 6, 2013 at 0:11
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
4
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.
-
-
\$\begingroup\$ @IlmariKaronen: Comments being intended as temporary, I have incorporated your link in my answers. Thank you. \$\endgroup\$ Commented 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\$ Commented 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 thath(goal) = 0. Then the heuristic is provably admissible; this form is given because, when proving consistency, it's much easier to show thath(goal) = 0than it is to show that the heuristic is admissible :) \$\endgroup\$ Commented Sep 6, 2013 at 5:21