Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 15

Рассмотрим простой пример игры в крестики-нолики на поле 3*3. Игроки поочередно ставят крестик либо нолик в клетках поля. Выигрывает тот, кто получит 3 крестика либо нолика подряд по горизонтали, вертикали либо диагонали.

Построим сначала статическую оценочную функцию. Пусть M – сумма числа строк, столбцов и диагоналей, которые при данной позиции теоретически могут быть заняты игроком КРЕСТИК, а N – аналогичная величина для игрока НОЛИК. Примем за оценку позиции значение F = M – N.

Например, для позиции (.....)

игрок КРЕСТИК потенциально может занять строки 2, 3, столбцы 1, 3 и обе диагонали, то есть M = 6, а игрок НОЛИК может занять строки 1, 3 и столбцы 1, 3, то есть N = 4. Таким образом позиция оценивается величиной F = M – N = 2.

Можно проверить, что если придерживаться принципа минимакса, пользоваться описанной функцией оценки и строить дерево игры на свой ход и ответ противника, то есть на 2 уровня, то первый ход игрока должен быть сделан в центр поля. Для игрока КРЕСТИК этот ход имеет оценку 1, тогда как ход в угол поля оценивается величиной –1, а ход в середину крайней строки или столбца величиной –2.

Описанная функция оценки далеко не всегда соответствует лучшему ходу. Пусть, например, в позиции, соответствующей корню дерева, очередь хода за игроком КРЕСТИК. В скобках проставлены оценки позиций после возможных ходов.(.....)

Позиция E имеет самую низкую оценку, но она выигрышная (как и D), а позиции A, B и C – ничейные, хотя и имеют более высокие оценки.

8.4. α – β отсечение

Для отсечения бесперспективных вариантов в игровых программах используется процедура α – β отсечения, использующая идеи метода ветвей и границ. Пусть имеется дерево игры и построена функция оценки, наибольшие значения которой определяют ход игрока ПЛЮС.

Допустим, что некоторая вершина дерева соответствует ходу игрока ПЛЮС. Оценка для нее вычисляется как

a = MAX (a₁, a₂, …, a_n) ,

где a₁, a₂, …, a_n – значения функции оценки в сыновьях этой вершины. Пусть нашли некоторое значение a_i. Тогда a ≥ a_i, то есть величина a_i определяет нижнюю границу для a, называемую α – значением. Эту границу можно использовать для отсечения некоторых ветвей дерева игры.

Аналогично для вершины, соответствующей ходу игрока МИНУС, оценка вычисляется как

b = MIN (b₁, b₂, …, b_m) ,

где b₁, b₂, …, b_m – значения функции оценки в сыновьях. После нахождения любого значения b_j получаем, что b≤ b_j, то есть величина b_j определяет верхнюю границу для b или β – значение.

Рассмотрим процедуру α – β отсечения на примере. На рисунке показан фрагмент дерева игры. Как и раньше, приведены оценки с точки зрения игрока ПЛЮС. Вершины дерева, соответствующие ходу игрока ПЛЮС, показаны квадратиками, а игрока МИНУС – кружками. Для игрока ПЛЮС оценка вершины определяется как максимум оценок сыновей, а для игрока МИНУС – как минимум. Корню соответствует текущая позиция. В листьях указаны статические оценки соответствующих позиций.(......)

Оказывается, что весь этот фрагмент дерева игры строить необязательно. Рассмотрим поэтапно процесс распространения оценок снизу вверх по дереву.

1. После получения показанных на рисунке оценок в листовых вершинах a, b и c получаем в вершине D оценку 3. Значит, в вершину p поднимется оценка ≤3.

2. Оцениваем вершины d и e. После получения оценки 5 в вершине f можно заключить, что в вершине H будет оценка ≥5, то есть вершина H не сможет оказать влияние на оценку вершины p. Отсюда других сыновей вершины H (на рисунке f) можно не рассматривать. Значит, имеет смысл строить дерево в процессе оценок, а не заранее.

