Стратегии поиска на основе эвристической функции оценки

Оценочная функция позволяет упорядочить вершины в списке ОТКРЫТ таким образом, чтобы первые позиции в нем занимали вершины с минимальной величиной оценки. Обозначим через f(n)значение оценочной функции на вершине n. Функция f(n)определяет оценку стои­мости наилучшего (т.е. имеющего минимальную суммарную стоимость) пути, соединяющего вершину n с начальной вершиной и целевой верши­ной.

Теперь алгоритм поиска решения - как маршрута в графе состоя­ний задачи, связывающего начальную и целевую вершины, на основе функции f(n) принимает следующий вид:

(1) Занести начальную вершину s в список ОТКРЫТ и вычислить f(s).

(2) Если список ОТКРЫТ пуст, то алгоритм завершается общей не­удачей; иначе - следующий шаг.

(3) В списке ОТКРЫТ выбирается вершина х с минимальным значением f(s).

(4) Если х - целевая вершина - то конец; иначе построить мно­жество Г(x). Для каждой вершины y Î Г(x) найти f(y). Если вершина у отсутствует в списке ОТКРЫТ, то поместить ее туда с найденным значением f(у). Если у уже входит в список ОТ­КРЫТ, то установить для у то из значений f(у), которое мини­мально.

(5) Перейти к п. (2).

Приведенный алгоритм известен в литературе как алгоритм А*. Нетрудно догадаться, что выбор оценочной функции является решаю­щим для эффективности алгоритма поиска. Определим оценочную фун­кцию f(n) в виде суммы

f(n) = g(n) + h(n), (3.12)

где g(n) - стоимость наилучшего пути, найденного для вершины n, ко­торый связывает ее с начальной вершиной; h(n)- стоимость оптимального пути от вершины n до целевой вершины.

Кроме того, пусть - оценка для g(n), - оценка для h(n)и - оценка для f(n),т.е.

(3.13)

Из определения g(n) имеем, что ³ g(n).

Отметим, что определение g(n)в общем случае не вызывает затруд­нений. Для функции дело обстоит иначе. Однако если представ­ляет нижнюю границу для h, то алгоритм А* находит маршрут с мини­мальной общей стоимостью. Теореме, устанавливающей это свойство алгоритма А*, предпочтем следующую лемму.

Лемма. Если для всех n выполняется условие ,то в любой момент времени до того, как алгоритм А* закончит свою работу, на лю­бом оптимальном пути Р от начальной вершины s к цели существует от­крытая вершина n', для которой f(n') £ f(s).

Доказательство. По определению .

Так как n' лежит на оптимальном пути, то и, следова­тельно, ,ибо мы приняли, что .

Далее имеем, что для любых двух вершин х₁ и х₂, лежащих на оп­тимальном пути f(x₁) = f(x₂) = f(s). В самом деле, пусть х₁ расположена до х₂ в оптимальном пути. Тогда

f(x₁) = g(x₁) + j(x₁, x₂), (2.14)

где j(x₁, x₂) - стоимость оптимального пути от х₁ к х₂.

но, очевидно, j(x₁, x₂) + h(x₂) = h(x₁)и g(x₁) + j(x₁, x₂) = g(x₂).

Отсюда следует, что .

Теорема 2.1.Если для всех вершин n выполняется условие и если стоимости всех дуг превосходят некоторое малое положительное число d, то алгоритм А* оканчивает свою работу построе­нием оптимального пути к цели.

Доказательство. Возможны три различных исхода.

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

Исход 2: Алгоритм не оканчивает работу. Эта ситуация невозможна если множество всех состояний задачи конечно. Допустим против­ное: граф конечен, но алгоритм не завершает работу. Это значит, что список ОТКРЫТ никогда не опустеет, т.е. в него будут попадать одни и те же вершины, для которых значение f(х) все время уменьшается. Каж­дый такой случай соответствует обнаружению нового, более лучшего пути из s в х. Но число всех таких путей в конечном графе ограничено, из чего следует противоречие.

Исход 3: Алгоритм завершает работу на целевой вершине, но найденный маршрут не оптимален. Допустим, что работа алгоритма А* оканчивается на некоторой вершине t с . Однако по лемме выше как раз перед окончанием работы на оптимальном пути существует такая вершина n',что f(n') £ f(), поэтому была бы выбрана для раскрытия не вершина t, а вершина n'.

Говорят, что эвристическая функция h удовлетворяет монотонному ограничению, если для любых вершин х и у, таких что у Î Г(х) имеет место h(x) ³ h(y) + c(x, y), где с(x, у) - стоимость дуги, связывающей вершины х и у.

Теорема 2.2. Если функция h удовлетворяет монотонному ограниче­нию, то А* оптимален.

Доказательство. Найдем

.(3.15)

Тогда примем для каждой вершиных .(3.16)

Ясно, что для всех х. В силу теоремы 2 А* оптимален.

Несмотря на то, что алгоритм А* находит маршрут минимальной стоимости, он имеет экспоненциальный характер. Поэтому естественны попытки ускорить сходимость процедуры поиска ценой потери оптимальности. В этой связи рассмотрим подход Галлаба и Алларда, предло­живших эвристический алгоритм А_e, ускоряющий сходимость процесса.

