Задача конкурентного размещения

Наконец, мы приходим к пятой задаче, которая базируется на следующей игре для двух участников. Допустим, имеются две крупные компании, которые открывают свои сети кофеен по всей стране (назовем их JavaPlanet и Queequeg's Coffee); в на- стоящее время они соревнуются за свою долю рынка в некотором географическом регионе.
Сначала JavaPlanet открывает свое заведение; затем Queequeg's Coffee открывает свое; потом JavaPlanet; снова Queequeg's, и т. д. Допустим, они должны выполнять градостроительные нормы, согласно которым две кофейни не должны располагаться слишком близко друг к другу, и каждая компания пытается разме- стить свои заведения в самых удобных точках. Кто выиграет?

Сделаем правила «игры» более конкретными. Географический регион, о кото- ром идет речь, разделен на n зон с номерами 1, 2, ..., n. Каждой зоне i присваивается оценка b — доход, который получит любая из компаний, открывшая кофейню в этой зоне. Наконец, некоторые пары зон (i, j) являются смежными, а местные градостроительные нормы запрещают открывать кофейни в двух смежных зонах независимо от того, какой компании они принадлежат (а также запрещают от- крывать две кофейни в одной зоне). Для моделирования этих конфликтов мы воспользуемся графом G = (V, E), где V — множество зон, а (i, j) — ребро в E, если зоны i и j являются смежными. Таким образом, градостроительные нормы требуют, чтобы полный набор кофеен образовал независимое множество в G.

В нашей игре два игрока P1 и P2 поочередно выбирают узлы в G, игрок P1 де- лает первый ход. Набор всех выбранных узлов в любой момент времени должен образовать независимое множество в G. Предположим, игрок P2 имеет целевую границу B, и мы хотим узнать: существует ли для P2 такая стратегия, чтобы неза- висимо от выбора ходов P1 игрок P2 мог выбрать множество узлов с суммарной оценкой не ниже B?

Мы назовем эту формулировку задачей конкурентного размещения.

Для примера возьмем набор данных на рис. 1.7; предположим, игроку P2 уста- новлена целевая граница B = 20. В этом случае у P2 имеется выигрышная стратегия. С другой стороны, при B = 25 у игрока P2 такой стратегии нет.

Рис. 1.7. Экземпляр задачи конкурентного размещения


В этом нетрудно убедиться, изучая диаграмму в течение некоторого времени; но для этого потребуется проверка разных сценариев в виде «Если P1 ходит так, то P2 пойдет вот так; но если Pl походит так, то P2 ответит так...» И похоже, это об- стоятельство является неотъемлемой особенностью задачи: мало того что проверка наличия у P2 выигрышной стратегии имеет высокую вычислительную сложность; в графе сколько-нибудь значительного размера нам будет трудно даже убедить вас в наличии у P2 выигрышной стратегии. Не существует короткого доказательства, которое можно было бы продемонстрировать; вместо этого приходится приводить объемистый анализ множества всех возможных ходов.

В этом отношении задача отличается от задачи независимого множества, в ко- торой, насколько нам известно, найти большое решение сложно, зато предложен- ное большое решение проверяется легко. Эти отличия формализуются в классе PSPACE-полных задач, к которому принадлежит задача конкурентного размеще- ния. Считается, что PSPACE-полные задачи строго сложнее ЖP-полных задач, и это предполагаемое отсутствие коротких «доказательств» их решений является признаком этой повышенной сложности. Концепция PSPACE-полноты отражает широкий спектр задач, связанных с играми и планированием; многие из них счи- таются фундаментальными проблемами в области искусственного интеллекта.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача конкурентного размещения:

  1. Конкурентная модель де-мократии.
  2. ВЫ В КОНКУРЕНТНОЙ СРЕДЕ И ВАМ ДЫШАТ В СПИНУ
  3. Статья 223. Размещение ценных бумаг без регистрацииих выпуска
  4. Статья 377. Право на земельный участок при приобретении жилого дома, здания или сооружения, которые размещенные на нем
  5. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  6. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  7. Статья 350. Выкуп земельных участков, других объектов недвижимого имущества, размещенных на них, частной собственности для общественных потребностей или их принудительное отчуждения по мотивам общественной необходимости
  8. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  9. ЗАДАЧА
  10. ЗАДАЧА: РЕШЕНИЕ
  11. Основные задачи.
  12. в) Задачи
  13. в) Задачи
  14. ПСИХОАНАЛИЗ: ЗАДАЧА
  15. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  16. Основные задачи
  17. Правило решаемой психологической задачи.
  18. Задачи и упражнения