Monotonicity in Computer Science
In computer science, monotonicity (also called consistency) is a condition applied to heuristic functions. A heuristic h(n) is monotonic if, for every node n and every successor n' of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' plus the estimated cost of reaching the goal from n' ,
This is a form of triangle inequality, with n, n', and the goal Gn closest to n. Because every monotonic heuristic is also admissible, monotonicity is a stricter requirement than admissibility. In some heuristic algorithms, such as A*, the algorithm can be considered optimal if it is monotonic.
Read more about this topic: Monotonic Function
Famous quotes containing the words computer and/or science:
“The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower.”
—Robert M. Pirsig (b. 1928)
“Consider the China pride and stagnant self-complacency of mankind. This generation inclines a little to congratulate itself on being the last of an illustrious line; and in Boston and London and Paris and Rome, thinking of its long descent, it speaks of its progress in art and science and literature with satisfaction.... It is the good Adam contemplating his own virtue.”
—Henry David Thoreau (1817–1862)