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

⇐ ПредыдущаяСтр 29 из 32Следующая ⇒

Оценочная функция позволяет упорядочить вершины в списке ОТКРЫТ таким образом, чтобы первые позиции в нем занимали вершины с минимальной величиной оценки. Обозначим через 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

e	0, 01	0, 05	0, 1	0, 15	0, 25	¥
Стоимость результирующего пути	100.1	100.4	101.1	101.9	103.0	107.0
число раскрытых вершин
число возвратов

3.4.2.3. (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, г).

⇐ Предыдущая 23 24 25 26 27 282930 31 32 Следующая ⇒