Игра Дракула

История вопроса
Этот вопрос мотивирован настольной игрой под названием «Дракула». В этой игре есть один вампир и четыре охотника, цель охотников - поймать вампира. Действие игры происходит в Европе. Игра выглядит следующим образом:
1. Игрок-охотник сажает всех охотников в города. В одном городе можно разместить более одного охотника.
2. Игрок-вампир отправляет вампира в город.
3. Игроки поочередно перемещают своих существ в соседние города.
4. Игрок охотник в свою очередь может перемещать столько охотников, сколько он хочет.
5. Основная трудность заключается в том, что игрок-вампир все время знает, где находятся охотники, а игрок-охотник знает только начальную позицию вампира.
6. Когда охотник и вампир встречаются в городе, игрок-вампир проигрывает.

Вопрос
Для заданного графа и чисел n и k , существует ли стратегия, которая гарантирует игроку-охотнику, который контролирует n охотников, ловить вампира менее чем за k ходов? Можно предположить, что G плоская. Была ли изучена эта проблема? Некоторые ссылки будут оценены.$G$$n$$k$$n$$k$$G$

Игра, которую вы описали, очень похожа на игру k Cops и 1 Robber, как описано в этой статье Clarke и Macgillivray: http://www.sciencedirect.com/science/article/pii/S0012365X12000064 . В основном это играется, помещая k полицейских и грабителя в вершины графа и прося, чтобы полицейские поймали грабителя, двигаясь вдоль краев.

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

Даже с полной информацией, если время не ограничено, было показано, что определение того, могут ли к-копы в конечном итоге захватить грабителя за конечное время, когда грабитель и копы играют оптимально, завершается по экспоненциальному времени ( http://arxiv.org /abs/1309.5405 ), когда k не зафиксировано. Следовательно, поскольку в вашу игру сложнее играть за копов, я бы предположил, что она также не может быть решена за полиномиальное время, когда время не ограничено. Я думаю, что число ходов, необходимое для k копов, чтобы поймать грабителя, может быть ограничено выше, скажем, c, и если число шагов k, разрешенных охотникам, близко к этому числу c, то игра охотников и вампиров будет по крайней мере так же трудно решить, чем k копов и грабителей (см. статью Бонато и др.: Время захвата графа).

Как отмечает @MarcusRitt в комментариях, это называется поиском графиков. Однако я хотел бы добавить, что конкретный вариант, который вы описываете (т. Е. Связывает количество раундов, сыгранных с количеством занятых поисковиков), также был исследован, что не отмечено в статье Википедии. Интересно, что переход от пространства поиска к времени поиска сохраняет характеристики проблемы (путем введения соответствующих «двойных» версий соответствующих параметров).

См. Статью «Поиск в графе и время поиска» Бранденбурга и Херрманна на SOFSEM 2006.

Если мы обобщим игровое условие, то оно будет равносильно игре ширины пути с коп-грабителем. Единственное расслабление в том, что грабитель может перейти в любую вершину$v$ он хочет, если есть чистый путь (без копа на этом пути) от его текущей позиции до $v$, Тогда минимальное количество копов, необходимое для поимки грабителя, равно ширине пути (G) -$1$, Если полицейским разрешено видеть грабителя в аналогичной игре, как я уже говорил, то минимальное количество копов, необходимое для того, чтобы поймать грабителя, равно ширине дерева (G) -$1$, В обоих случаях есть полиномиальный алгоритм, чтобы найти грабителя для фиксированной$k$Кроме того, для плоских графов можно аппроксимировать количество копов (и затем получить соответствующее разложение) за полиномиальное время. Может быть, вы заинтересованы, чтобы прочитать больше из этой лекции.