10.2. Оптимальный алгоритм упорядоченного поиска

10.2.0. Определение эвристической функции

Нильсон предлагает при осуществлении упорядоченного поиска определять формулой

Он называет эвристической оценкой, соответствующей наиболее точному при данной информации о некоторых особенностях узла представлению о трудности достижения из Такое определение интуитивно оправдано, поскольку, если все наши оценки точны, мы получим и функция

очевидно, будет оптимальной. Заметим, что в определении (13) предполагается, что трудность решения задачи при данном частном решении (т. е. приходе в узел не зависит от способа достижения частного решения.

Нильсон показал также, что некоторые интуитивно обоснованные ограничения на приводят к интересным результатам. Пусть — стоимость кратчайшего пути из где ни ни не должны принадлежать ни ни Потребуем, чтобы выполнялись неравенства

Поскольку - „истинная стоимость" перехода от к первое ограничение означает, что оценка стоимости перехода от неотрицательна и не превышает истинной. Неравенство (16) означает, что подобное ограничение, препятствующее завышению оценки, применяется к стоимости любого участка решающего пути.

Алгоритм называется допустимым, если решение, которое он находит, имеет минимальную стоимость. В следующей теореме доказывается, что применение формулы (13) в процедуре упорядоченного поиска определяет допустимый алгоритм.

Теорема об упорядоченном поиске. Алгоритм упорядоченного поиска, использующий функцию определенную формулой (13), где подчиняется ограничениям (15) и (16), допустим.

Доказательство. Алгоритм не может закончить работу до тех пор, пока либо не будет достигнута цель, либо не будут закрыты все потомки узлов, принадлежащих Таким образом, если решение существует, оно будет найдено.

По определению для любого узла Тогда, согласно (14), Пусть узел помещен в список ОТКРЫТ после закрытия некоторого узла Тогда

Впоследствии изменится, только если закроется такой узел что

Здесь нам понадобится одна лемма.

Лемма 1. При выполнении условий теоремы

В лемме 1 утверждается, что при закрытии узла определяется его путь минимальной стоимости из 50. Справедливость леммы для случая для всех уже показывалась: это метод равных цен. Докажем ее для общего случая.

Доказательство. Пусть узел, который должен быть закрыт, множество узлов в списке ОТКРЫТ в это время. После закрытия путь к нему с меньшей стоимостью можно было бы обнаружить, только если бы был закрыт такой узел что и

Покажем, что это невозможно.

Кратчайший путь от не может содержать в качестве промежуточного узла. Допустим противное. Если при закрытии узла он является потомком узла то

а это противоречит неравенству (19).

Если при закрытии узла он не является потомком узла то он должен быть потомком такого узла который не может быть потомком узла Более того, при, закрытии его новая оценка не должна оказаться ниже той, что была после закрытия так как обратное противоречило бы предположению о том, что а значит, и не являются потомками узла Поэтому

В силу (16)

Поскольку узел был закрыт перед то Отсюда

Заменяя левую часть в (23) на левую часть в (21) и вычитая из обеих частей, получаем

Таким образом, величина должна быть минимальной, т. е. должна равняться при закрытом узле Лемма доказана. Непосредственное применение леммы показывает, что, когда некоторый узел закрыт, т. е. установлена стоимость кратчайшего пути к этому целевому узлу.

Осталось показать, что будет выбираться целевой узел, ближайший к Применяя лемму 1, получаем, что ни один целевой узел не будет закрыт, пока не будут закрыты прямые предки на пути минимальной стоимости. Более того, по условию (15) при закрытии любого предка целевого узла стоимость пути между предком и ближайшим целевым узлом не завышена. Поскольку все узлы из в некоторый момент содержатся в списке ОТКРЫТ, ясно, что туда занесен или целевой узел на пути минимальной стоимости с оценкой , или некоторый его предок. В первом случае

закроется раньше любого другого целевого узла из списка ОТКРЫТ, во втором раньше закроется его предок; при этом или один из его более близких предков помещается в список ОТКРЫТ, и ситуация повторяется. Поэтому никакой целевой узел не будет закрыт до закрытия и алгоритм должен найти путь минимальной стоимости.