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. 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 .
źródło
Odpowiedzi:
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ćℓ 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
źródło