Generowanie labiryntu obrony wieży, czyli Znalezienie K najbardziej istotnych węzłów („interwencja nodewise”) na nieważonym wykresie siatkowym

22

W grze typu tower defense masz siatkę NxM z początkiem, wykończeniem i wieloma ścianami.

Zdjęcie 1

Wrogowie podążają najkrótszą ścieżką od początku do końca, nie przechodząc przez ściany (zwykle nie są ograniczeni do siatki, ale dla uproszczenia powiedzmy, że są. W obu przypadkach nie mogą poruszać się po przekątnych „otworach”)

Zdjęcie 2

Problem (przynajmniej w przypadku tego pytania) polega na umieszczeniu do K dodatkowych ścian, aby zmaksymalizować ścieżkę, którą muszą pokonać wrogowie, bez całkowitego blokowania początku od końca. Na przykład dla K = 14

Zdjęcie 3


Ustaliłem, że jest to ten sam problem, co „k najbardziej istotnych węzłów”:

Biorąc pod uwagę nieukierowany wykres G = (V, E) i dwa węzły s, t ∈ V, k-najbardziej żywotnymi węzłami jest k węzłów, których usunięcie maksymalizuje najkrótszą ścieżkę od s do t.

Khachiyan i wsp. 1 wykazali, że nawet jeśli wykres jest nieważony i dwustronny, nawet przybliżenie długości maksymalnej najkrótszej ścieżki w ramach współczynnika 2 wynosi NP-Twardość (biorąc pod uwagę k, s, t) .

Nie wszystko jednak stracone: później L. Cai i wsp. 2 wykazali, że w przypadku „dwustronnych grafów permutacyjnych” problem ten można rozwiązać w czasie pseudo-wielomianowym za pomocą „modelu przecięcia”.

Nie byłem w stanie znaleźć niczego konkretnie na nieważonych grafach siatkowych i nie mogę zrozumieć, w jaki sposób powiązane są „dwustronne grafy permutacyjne”. Czy opublikowano jakieś badania dotyczące mojego problemu - może szukam w zupełnie niewłaściwym miejscu? Nawet porządny algorytm aproksymacji pseudo-wielomianowej działałby dobrze. Dzięki!


1 L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf i J. Zhao „O problemach z krótką ścieżką: Ograniczone całkowite i ograniczone węzły”, Teoria systemów komputerowych 43 ( 2008), 2004–233. link .
2 L. Cai i J. Mark Keil, „Znajdowanie k najważniejszych węzłów na wykresie interwałowym”. link .

Uwaga: to pytanie jest kontynuacją mojego pytania dotyczącego przepełnienia stosu znalezionego tutaj .

BlueRaja - Danny Pflughoeft
źródło
3
Wyjaśnienie: nie możesz usunąć zestawu węzłów, które całkowicie odłączyłyby początek od końca?
David Eppstein
@David: Tak edytowane, przepraszam za zamieszanie. Nadal musi być rozwiązanie.
BlueRaja - Danny Pflughoeft

Odpowiedzi:

12

Wydaje się, że jest to NP-całkowite przez redukcję z cyklu Hamiltona w płaskich wykresach stopnia co najwyżej trzy. Cykl hamiltonowski powinien być nadal trudny na płaskich wykresach stopnia co najwyżej trzy, które zawierają dwa sąsiednie węzły stopień-dwa (tej części nie sprawdziłem bardzo dokładnie). Osadź dany wykres płaski na siatce w taki sposób, aby każdy wierzchołek stał się punktem siatki, każda krawędź stała się ścieżką siatki, a wszystkie krawędzie miały tę samą długość (w razie potrzeby wypełnij krótsze, zygzakiem). Daj i są dwa sąsiednie stopni dwa węzły. Uwzględnij ściany w początkowym położeniu ścian, aby tylko wierzchołki i krawędzie osadzenia pozostały dostępne do podłączenia do . Pozwolićsfsfn i będą liczbami wierzchołków i krawędzi na oryginalnym wykresie. Wówczas oryginalny wykres ma cykl hamiltonowski wtedy i tylko wtedy, gdy możliwe jest umieszczenie większej liczby ścian w taki sposób, że nowa najkrótsza ścieżka od do ma długość . Ścieżka o tej długości musi być ścieżką hamiltonowską na oryginalnym wykresie, która wraz z krawędzią od do tworzy cykl hamiltonowski, i odwrotnie, jeśli wykres zawiera cykl hamiltonowski, możesz wymusić ścieżkę od do aby była długo, umieszczając ścianę na sobie nawzajem.mm(n1)sf(n1)l+(n2)sfsf

David Eppstein
źródło
Niezła redukcja!
Marzio De Biasi
Jasne, pomyślałem o tym, biorąc pod uwagę odniesienia w pytaniu; ale wciąż potrzebuję jakiegoś rozwiązania i liczyłem na coś lepszego niż proste „użycie algorytmu wyżarzania / algorytmy genetyczne / podobne”. Moje pytanie brzmi: czy istnieje (podobnie jak powyższy przypadek dwustronnego wykresu permutacji) jakieś znane rozwiązanie pseudo-wielomianowe, czy nawet pół przyzwoite przybliżenie, które gwarantuje pewne wiązanie?
BlueRaja - Danny Pflughoeft
3
Silna kompletność NP sprawia, że ​​rozwiązanie pseudopolomiczne jest mało prawdopodobne. I powyższa redukcja, wraz z faktem, że nie ma dobrego przybliżenia dla najdłuższej ścieżki (najlepiej znanym przybliżeniem jest i jest wynik niedopuszczalności dla ukierunkowanego przypadku ) łącznie oznaczają, że trudne do udowodnienia przybliżenie tego problemu również będzie trudne. Ω ( n 1 - ϵ )O(n/polylog)Ω(n1ϵ)
David Eppstein
Nie jestem w stanie podążać tym tropem logiki, ale uwierzę ci na słowo i dam ci bardzo sadface znacznik wyboru :( ✓. Dziękuję za poświęcenie czasu na zastanowienie się i odpowiedź na to pytanie, profesorze Eppstein!
BlueRaja - Danny Pflughoeft
Rok i dużo nauki (z mojej strony) później, teraz rozumiem i zgadzam się z tym dowodem.
Jeszcze