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

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

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”)

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

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. ¹ 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. ² 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!

¹ 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 .
² 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 .

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ć$\ell$$s$$f$$s$$f$$n$ 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.$m$$m-(n-1)$$s$$f$$(n-1)l+(n-2)$$s$$f$$s$$f$