Consequences of Monotonicity
Consistent heuristics are called monotone because the estimated final cost of a partial solution, is monotonically non-decreasing along the best path to the goal, where is the cost of the best path from start node to . It's necessary and sufficient for a heuristic to obey the triangle inequality in order to be consistent.
In the A* search algorithm, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that Dijkstra's algorithm requires in solving the shortest path problem (no negative cost cycles). In fact, if the search graph is given cost for a consistent, then A* is equivalent to best-first search on that graph using Dijkstra's algorithm. In the unusual event that an admissible heuristic is not consistent, a node will need repeated expansion every time a new best (so-far) cost is achieved for it.
Read more about this topic: Consistent Heuristic
Famous quotes containing the words consequences of and/or consequences:
“Cultivate the habit of thinking ahead, and of anticipating the necessary and immediate consequences of all your actions.... Likewise in your pleasures, ask yourself what such and such an amusement leads to, as it is essential to have an objective in everything you do. Any pastime that contributes nothing to bodily strength or to mental alertness is a totally ridiculous, not to say, idiotic, pleasure.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“War is thus divine in itself, since it is a law of the world. War is divine through its consequences of a supernatural nature which are as much general as particular.... War is divine in the mysterious glory that surrounds it and in the no less inexplicable attraction that draws us to it.... War is divine by the manner in which it breaks out.”
—Joseph De Maistre (1753–1821)