<<
>>

Расширения: алгоритм для задачи конкурентного размещения

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

Предположим, игрок 1 ходит первым.

Мы последовательно рассматриваем все возможные ходы. Для каждого из ходов мы проверяем, кто из игроков имеет фор- сированный выигрыш в полученной игре с первым ходом игрока 2. Если игрок 1 имеет форсированный выигрыш в какой-либо из этих игр, то он имеет форсирован- ный выигрыш и в исходной позиции. Здесь, как и в случае алгоритма QSAT, важно то, что пространство может повторно использоваться при перемещении между кандидатами; достаточно хранить один бит, представляющий результат. В этом случае алгоритм потребляет полиномиальное пространство плюс пространство, необходимое для одного рекурсивного вывода в графе с меньшим количеством узлов. Как и в случае QSAT, мы получаем рекуррентное отношение

S(n) < S(n — 1) + p(n)

для полиномиальной функции p(n).

В итоге получаем следующий результат:

(9.5) Задача конкурентного размещения решается с полиномиальными затра- тами пространства.

9.4.

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

Еще по теме Расширения: алгоритм для задачи конкурентного размещения:

  1. Статья 350. Выкуп земельных участков, других объектов недвижимого имущества, размещенных на них, частной собственности для общественных потребностей или их принудительное отчуждения по мотивам общественной необходимости
  2. Конкурентная модель де-мократии.
  3. ВЫ В КОНКУРЕНТНОЙ СРЕДЕ И ВАМ ДЫШАТ В СПИНУ
  4. Высшее «Я» и жизненная задача для шизоидного характера
  5. Статья 223. Размещение ценных бумаг без регистрацииих выпуска
  6. Жизненная задача и высшее «Я» для оральной структуры
  7. Жизненная задача и высшее «Я» для психопатического характера
  8. Жизненная задача и высшее «Я» для мазохистского характера
  9. Жизненная задача и высшее «Я» для жесткого характера
  10. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО РЕШЕНИЮ ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ ЗАДАЧ
  11. для успешного осмотра места происшествия рекомендуется решать следующие три задачи
  12. Прием создания исходных благоприятных психологический условий для решения задач общения.
  13. 4. Успеха добивается тот, кто для того, чтобы лучше решить задачу, повышает планку цели.
  14. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  15. АЛГОРИТМ
  16. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  17. АЛГОРИТМ УДАЧИ
  18. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН