Монотонное ограничение. 
Символический искусственный интеллект: математические основы представления знаний

Говорят, что функция h удовлетворяет монотонному ограничению (или неравенству треугольника), если.

где г — правило для перехода из узла d в узел r.f (d).

Другими словами, эвристическая функция локально согласована с весом дуг (правил).

Теорема 3.3. Если выполнено условие состоятельности, оценочная функция удовлетворяет монотонному ограничению и существует оптимальный путь, то алгоритм А* всегда выбирает для раскрытия узел, к которому уже найден оптимальный путь, т. е.

Доказательство. Индукция по длине оптимального пути.

База индукции: g (d₀) =g'(d_(}) = 0. Индукционный переход. Пусть выбран для раскрытия узел d*d₀ и пусть А = d₀, d_x,…, d,…, d — оптимальный путь. Имеем.

по монотонному ограничению. Далее Имеем

и по транзитивности.

Пусть теперь d_k — самый левый открытый узел на пути А, т. е. d_k е А, d_k е О и /j е С. Такой узел существует, гак как d₀ е С, d е О. Все вершины на пути А левее d_k, т. е. все закрытые вершины, предшествующие d_!t на пути А, уже раскрыты, значит g (d_k) = g'(d_k).

Поскольку алгоритм А' при раскрытии очередного узла из двух узлов d и dj. выбирает узел d, то F (d) < F (d_k). Итак, имеем.

g (d) + h (d) = F (d) < F{d_k) = g{d_k) + h (d_k) = g*(d_k) + h (d_k) Следовательно, g (d) Ho /d g (d) >g*(d) и, значит, g (d) = g*(d),

ч.т.д.

Следствие. Если оценочная функция удовлетворяет монотонному ограничению, то последовательность значений оценочной функции для выбираемых узлов не убывает.

Доказательство. Пусть раскрыты узлы d_x, d₂ (подряд). Если в момент раскрытия узла d_x уже d₂ е О, то по построению А* имеем F (d_x) < F (d₂).

Иначе d₂ должен попадать в О при раскрытии d_x. Имеем: F (d₂) = g (d₂) + + h (d₂) = gd₂) + h (d₂) = gd_x) + w (d_b d₂) + h (d₂) = g (d_x) + w (d_x, d₂) + + h (d₂) >g (d_x) + h (d_x) = F{d_x), ч.т.д.