Gra Dracula

Kontekst
To pytanie jest motywowane grą planszową o nazwie „Dracula”. W tej grze jest jeden wampir i czterech łowców, których celem jest złapanie wampira. Gra toczy się w Europie. Gra wygląda następująco:
1. Łowca umieszcza wszystkich łowców w miastach. W tym samym mieście można umieścić więcej niż jednego myśliwego.
2. Gracz wampirów umieszcza wampira w mieście.
3. Gracze naprzemiennie przenoszą swoje stworzenia do sąsiednich miast.
4. Gracz łowca z kolei może poruszyć dowolną liczbę myśliwych.
5. Główna trudność polega na tym, że gracz wampirów wie przez cały czas, gdzie przebywają łowcy, ale gracz łowców zna tylko pozycję początkową wampira.
6. Kiedy łowca i wampir spotykają się w mieście, gracz wampir przegrywa.

Pytanie
Dla danego wykresu oraz liczb n i k , czy istnieje strategia gwarantująca, że ​​gracz myśliwy, który kontroluje n myśliwych, złapie wampira w czasie krótszym niż k tur? Można założyć, że G jest płaskie. Czy zbadano ten problem? Doceniamy niektóre referencje.$G$$n$$k$$n$$k$$G$

Gra, którą opisałeś, przypomina grę K Cops i 1 Robber, jak opisano w tym artykule Clarke i Macgillivray: http://www.sciencedirect.com/science/article/pii/S0012365X12000064 . Zasadniczo rozgrywka polega na umieszczeniu k-policjantów i rabusia na wierzchołkach wykresu i poproszeniu gliniarzy o złapanie rabusia poprzez przesuwanie się wzdłuż krawędzi.

Główną różnicą od twojej gry i tej jest częściowa widoczność myśliwych, podczas gdy w klasycznych policjantach i złodziejach policjanci wiedzą dokładnie, gdzie jest złodziej i odwrotnie. Również u gliniarzy i złodziei czas nie jest ograniczony.

Nawet przy pełnej informacji, jeśli czas nie jest ograniczony, wykazano, że ustalenie, czy k-gliniarze mogą ostatecznie schwytać rabusia w skończonym czasie, gdy rabuś i gliniarze grają optymalnie, jest zakończone w czasie wykładniczym ( http://arxiv.org /abs/1309.5405 ), gdy k nie jest naprawiony. Dlatego, ponieważ twoja gra jest trudniejsza dla gliniarzy, sądzę, że nie można jej rozwiązać w czasie wielomianowym, gdy czas nie jest ograniczony. Myślę, że liczbę ruchów niezbędnych do złapania rabusia przez policjantów można ograniczyć powyżej, powiedzmy c, a jeśli liczba kroków dozwolonych myśliwym k jest zbliżona do tej liczby c, to gra łowców i wampirów byłaby co najmniej tak trudne do rozwiązania, jak k gliniarze i rabusie (patrz artykuł Bonato i wsp .: Czas przechwytywania wykresu).

Jak zauważył @MarcusRitt w komentarzach, nazywa się to przeszukiwaniem grafów. Chciałbym jednak dodać, że konkretny wariant, który opisujesz (tj. Związany z liczbą rund rozgrywanych z liczbą zatrudnionych wyszukiwarek) został również zbadany, czego nie odnotowano w artykule na Wikipedii. Co ciekawe, przejście z przestrzeni wyszukiwania do czasu wyszukiwania zachowuje charakterystykę problemu (poprzez wprowadzenie odpowiednich „podwójnych” wersji odpowiednich parametrów).

Zobacz artykuł „Wyszukiwanie wykresów i czas wyszukiwania” Brandenburg i Herrmann na SOFSEM 2006.

$v$$v$$1$$1$$k$, również w przypadku wykresów płaskich możliwe jest przybliżenie liczby gliniarzy (a następnie uzyskanie odpowiedniego rozkładu) w czasie wielomianowym. Być może chcesz przeczytać więcej z tych notatek z wykładu.