Алгоритм А_e придерживается стратегии поиска в глубину, раскры­вая вершины, принадлежащие одному и тому же пути, пока это возмож­но. Считается, что вершина n допустима, если f(n)не превосходит величины (1 + e) max {f(n')}, где n' принадлежит множеству вершин, бывших первыми в списке ОТКРЫТ.

Другое отличие между А* и А_e заключается в том, что если для рас­крываемой вершины n Г(n)не содержит допустимой вершины, то А_e пытается раскрыть вершины из Г(n),затем вершины из Г(Г(n))и т.д. несколько раз, предполагая, что в силу монотонности h с увеличением f(n')некоторые вершины перейдут из разряда недопустимых в разряд допустимых.

Алгоритм А_e :

1. Список ОТКРЫТ = {s}.

Список ЗАКРЫТ = Æ

g(s) = 0; f(s) = h(s)

верхняя граница = (1 + e) f(s)

РАСКРЫТЬ (s)

АХ = {x Î Г(s)¦ x допустима}

x допустима, если x Î ОТКРЫТ и f(x) £ верхняя_граница

2. Если АХ ¹ Æ, то n = выбрать (АХ) иначе n = выбрать (ОТКРЫТ)

3. РАСКРЫТЬ (n).

4. Если Г(n) не содержит допустимых вершин, то строить Г(Г(n)), Г(Г(Г(n)))... и т.д. до тех пор, пока не будет получена вершина t, являющаяся допустимой или список ОТКРЫТ не станет пустым; или число последовательных применений операции раскрытия Г...Г не станет больше некоторого порогового значения N

РАСКРЫТЬ (t)

5. АХ = {x Î Г(n)¦ x допустима}

6. Если целевая вершина найдена и допустима, то конец.

Если ОТКРЫТ = Æ, то общая неудача,

иначе

вычислить_новую_верхнюю_границу и повторить с п. 2.

Процедура выбрать (АХ) выбирает в множестве АХ вершину х с минимальным значением f(х);

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

При этом такой выбор должен минимизировать функцию

a₁ × f(x) + a₂ × h(x) (3.17)

Выбор a₁ и a₂ определяется из следующих соображений. Миними­зация h(х) "ориентирована" на скорейшее приближение к целевой вер­шине, однако увеличивает риск возврата с выбранного пути к верши­нам на более высоком уровне в графе решения. Минимизация f(х) максимально увеличивает верхнюю границу (1 + e) f(x), т.е. увеличивает пе­ребор. Практически рекомендовано устанавливать значение a₁ > a₂. Следующие результаты получены для задачи о коммивояжере для N = 9 городов (табл. 3.1).

Из табл. 2.1 видно, что при e = О результирующий путь имеет мини­мальную стоимость (100), но и максимальное число раскрытых вершин (100). С увеличением происходит сокращение числа раскрытых вершин. При e = 0.25 было раскрыто всего 23 вершины и сделано 3 возврата, что практически на порядок меньше, чем при e = О. При этом относительная потеря точности результата составляет 3%.

Таблица 3. 1

A - b)-процедура

Рассмотрим граф состояний, в котором все множество состояний делится на два непересекающихся класса U_a и U_b. Будем считать, что в каждом состоянии а из U_a игрок a выбирает допустимый переход в не­которое состояние из U_b, причем Г(а)ÍU_b; наоборот, в каждом состоя­нии b из U_b игрок b выбирает некоторый допустимый переход в одно из состояний Г(b)ÍU_a. Считается, что выигрывает тот игрок, который своим последним ходом исключает возможность сделать очередной ход противнику, т.е. у противника отсутствует допустимый ход в заключи­тельном состоянии.

Стратегия называется выигрышной для игрока a, если независимо от ответного хода противника игра заканчивается в ситуации, выиг­рышной для a.

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

Будем полагать, что игроки a и b оценивают ситуации таким образом, что для любой ситуации х оценка a(х) = 1 - b(х), a(х) + b(х) = 1.

Из этого допущения следует, что стремление каждого игрока до­биться лучшей для себя ситуации означает адекватное ухудшение соот­ветствующей оценки противника. Очевидно, разумная тактика у игрока a заключается в стремлении получить гарантированный минимальный выигрыш на каждом шаге, т.е. строить игру, исходя из допущения, что игрок b придерживается каждый раз своей наилучшей стратегии.

Пусть х - текущая ситуация, в которой ход делает игрок a. Тогда он может выбрать любую вершину из множества Г(х). Допустим, он вы­брал вершину у*ÎГ(х). Теперь, в свою очередь, игрок b может выбрать любую вершину из Г(у*). Очевидно, игрок b выберет из Г(у*) ту вершину z*, которая доставляет максимальное значение величине b(z*). Следовательно, игрок a должен выбором вершины у* гарантировать

(3.18)

С другой стороны, игрок а стремится максимизировать минималь­ный выигрыш независимо от выбора игрока b , т.е.

(3.19)

Убеждаемся, что (2.19) вытекает из (2.18) в силу того, что a(х) ~ minb(x).Теперь ясно, что оптимальная стратегия игрока a должна га­рантировать соблюдение для каждого состояния х условия

W^a(x) ³ U^b(x) (3.20)

Стратегия со свойством (2.20) называется оптимальной для игрока a. Оценка (2.20) позволяет отсечь те направления, для которых с учетом возвращаемого игроком b значения U^b(х), соотношение (2.20) не выполняется.

Первоначальный граф представлен на рис. 3.5.

Удалим дуги x₆ x₅, x₃ x₅, согласно операции О₂ (рис. 3.6,а).

Согласно операции О₃ удаляем вершину x₈ вместе с инцидентными ей дугами. (рис. 3.6,б).

Согласно операции О₆ удаляем альтернативную вершину x₂ вместе с инцидентными ей дугами.

По О₅ пометка 4 снимается со всех дуг, входящих в x₆ и x₄ и пометка 5. Следовательно, удаляются дуги x₅ x₆, x₅ x₄ и x₇ x₄ (рис. 3.6,в).

Согласно операции О₆ удаляем альтернативную вершину x₄ вместе с инцидентными ей дугами.

По О₅ пометка 6 снимается со всех дуг, входящих в x₆. Следовательно, из дуг x₁ x₆ и x₃ x₆ (рис. 3.6,г).