PS-полнота задачи Generalized geography — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Утверждение)
(рисунки)
Строка 1: Строка 1:
 
== Формулировка задачи==
 
== Формулировка задачи==
Городки (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий. Повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.
+
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.
  
 
=== Графическая модель ===
 
=== Графическая модель ===
Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Ниже приведен пример такого графа для игры в городки в штате Мичиган.
+
Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Например, граф для игры в городки в штате Мичиган может выглядеть так:
  
Рисунок
+
[[Файл:Generalized_geography_1.png]]
  
В обобщенных городках (Generalized Geography) используется любой ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход.
+
В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).
Пусть P1 - игрок, который ходит первым, и  P2 - игрок, который ходит вторым. В приведенном ниже примере первый игрок имеет следующую выигрышную стратегию(изначально находится в вершине 1): переходит в вершину 2, после чего второй игрок переходит в вершину 4, так как это единственный вариант. Первый игрок переходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора второго игрока, первый переходит в вершину 9, откуда второй игрок никуда не может пойти.
 
  
Рисунок.  
+
Рассмотрим пример такой игры. Пусть P1 - игрок, который ходит первым, и  P2 - игрок, который ходит вторым. Здесь первый игрок обладает следующей выигрышной стратегией(игра начинается с первой вершины): делает ход в вершину 2, после чего второй игрок переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора второго игрока, первый может перейти в вершину 9, откуда второй игрок никуда не может пойти.
 +
 
 +
[[Файл:Generalized_geography_2.png]]
  
 
== Утверждение ==
 
== Утверждение ==

Версия 15:30, 29 марта 2010

Формулировка задачи

Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

Графическая модель

Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Например, граф для игры в городки в штате Мичиган может выглядеть так:

Generalized geography 1.png

В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).

Рассмотрим пример такой игры. Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. Здесь первый игрок обладает следующей выигрышной стратегией(игра начинается с первой вершины): делает ход в вершину 2, после чего второй игрок переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора второго игрока, первый может перейти в вершину 9, откуда второй игрок никуда не может пойти.

Generalized geography 2.png

Утверждение

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

Эта задача PS-полна.

Доказательство

Доказательство принадлежности задачи классу PS

Чтобы показать, что задача принадлежит классы PS, предъявим алгоритм, работающий на полиномиальной памяти, определяющий, обладает ли игрок выигрышной стратегией находясь в вершине v графа G.

Алгоритм M(<G,v>):

1. Если из вершины, в которой находится игрок, не ведет ни одного ребра в непосещенные ранее вершины, то вернем FALSE, мы проиграли.

2. Иначе запустим этот же алгоритм от всех вершин, в которые можно пойти, и если везде вернется TRUE, вернем FALSE, куда бы мы ни пошли, второй игрок выиграет. Если же хоть из одной вершины функция вернула FALSE, то вернем TRUE, в этой вершине второй игрок проигрывает.

Этот алгоритм перебором находит выигрышную стратегию для первого игрока, и очевидно, требует полиномиальную память: на каждом шаге одна или более вершин помечаются как посещенные, и более не обрабатываются.

Доказательство принадлежности задачи классу PSH

Для доказательства этого факта сведем задачу о выигрывании игрока Существует в булевой КНФ-формуле с пердворяющими кванторами(эта задача PS-трудная) к Generalized Geography за полиномиальное время.

Булева формула с кванторами имеет следующий вид: φ = Q1x1 Q2x2 Q3x3 ...Qkxk(ψ) где Q</sub>i</sub> квантор ∃ или ∀. Заметим, что любую такую формулу можно преобразовать к виду φ = ∃x1x2x3 ...∃xk(ψ) , добавив необходимое количество переменных с кванторами. Если булева формула возвращает TRUE после ходов игроков По-любому и Существует, то выиграл существует, иначе выиграл По-любому.

Построив аналогичный граф (приведен ниже) для любой булевой формулы с кванторами, мы сможем свести задачу о выигрывании игрока Существует к задаче о наличии выигрышной стратегии у первого игрока в Generalized Geography.

Левый столбец описывает процедуру выборки игроками значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.

Зафиксировав значения переменных, игрок По-любому (т.к. в нашей КНФ-формуле с предворяющими кванторами последний квантор Существует) выбирает скобку, значение которой может быть FALSE (тогда он выиграет!). На рисунке каждая скобка - отдельная вершина ci.

После того, как игрок По-Любому зафиксировал скобку, игрок Существует выбирает переменную, значение которой не ноль (игроки уже зафиксировали значения переменных в самом начале) и делает переход в соответсвующую вершинку. Т.к. значение этой переменной не ноль, то игрок По-любому не сможет никуда пойти из этой вершины. Для этого проведем ребра из каждый скобки в вершины, соответствующие выбору TRUE или FALSE значений переменных.