10.2.1. Теорема оптимальности

Эта теорема устанавливает одно свойство алгоритмов, обеспечивающее эффективный поиск оптимального пути. Введем понятие информированного алгоритма. Пусть А и А — алгоритмы упорядоченного поиска, совпадающие во всем, кроме их эвристических функций и соответственно. Будем говорить, что алгоритм А не более информирован, чем А, если для всех узлов

т. е. если А и А оба недооценивают но оценки алгоритма А более точны.

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

В частности, алгоритм А, поступающий в случае совпадения значений так же, как А, будет закрывать только те узлы, которые закрывает А. Множество А оптимально в том смысле, что оно содержит по крайней мере один алгоритм, закрывающий не более узлов, чем любой алгоритм

Хотя само по себе понятие оптимальности интуитивно, теорема менее интересна, чем могла бы быть, судя по названию. В ней утверждается лишь, что если ограничиться множеством допустимых алгоритмов, основанных на „непереоценивающих" истинную величинах стоимости достижения решения из данной точки, то лучший из них — тот, который приводит к наименьшей недооценке.

Короче, теорема оптимальности верна потому, что каждый алгоритм на любом шаге стремится закрыть очередной узел на пути минимальной стоимости. Поскольку А оценивает стоимости путей ниже, чем А, он может исследовать те пути, которые А отбрасывает, но не наоборот. Формальное доказательство мы приводим ниже, причем оно оказывается удивительно утомительным. Хорошее интуитивное представление об алгоритме можно получить, обратившись сразу к примеру.

Доказательство. Сначала нам понадобится лемма.

Лемма 1. Если алгоритм упорядоченного поиска закрывает узлы в порядке то из следует, что

Доказательство. Лемма доказывается индукцией по узлам в том порядке, как они закрываются, т. е.

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

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

Так как к мы пришли от некоторого узла то в силу (15) и (16)

Подставим определение для и применим (26); получим

что доказывает лемму для

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

Поскольку для закрытия мы выбрали вместо

Рассмотрим теперь любой узел который либо отсутствовал в списке ОТКРЫТ, когда закрылся, либо не удовлетворял определению Когда закроется, одним из его предков окажется либо сам либо некоторый узел удовлетворяющий (30) и (31). В первом случае

Во втором случае заменяем в на , применяя (31), находим

Лемма доказана.

Доказательство теоремы. Обозначим через оценки, порожденные алгоритмом А, использующим Поскольку А и А — алгоритмы упорядоченного поиска, то

для всех . Никакой узел не может закрыться алгоритмом, если

где целевой узел на пути минимальной стоимости из

Докажем теорему индукцией по узлам в том порядке, в каком они закрываются алгоритмом А.

Базис индукции. Так как то помещается в список ОТКРЫТ алгоритмами А и А на шаге 1. Поскольку

и алгоритм А должен закрыть то он должен закрыть

Индукция. Предположим, что все узлы до закрыты алгоритмом А и так что А закроет и

Либо , либо — потомок узла, закрытого алгоритмами А и А. В первом случае он содержится в списке ОТКРЫТ с и его следует закрыть. Во втором либо сам узел был помещен в список ОТКРЫТ алгоритмом А, либо такой его предок , что

Следовательно, алгоритм А должен закрыть либо узел либо одного из его предков, прежде чем закроет и закончит работу. Алгоритм А должен занести в список , будучи там,

узел и] должен закрыться раньше, чем Поэтому возможен только случай равенства

В этом случае А либо выберет для закрытия и закончит работу, либо сделает неверный выбор. Это будет зависеть от правила поведения в случае совпадения значений. Если А делает неверный выбор, то А содержит другой алгоритм А, во всем совпадающий с А, но применяющий правила поведения из А.

Пример. Алгоритм упорядоченного поиска может улучшить поиск решения даже при использовании грубой эвристики. Чтобы убедиться в этом, рассмотрим снова задачу нахождения пути от Сан-Франциско к Лос-Анджелесу согласно следующей процедуре:

1. Если общее направление пути — на север, ток равняется половине пути, пройденного к северу.

2. Если общее направление пути — на восток, то равняется четверти пройденного пути.

3. Если общее направление пути — на юг, то .

Решение достигается так (оценка заменена на ):

(см. скан)

Решение находится на следующем шаге. Открыты только пять узлов вместо шести, открытых методом равных цен.

В сложных транспортных задачах использование лишь немного более сложных эвристических функций дает потрясающие результаты. Примером служит задача нахождения пути для вездехода. Пусть он находится в точке х и стремится прийти в точку у. Вездеход может двигаться с разными скоростями по проселочным дорогам, полям, бездорожью. Требуется как можно скорее попасть из в у. Поскольку — эвристическая функция, определим ее как время движения из точки по наилучшей возможной дороге в предположении, что соответствующий прямой путь существует. Эта эвристика использовалась при исследовании тактического планирования с помощью ЭВМ для движения военных подразделений, причем оказалось, что она сокращает время работы программы в 100 раз, а в некоторых случаях и больше.