Игра с камушками

В математике и информатике игра с камешками — это тип математической игры, в которую играют путем размещения «камешков» или «маркеров» на ориентированном ациклическом графе по определенным правилам:

Данный шаг игры состоит в том, чтобы либо поместить камешек в пустую вершину, либо удалить камешек из ранее выложенной вершины.
Вершина может быть галечной только в том случае, если все ее предшественники содержат камешки.
Цель игры — последовательно обработать каждую вершину графа G (в любом порядке), минимизируя при этом количество камешков, одновременно находящихся на графе.

Время работы

Тривиальное решение — разбить n -вершинный граф за n шагов, используя n камешков. Хопкрофт, Пол и Валиант ^[1] показал, что любая вершина n -вершинного графа может быть покрыта камнями O( n /log n ), где константа зависит от максимальной входной степени. Это позволило им доказать, что DTIME ( f ( n )) содержится в DSPACE ( f ( n )/log f ( n )) для всех конструируемых по времени f . Липтон и Тарьян ^[2] показал, что любой с n -вершинами планарный ациклический ориентированный граф и максимальной входной степенью k можно разложить с помощью O( √ n + k log ₂ n ) камешков. Они также доказали, что можно получить существенное сокращение количества камешков, сохраняя при этом полиномиальную оценку количества шагов камешков, используя теорему о том, что любой планарный ациклический ориентированный граф с n -вершинами с максимальной входной степенью k может быть камешком с использованием O( n ^2/3 + k ) галька за O( n ^5/3) время. Алон, Сеймур и Томас ^[3] показал, что любой n -вершинный ациклический ориентированный граф без k _h - минора и с максимальной входной степенью k может быть раздроблен с помощью O( h ^3/2 н ^1/2 + k log n ) галька.

Вариации

Расширение этой игры, известное как «черно-белая галька», было разработано Стивеном Куком и Рави Сетхи в статье 1976 года. ^[4] Он также добавляет белые камешки, которые по желанию можно разместить в любой вершине, но удалить их можно только в том случае, если все вершины непосредственных предков вершины также покрыты камнями. Целью остается поместить черный камешек в целевую вершину, но засыпку соседних вершин можно выполнить камушками любого цвета.

Такуми Касаи и др. разработал игру, в которой камешек можно переместить по ребру-стрелке в незанятую вершину только в том случае, если второй камешек находится в третьей, контрольной вершине; цель — переместить камешек в целевую вершину. Этот вариант превращает игру с камушками в обобщение таких игр, как китайские шашки и Халма . Они определили вычислительную сложность версий этой игры для одного и двух игроков, а также их особые случаи. В версии для двух игроков игроки по очереди перемещают камешки. Также могут быть ограничения на то, какие камешки может перемещать игрок. ^[5]

Камешек можно использовать для расширения игр Эренфойхта – Фрэссе . ^[6]

См. также

Галька графа : определенное количество камешков распределяется по вершинам неориентированного графа; цель состоит в том, чтобы переместить хотя бы один в определенную целевую вершину. Но чтобы переместить один камешек в соседнюю вершину, необходимо отбросить другой камешек в той же вершине.
Игра на чипсете
Теорема о плоском сепараторе

Ссылки

^ Дж. Хопкрофт, В. Пол и Л. Валиант, Время и пространство, Журнал Ассоциации вычислительной техники, 1977 г.
^ Ричард Дж. Липтон и Роберт Э. Тарьян, Применение теоремы о плоском сепараторе, SIAM J. Comput. 1980 год
^ Нога Алон, Пол Сеймур, Робин Томас, Теорема о разделителе для графов с исключенным минором и ее приложения, ACM, 1990.
^ Стивен Кук ; Рави Сетхи (1976). «Требования к памяти для детерминированных языков, распознаваемых с полиномиальным временем» . Журнал компьютерных и системных наук . 13 (1): 25–37. дои : 10.1016/S0022-0000(76)80048-7 .
^ Такуми Касаи; Акео Адачи; Сигеки Ивата (1979). «Классы игр с камушками и полные задачи». SIAM Journal по вычислительной технике . 8 (4): 574–586. дои : 10.1137/0208046 .
^ Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы . Прогресс в теоретической информатике. Базель: Биркхойзер. стр. 39–44 . ISBN 3-7643-3719-2 . Заказ № 0816.68086 .

Дальнейшее чтение

Гредель, Эрих; Колайтис, Фокион Г.; Либкин, Леонид; Мартен, Маркс; Спенсер, Джоэл ; Варди, Моше Ю .; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN 978-3-540-00428-8 . Збл 1133.03001 .
Николас Пиппенджер . Галька. Технический отчет RC 8258, Исследовательский центр IBM Watson , 1980 г. Опубликован в материалах 5-го симпозиума IBM по математическим основам информатики, Япония .
Якоб Нордстрем . Игры с камушками, сложность доказательств и компромисс между временем и пространством. Логические методы в информатике , том 9, выпуск 3, статья 15, сентябрь 2013 г.

[1] Дж. Хопкрофт, В. Пол и Л. Валиант, Время и пространство, Журнал Ассоциации вычислительной техники, 1977 г.

[2] Ричард Дж. Липтон и Роберт Э. Тарьян, Применение теоремы о плоском сепараторе, SIAM J. Comput. 1980 год

[3] Нога Алон, Пол Сеймур, Робин Томас, Теорема о разделителе для графов с исключенным минором и ее приложения, ACM, 1990.

[4] Стивен Кук ; Рави Сетхи (1976). «Требования к памяти для детерминированных языков, распознаваемых с полиномиальным временем» . Журнал компьютерных и системных наук . 13 (1): 25–37. дои : 10.1016/S0022-0000(76)80048-7 .

[5] Такуми Касаи; Акео Адачи; Сигеки Ивата (1979). «Классы игр с камушками и полные задачи». SIAM Journal по вычислительной технике . 8 (4): 574–586. дои : 10.1137/0208046 .

[6] Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы . Прогресс в теоретической информатике. Базель: Биркхойзер. стр. 39–44 . ISBN 3-7643-3719-2 . Заказ № 0816.68086 .

[1]

[2]

[3]

[4]

[5]

[6]