ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 3, с. 54-58
== УПРАВЛЕНИЕ В СТОХАСТИЧЕСКИХ СИСТЕМАХ
И В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
УДК 519.6
ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ДЛЯ ИГР С ЗАПРЕТАМИ
И ИХ ПРИЛОЖЕНИЯ*
© 2007 г. В. Н. Лебедев, В. И. Цурков
Волгоград, Волгоградский государственный ун-т, Москва, ВЦ РАН Поступила в редакцию 07.07.06 г.
Представлен полиномиальный алгоритм решения игр с запретами с равномерным функционалом по циклу для сильноэргодических игровых сетей. Дается критерий сильной эргодичности простейшей сети и показывается, что определение сильной эргодичности является со-ЫР полной проблемой. Игры с запретами интерпретируются в контексте задач теории расписаний с логическими условиями предшествования.
Введение. Рассматриваются сложностные вопросы решения циклических игр с запретами. Эти игры с аддитивным и максимальным функционалом исследованы в работе [1], где дано конструктивное доказательство наличия равновесия в стационарных, чистых стратегиях игроков с помощью метода потенциалов. Алгоритм, который следует из доказательства, оказался экспоненциальным в худшем случае. Но вычислительные эксперименты на задаче преследования показали его практическую эффективность. В [2] представлено обобщение подобных игр, где разрешенные отсечения ребер являются произвольной системой независимых подмножеств. Также и в этом случае техника потенциальных преобразований дает результат о наличии равновесия в стационарных стратегиях игроков.
В работе рассматриваются игры с запретами с равномерным функционалом по циклу. Техника потенциальных преобразований в данном случае не имеет места. Используя метод форсирования критической позиции [3], получен результат о наличии равновесия в чистых, стационарных стратегиях игроков. Переход от максминных игр [3] к играм с запретами не меняет основной идеи даказа-тельства, поэтому оно дается в сокращении. Представленный алгоритм оказывается полиномиальным для специальных, сильноэргодических структур игровых сетей.
Далее проводится анализ сложности определения, является ли данная простейшая игровая сеть сильноэргодической. Сформулирован критерий сильной эргодичности простейшей игровой сети и показано, что задача определения сильной эргодичности будет со-ЫР полной.
Игры с запретами важны в контексте задач теории расписаний с логическими условиями предшествования и для динамических задач большой раз-
* Работа выполнена при финансовой поддержке РФФИ (проект < 05-01-00531).
мерности [4]. Одна из возможных интерпретаций следующая. Есть некоторое множество работ и условия предшествования. Каждое условие включает некоторый список основных и побочных работ и заданное натуральное число к. Основная работа может быть принята к исполнению только после завершения по крайней мере к побочных работ. Даны времена и относительные сроки исполнения работ - основная работа может быть выполнена не раньше или не позже определенного срока, зависящего от побочной работы. Требуется найти любое допустимое расписание и, если такое существует, выявить оптимальное расписание с минимальным сроком исполнения всех работ. Считаем, что занятость исполнителей не является сдерживающим фактором, т.е. исполнителей работ большое число, и поэтому каждая работа может быть начата в любой момент при всех условиях предшествования.
1. Постановка задачи. Циклическая игра определяется игровой сетью (V; Е; с; к; у0), где (V; Е) - ориентированный граф без тупиков с множеством вершин V и множеством ориентированных ребер Е (в графе допускаются петли и кратные ребра), начальной вершиной v0, стоимостью локальных платежей с: V —► 2, функцией запретов к: V —► N (для любой вершины V е V, к(у) < |Е(^| - 1; Е(у) - ребра с началом в вершине V). Ориентированное ребро с началом в вершине Vи концом в ц> обозначим (V, м>). Множество Е(^, У2) объединяет ребра с началами в вершинах V1 и концами в вершинах V2; Е( - ребра с началами в вершинах V(V1) - множество концевых вершин ребер с началами в вершинах V].. Предполагается беступиковость графа, т.е. множество Е(у) не пусто для каждой вершины V графа. Любой вершине V е V приписано целое число с(у) е 2 (целочисленная стоимостная функция локальных платежей на вершинах графа). Имеется фишка, которая в начальный момент располагается в некоторой вершине v0 е V. Игроки шаг за шагом передвигают фишку по ребрам графа по следующему правилу.
Пусть в текущий момент времени фишка находится в позиции v е V, тогда второй игрок отсекает некоторые k(v) ребер, исходящих из вершины v, а первый перемещает фишку по одному из оставшихся ребер в очередную вершину. Партия продолжается до первого цикла, когда фишка пройдет конечный маршрут T: = v0, ..., vi, ..., vt = v; i < t, т.е. возникнет простой цикл C : vi, vi + 1, ..., vt = v. Пусть f - стоимостной функционал, заданный на множестве циклов. Тогда если f(C) > 0, то в разыгранной партии выигрывает второй, если f(C) < 0 -первый. Таким образом цель первого ходящего -минимизация стоимости цикла, а второго отсекающего - максимизация платежа.
Рассмотрим следующие варианты представления стоимостного функционала:
a) f(C) = maxc(v) (максимальный);
v е C
b)f(C) = maxc( v) + minc(v) (равномерный);
v е C v е C
c)f(C) = ^c( v}) (аддитивный).
] ='
В [1] доказано наличие равновесия для случаев а), с) и построены алгоритмы решения игр с запретами. Причем для а) алгоритм оказывается полиномиальным, а для с) он экспоненциален в худшем случае. В данной работе рассматриваем функционал Ь).
Несложными рассуждениями игры с запретами можно свести к обычным циклическим играм [3], изменяя структуру игровый сети (добавляя новые ребра согласно всем возможным отсечениям второго игрока), и тогда вывод о наличии равновесия в стационарных стратегиях будет следовать из [3]. Но это только экспоненциальное сведение, и алгоритм, вытекающий из этих рассуждений, практически неэффективен (экспоненциален в любом случае).
Замечательным свойством представленных игровых задач является их принадлежность классу ЫР п ео-ЫР (это непосредственно следует из наличия равновесия в стационарных стратегиях), поэтому при условии ЫР Ф ео-ЫР, доказать ЫР-полно-ту проблемы определения победителя в рассматриваемых циклических играх Ь), с) невозможно.
З а м е ч а н и е 1. Класс ЫР включает задачи распознавания, решаемые за полиномиальное время на недетерминированной машине Тьюринга, класс ео-ЫР - задачи, дополнение к которым определея-ется за полиномиальное время на недетерминированной машине Тьюринга. Таким образом, ЫР п ео-ЫР - это задачи, которые распознаются вместе со своим дополнением за полиномиальное недетерминированное время. Существует гипотеза (аналогичная теореме Поста, утверждающей, что если множество и его дополнение рекурсивно перечислимы, то это множество рекурсивно) в соответствии с которой, если множество распознаваемо за полино-
миальное, недетерминированное время вместе со своим дополнением, то оно распознаваемо за полиномиальное детерминированное время. Для всех известных задач линейного программирования (в этом случае, принадлежность классу ЫР п ео-ЫР следует непосредственно из теорем двойственности), и простоты числа (принадлежность классу ЫР п ео-ЫР доказывается теоремой Эйлера) приведенная гипотеза оказалась верной и были построены полиномиальные алгоритмы решения. Для решения циклических игр с запретами вопрос получения полиномиального алгоритма остается открытым. Для этого используем метод форсирования критической позиции.
2. Поиск стационарных стратегий выигрыша форсированием критической позиции. Рассматриваем игру с запретами (V; Е; е; к у0) с равномерным функционалом по варианту Ь. Партию выигрывает второй игрок, если сумма максимальной и минимальной стоимостей вершин цикла не меньше нуля и первый игрок в противном случае.
О п р е д е л е н и е 1. Примем, что первый игрок применяет стационарную стратегию ^ в графе (V; Е), ^ : V —► Е, где ^(у) с Е(у); = к(у) + 1 для любой V е V, если всякий раз, когда фишка попадает в вершину у, он передвигает ее по любому из ребер, оставшихся после отсечений второго игрока (так как ку) + 1 < |Е(у)|, а второй игрок отсекает к(у) ребра, то стратегия определена корректно).
О п р е д е л е н и е 2. Будем говорить, что второй игрок использует стационарную стратегию 52 в графе (V; Е), ^2 : V —► Е, где ^(у) с Е(у); ^(у) = к(у) для любой у е V, если всякий раз, когда фишка попадает в вершину у, он отсекает множество ребер
У т в е р ж д е н и е 1. Для произвольной циклической игры с запретами (V; Е; е; к) существует разбиение вершин V = V1 и V2; V1 п V2 = 0 (возможно одно из множеств V1 или V2 пусто) и пара стратегий первого и второго игроков s2, для которых справедливы условия:
1) в графе V; Е(У1, V!) п все циклы меньше нуля;
2) п Е(^, V,) = 0;
3) в графе (У2; Е(У2, V2) п 52) все циклы не меньше нуля;
4) Е(УЪ V) с 52.
Таким образом, действуя в вершинах V],, согласно ¿1, первый игрок обеспечивает отрицательный цикл независимо от усилий противника, играя в вершинах V2 в соответствии с 52 второй игрок добивается цикла не меньшего нуля. Выигрывающие стратегии игроков 5 и 52 независимы от начальной вершины.
Д о к а з а т е л ь с т в о. Воспользуемся индукцией по числу вершин в графе. Для графа с одной вершиной (петли допустимы) утверждение, очевидно, справедливо. Пусть утверждение верно для любой игровой сети с числом вершин не более п > 1. Возь-
t -1
мем произвольную игровую сеть (V; E; c; k) с числом вершин n + 1. Введем величины m = minc (v),
v e V
M = maxc (v). Рассмотрим два возможных случая.
v e V
Случай 1. M + m > 0. Обозначим множество вершин I = {v: c( v) = M}. Найдем множество вершин W, из которых второй игрок форсированно, т.е. не зависимо от игры противника, добивается вершины из множества I.
Это множество строится следующей рекурсивной процедурой. Пусть уже сформированы множества W1 = I, ..., Wt_!,где W = WjU,...,uWt_Тогда Wt = {v e W', |{(v, s) e E, s e W }| < k(v)}.
Если Wt = 0, то W = W. Отметим стационарную стратегию s1 второго игрока, которая позволяет ему в вершинах W добиваться максимальной стоимости в I. Эта стратег
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.