Monotonic Function - Monotonicity in Computer Science

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 computer takes up where psychoanalysis left off. It takes the ideas of a decentered self and makes it more concrete by modeling mind as a multiprocessing machine.
    Sherry Turkle (b. 1948)

    The sweetest and most inoffensive path of life leads through the avenues of science and learning; and whoever can either remove any obstructions in this way, or open up any new prospect, ought so far to be esteemed a benefactor to mankind.
    David Hume (1711–1776)