Русская Википедия:Фишечная игра
Фишечная игра — это вид Шаблон:Не переведено 5, в которой игра заключается в передвижении «фишек» или «маркеров» на ориентированном графе. Существует большое число различных фишечных игр.
Прохождение фишками
- Прохождение фишками — это игра, в которой фишки размещаются на вершинах направленного ациклического графа G согласно некоторым правилам.
- Ход игры состоит либо в размещении фишки в вершине графа G, либо изъятию фишки из занимаемой фишкой вершины.
- Вершина может быть занята фишкой, только если имеются все её предшественницы.
- Целью игры является успешное посещение фишками всех вершин графа G (в любом порядке) с минимальным числом фишек, выставленных на графе одновременно.
Время игры
Тривиальным решением является заполнение фишками n-вершинного графа за n шагов, используя n фишек. Хопкрофт, Пол и ВэлиентШаблон:Sfn показали, что любая вершина графа с n вершинами может быть посещена с <math>O(n \log n)</math> фишками, где константа зависит от максимальной полустепени захода. Это дало им возможность доказать, что Шаблон:Не переведено 5<math>(f(n))</math> содержится в Шаблон:Не переведено 5<math>(f(n)\log f(n))</math> для всех Шаблон:Не переведено 5 f. Липтон и ТарьянШаблон:Sfn показали, что любой n-вершинный планарный ациклический ориентированный граф с максимальной полустепенью захода k может быть пройден с <math>O(\sqrt{n} + k \log_2 n)</math> фишками. Они также доказали, что можно получать существенное сокращение числа фишек, сохраняя полиномиальную границу числа шагов размещения фишек, доказав теорему, что любой n-вершинный планарный ацикличный ориентированный граф с максимальной полустепенью захода k может быть пройден с <math>O(n^{\tfrac{2}{3}} + k)</math> фишками за время <math>O(n^{\tfrac{5}{3}})</math>. Алон, Сеймур и ТомасШаблон:Sfn показали, что любой n-вершинный ацикличный ориентированный граф без kh-миноров и максимальной полустепенью захода k может быть пройден с <math>O(h^{\tfrac{3}{2}} n^{\tfrac{1}{2}} + k \log n)</math> фишками.
Прохождение черными и белыми фишками
Обобщение этой игры, известное как «прохождение черными и белыми фишками», разрабатывали Стивен Артур Кук и Рави Сети в статье 1976 годаШаблон:Sfn. В игру добавляются белые фишки, которые могут быть размещены в любой вершине, какой захотим, но удалить такую фишку можно, только если все непосредственные дочерние вершины также заняты фишками. Цель остаётся той же — разместить чёрную фишку на целевой вершине, но заполнение фишками смежных вершин можно делать фишками любого цвета.
Другие варианты
Такуми Касаи, Акэо Адати и Сигэки Ивата разработали игру, в которой фишка может двигаться вдоль ребра в неоккупированную вершину, только если вторая фишка расположена на третьей контрольной вершине. Целью является продвинуть фишку до целевой вершины. Эти вариации делают фишечную игру обобщением игр, таких как китайские шашки и халма. Они определяют вычислительную сложность версий игры с одним и двумя игроками и их специальные версии. В версии с двумя игроками игроки двигают фишки поочерёдно. Могут существовать ограничения на то, какие фишки игрок может двигатьШаблон:Sfn.
Игра с прохождением фишками может быть обобщена до игры Эренфойхта — ФраисаШаблон:Sfn.
См. также
Шаблон:Не переведено 5: некоторое число фишек располагается в вершинах неориентированного графа. Целью является достижение целевой вершины, но чтобы передвинуть фишку на смежную вершину, другая фишка на той же вершине должна быть удалена.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
Литература для дальнейшего чтения
