Галька игра - Pebble game

Для настольной игры см. Go (игра).

В математика и Информатика, а камешковая игра это тип математическая игра играют, перемещая "камешки" или "маркеры" на ориентированный граф. Существует множество различных игр с галькой. Ниже дано конкретное определение гальки.

  • Галька - это игра, в которой камешки помещаются в вершины ориентированного ациклического графа. грамм по определенным правилам.
    • Данный шаг игры состоит в том, чтобы либо положить камешек на пустую вершину грамм или удаление камешка из вершины, на которой ранее был камешек.
    • Вершина может быть покрыта галькой только в том случае, если все ее предшественники имеют гальку.
    • Цель игры - последовательно камушить каждую вершину грамм (в любом порядке) при минимальном количестве камешков, которые когда-либо одновременно находятся на графике.
  • Время работы: тривиальное решение - п-вершинный граф в п шаги с использованием п галька. Хопкрофт, Пол и Валиант [1] показал, что любая вершина п-вершинный граф можно разбить на O (п/бревно п) гальки, где постоянная зависит от максимальной степени. Это позволило им доказать, что DTIME (ж(п)) содержится в DSPACE (ж(п)/бревнож(п)) для всех конструктивный ж. Липтон и Тарьян [2] показал, что любой п-вертекс планарный ациклический ориентированный граф с максимальной степенью k можно расчистить с помощью O (√п + k бревно2 п) галька. Они также доказали, что можно добиться существенного уменьшения количества камней, сохраняя при этом полиномиальную оценку количества шагов по камешку с теоремой о том, что любая п-вершинный плоский ациклический ориентированный граф с максимальной внутренней степенью k можно расчистить с помощью O (п2/3 + k) галька в O (п5/3) время. Алон, Сеймур и Томас [3] показал, что любой п-вершинный ациклический ориентированный граф без kчас-незначительный и с максимальной в степени k можно расчистить с помощью O (час3/2 п1/2 + k бревно п) галька.
  • Расширение этой игры, известное как «черно-белая галька», было разработано Стивен Кук и Рави Сетхи в статье 1976 года.[4] Он также добавляет белые камешки, которые могут быть размещены в любой вершине по желанию, но могут быть удалены только в том случае, если все вершины, являющиеся непосредственными потомками вершины, также являются камешками. Цель остается - поместить черный камешек в целевую вершину, но камешки соседних вершин могут быть любого цвета.
  • Такуми Касаи и другие. разработали игру, в которой камешек можно перемещать по краю-стрелке к незанятой вершине только в том случае, если второй камешек находится в третьей, контрольной вершине; цель - переместить камешек в целевую вершину. Этот вариант превращает игру в камешек в обобщение таких игр, как Китайские шашки и Хальма. Они определили вычислительная сложность однопользовательской и двухпользовательской версий этой игры, а также их частные случаи. В версии для двух игроков игроки по очереди перемещают гальку. Также могут быть ограничения на то, какие камешки игрок может перемещать.[5]
  • Галька может использоваться для увеличения Игры Эренфойхта – Фраиссе.[6]

Смотрите также

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

Рекомендации

  1. ^ Дж. Хопкрофт, У. Пол и Л. Валиант, О времени и пространстве, J. Assoc. Comput. Мах. 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 Журнал по вычислениям. 8 (4): 574–586. Дои:10.1137/0208046.
  6. ^ Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы. Успехи теоретической информатики. Базель: Биркхойзер. стр.39–44. ISBN  3-7643-3719-2. Zbl  0816.68086.

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