Расширения: алгоритм для задачи конкурентного размещения
Предположим, игрок 1 ходит первым.
Мы последовательно рассматриваем все возможные ходы. Для каждого из ходов мы проверяем, кто из игроков имеет фор- сированный выигрыш в полученной игре с первым ходом игрока 2. Если игрок 1 имеет форсированный выигрыш в какой-либо из этих игр, то он имеет форсирован- ный выигрыш и в исходной позиции. Здесь, как и в случае алгоритма QSAT, важно то, что пространство может повторно использоваться при перемещении между кандидатами; достаточно хранить один бит, представляющий результат. В этом случае алгоритм потребляет полиномиальное пространство плюс пространство, необходимое для одного рекурсивного вывода в графе с меньшим количеством узлов. Как и в случае QSAT, мы получаем рекуррентное отношениеS(n) < S(n — 1) + p(n)
для полиномиальной функции p(n).
В итоге получаем следующий результат:
(9.5) Задача конкурентного размещения решается с полиномиальными затра- тами пространства.
9.4.
Источник:
Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016
Еще по теме Расширения: алгоритм для задачи конкурентного размещения:
- Статья 350. Выкуп земельных участков, других объектов недвижимого имущества, размещенных на них, частной собственности для общественных потребностей или их принудительное отчуждения по мотивам общественной необходимости
- Конкурентная модель де-мократии.
- ВЫ В КОНКУРЕНТНОЙ СРЕДЕ И ВАМ ДЫШАТ В СПИНУ
- Высшее «Я» и жизненная задача для шизоидного характера
- Статья 223. Размещение ценных бумаг без регистрацииих выпуска
- Жизненная задача и высшее «Я» для оральной структуры
- Жизненная задача и высшее «Я» для психопатического характера
- Жизненная задача и высшее «Я» для мазохистского характера
- Жизненная задача и высшее «Я» для жесткого характера
- ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО РЕШЕНИЮ ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ ЗАДАЧ
- для успешного осмотра места происшествия рекомендуется решать следующие три задачи
- Прием создания исходных благоприятных психологический условий для решения задач общения.
- 4. Успеха добивается тот, кто для того, чтобы лучше решить задачу, повышает планку цели.
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- АЛГОРИТМ УДАЧИ
- ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
-
Windows -
Архитектура компьютера -
Интернет -
Информатика -
Компьютер -
Компьютерные и телекоммуникационные системы -
Программирование -
Социальные сети -
-
Английский язык -
Астрология -
Астрономия -
Биология -
Военная литература -
Журналистика -
Компьютерная инженерия -
Педагогика -
Право -
Психология -
Социология -
Lecture.Center