3. Аналогично получив в вершине h оценку 4, заключаем, что в вершине L будет оценка ≥4, поэтому вершины k и l можно не рассматривать. Это примеры β – отсечения, так как рассматривались сыновья вершины p, в которой оценка находится по минимуму оценок сыновей. Таким образом, в вершине p устанавливается окончательная оценка 3.

4. Оцениваем вершины n, o и p, получая оценку 2 в вершине B. Значит, в вершине q оценка ≤2.

5. Нас интересует оценка в корне. Для него определяется максимум из оценок сыновей, но в вершине p уже достигнуто значение 3. Значит, вершина q с оценкой ≤2 не может оказать влияние на оценку корня, поэтому в корень поднимается оценка 3. Вершины S и T со всеми своими сыновьями можно не рассматривать, а соответствующие части дерева игры не строить вообще. Это примеры α - отсечения.

Оценки вершин a, b и c сказались на 2 уровня выше, как и оценка q. Процедура α – β отсечения позволяет, например, в шашках сократить объем вычислений в 4-6 раз.

Эффективность процедуры зависит от порядка перебора вершин. Например, перебирая вершины в порядке d, e, f, h, k, l, a, b, c, для вершины p получали бы последовательно ограничения ≤5, ≤4, ≤3, то есть β – отсечения не было бы совсем. Поэтому важно как можно раньше получать удовлетворительный ход, что возможно на основе дополнительной информации об игре. Опытный игрок вообще не рассматривает бесперспективные варианты.

Методы теории вероятности позволяют распространить описанные подходы и на недетерминированные игры.

Не стоит думать, что подобные игровые модели имеют значение только в развлекательных целях. Существует, например, класс так называемых "игр с природой”, когда необходимо принимать решения, позволяющие добиться наибольшей выгоды, избегая риска катастрофических последствий. Другой вид игр – противодействие (ответные ходы) попыткам доступа к конфиденциальной информации.

8.5. Динамическое программирование

Динамическое программирование – это особый способ оптимизации, специально приспособленный к так называемым "многошаговым” операциям, в частности к задачам перебора вариантов. Предположим, что эффективность операции определяется функцией стоимости, которая складывается из стоимостей на отдельных шагах, то есть

F (a₁, a₂, …, a_m) = С(a₁) + С(a₂) +…+ С(a_m),

где С(a_i) – функция, определенная для всех a_i. Показатели такого вида называют аддитивными. Требуется найти такой набор (a₁, a₂, …, a_m), чтобы стоимость была минимальной (максимальной).

Рассмотрим примеры многошаговых операций.

1. Руководитель предприятия намерен эксплуатировать некоторый аппарат в течение m лет. В начале каждого года он может принять одно из трех решений:

1. продать аппарат и заменить его новым;

2. провести капитальный ремонт и продолжить эксплуатацию;

3. продолжить эксплуатацию без капитального ремонта.

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

Стоимость складывается из годовых затрат. Решение представляет из себя комбинацию чисел 1, 2 и 3. Например, (3, 3, 2, 2, 2, 1, 3, …) означает: первые 2 года эксплуатировать аппарат без ремонта, последующие 3 года производить ремонт, в начале шестого года продать, купив новый, затем снова эксплуатировать без ремонта и т. д.

2. Планируется деятельность промышленных предприятий B₁, B₂, …, B_k на m лет. В начале периода на развитие всей группы предприятий выделены средства в размере S единиц. В процессе работы предпрятия вложенные в него средства частично расходуются, а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств нужно выделять каждому предприятию, чтобы суммарный доход за m лет был максимальным ?

Суммарный доход представляет собой сумму доходов на отдельных шагах (годах). На каждом i-ом шаге предприятиям выделяются некоторые средства a_i1, a_i2, …, a_ik (первый индекс – номер шага, второй – номер предприятия), то есть a_i = (a _i1, a _i2, …, a _ik). Таким образом, элементы a_i представлят собой вектора.

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

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

Планируя последний шаг, нужно рассмотреть все возможности того, чем кончился предпоследний (m-1)-й шаг, и для каждой такой возможности найти наилучший вариант последнего шага. В динамическом программировании это называют условным оптимальным управлением, так как оно выбирается из условия, что предпоследний шаг закончился определенным образом. Затем находят условное оптимальное управление на (m-2)-м шаге и т. д., пока не доходят до первого шага, на котором находится уже истинное оптимальное управление, минимизирующее функцию стоимости. Сейчас двигаясь от начала к концу, на каждом i-ом шаге находят наилучшие значения a_i.

Таким образом, многошаговый процесс проходится дважды: первый раз от конца к началу, в результате чего находятся условные оптимальные управления и соответствующие условные оптимальные значения за оставшийся "хвост” процесса, а второй раз от начала к концу, когда остается "вспомнить” уже готовые рекомендации и найти оптимальные значения элементов a_i. Первый этап несравненно сложнее и длительнее второго, который почти не требует дополнительных вычислений.

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

Пусть, например, прямоугольник (квадрат) заполнен следующим образом:

	A	B	C	D	E
1	25	21	-10	14	9
2	-15	18	4	12	-1
3	10	14	7	8	14
4	6	6	3	18	-11
5	8	2	6	9	8

Для удобства клетки обозначаются аналогично шахматам: буквами по горизонтали и цифрами по вертикали. Результаты прохода от конечной клетки к начальной показаны ниже.

	A	B	C	D	E
1	59 ►	34 ►	13 ►	23 ►	9
2	20 ►	35 ►	▲ 17	20 ►	▲ 8
3	▲ 30	38 ►	▲ 24	▲ 28	▲ 22
4	▲ 36	33 ►	▲ 27	29 ►	▲ 11
5	43 ►	▲ 35 ►	▲ 33	28 ►	▲ 19

Направление лучшего хода отмечено символами "►” и "▲”. В каждой клетке проставлена наименьшая стоимость пути, включая стоимости ее самой и конечной клетки.

Начнем с конечной клетки E1. В нее можно попасть за один ход из клеток D1 и E2. В обеих клетках возможен единственный ход. В клетке D1 проставляется стоимость 14+9=23, а в e2 – (-1)+9=8. Далее проставим минимальную стоимость во все клетки первой строки, двигаясь влево от клетки D1. Для каждой такой клетки также имеется единственный ход, и стоимость формируется путем сложения стоимости текущей клетки с минимальной стоимостью клетки справа, расмотренной на предыдущем шаге. Аналогично сверху вниз находятся минимальные стоимости для всех клеток последней вертикали E.

Далее также в порядке сверху вниз рассмотрим клетки предпоследнего столбца D. В клетке D2 нужно, очевидно, двигаться направо, поскольку стоимость клетки E2 меньше, чем D1. Запомним направление движения из клетки D2 и минимальную стоимость 12+8=20. В клетке D3 лучший ход вверх при стоимости 8+12=20. Затем можем перейти к третьему столбцу с и т. д. Отметим, что, в клетке B5 оба хода приводят к одинаковой стоимости 35.

Начальная клетка A5 будет рассмотрена последней. Получим, что минимальная стоимость пути из A5 в E1 составляет 43 единицы. Сам путь восстанавливается по тем лучшим ходам, которые были сохранены. В этом примере есть 2 пути минимальной стоимости: A5, B5, B4, C4, C3, C2, C1, В1, E1 и A5, B5, C5, C4, C3, C2, C1, D1, E1.

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

Отметим в заключение некоторые дополнительные аспекты применения методов динамического программирования.

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

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

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

4. Задача может не иметь выраженного многошагового характера, но тем не менее сводится к подобным задачам. Например, при проектировании дороги можно рабить предполагаемую область прохождения дороги на маленькие участки и оценивать их в зависимости от разных условий (рельеф местности, болота, реки, лесные участки, тип грунта и т. п.).