Такое свойство соблюдается, если на функцию h(n) налагается дополнительное требование, а именно требование обеспечения преемственности эвристической функции (такое свойство называют также монотонностью эвристической функции). Эвристическая функция h(n) является преемственной, если для любого узла п и для любого преемника л' узла л, сформированного в результате любого действия а, оценка стоимости достижения цели из узла л не больше чем стоимость этапа достижения узла n' плюс оценка стоимости достижения цели из узла n':

Это — форма общего неравенства треугольника, которое указывает, что длина любой стороны треугольника не может превышать сумму длин двух других сторон. В данном случае треугольник образован узлами л, л' и целью, ближайшей к л. Можно довольно легко показать (упр. 4.7), что любая преемственная эвристическая функция является также допустимой. Наиболее важным следствием из определения преемственности является такой вывод: поиск А* с использованием алгоритма Graph- Search является оптимальным, если функция л (л) преемственна.

Несмотря на то что требование к преемственности является более строгим, чем требование к допустимости, весьма нелегко составить такие эвристические функции, которые были бы допустимыми, но не преемственными. Все допустимые эвристические функции, рассматриваемые в данной главе, являются также преемственными. Возьмем в качестве примера функцию. Известно, что общее неравенство треугольника удовлетворяется, если длина каждой стороны измеряется с помощью расстояния по прямой, и что расстояние по прямой между n и n' не больше чем . Поэтому эвристическая функцияявляется преемственной.

Еще один важный вывод из определения преемственности является таковым: если функция h{n) преемственна, то значения функции f(n) вдоль любого пути являются неубывающими. Доказательство этого утверждения непосредственно вытекает из определения преемственности. Предположим, что узел л' — преемник узла л; в таком случае для некоторого а справедливо выражение и имеет место такая формула: