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 archetype of all humans, their ideal image, is the computer, once it has liberated itself from its creator, man. The computer is the essence of the human being. In the computer, man reaches his completion.
    Friedrich Dürrenmatt (1921–1990)

    Science has nothing to be ashamed of even in the ruins of Nagasaki. The shame is theirs who appeal to other values than the human imaginative values which science has evolved.
    Jacob Bronowski (1908–1974)