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:
“Without being forgiven, released from the consequences of what we have done, our capacity to act would ... be confined to one single deed from which we could never recover; we would remain the victims of its consequences forever, not unlike the sorcerer’s apprentice who lacked the magic formula to break the spell.”
—Hannah Arendt (1906–1975)
“The middle years are ones in which children increasingly face conflicts on their own,... One of the truths to be faced by parents during this period is that they cannot do the work of living and relating for their children. They can be sounding boards and they can probe with the children the consequences of alternative actions.”
—Dorothy H. Cohen (20th century)