Generieren eines Tower Defense Labyrinths, auch bekannt als Finden der K wichtigsten Knoten ("knotenweises Verbot") in einem ungewichteten Graphen

22

In einem Tower Defense-Spiel haben Sie ein NxM-Raster mit einem Start, einem Ziel und einer Reihe von Wänden.

Image1

Gegner nehmen den kürzesten Weg vom Anfang bis zum Ende, ohne Wände zu durchqueren (normalerweise sind sie nicht an das Gitter gebunden, aber der Einfachheit halber können sie sich nicht durch diagonale "Löcher" bewegen.)

Image2

Das Problem (zumindest für diese Frage) besteht darin, bis zu K zusätzliche Wände zu platzieren, um den Weg der Feinde zu maximieren, ohne den Start vom Ziel aus vollständig zu blockieren. Zum Beispiel für K = 14

Image3


Ich habe festgestellt, dass dies dasselbe ist wie das Problem mit den "k wichtigsten Knoten":

Bei einem ungerichteten Graphen G = (V, E) und zwei Knoten s, t ∈ V sind die k vitalsten Knoten die k Knoten, deren Entfernung den kürzesten Weg von s nach t maximiert.

Khachiyan et al. 1 haben gezeigt, dass, selbst wenn der Graph ungewichtet und zweiteilig ist, die Länge des kürzesten maximalen Pfades innerhalb eines Faktors von 2 NP-hart ist (gegeben k, s, t) .

Es ist jedoch nicht alles verloren: Später zeigten L. Cai et al. 2 , dass dieses Problem für "zweigliedrige Permutationsgraphen" mit dem "Schnittmodell" in pseudo-polynomialer Zeit gelöst werden kann.

Auf ungewichteten Graphen konnte ich nichts finden und ich kann nicht herausfinden, wie "zweigliedrige Permutationsgraphen" zusammenhängen, wenn überhaupt. Wurden Recherchen zu meinem Problem veröffentlicht ? Vielleicht suche ich an einer völlig falschen Stelle? Sogar ein anständiger Pseudo-Polynom-Approximationsalgorithmus würde gut funktionieren. Vielen Dank!


1 L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf und J. Zhao "On Kurzweg Interdiction Probleme: Total und Node-Wise Begrenzte Interdiction" Theory of Computer Systems 43 ( 2008), 2004-233. link .
2 L. Cai und J. Mark Keil, "Finden der k wichtigsten Knoten in einem Intervallgraphen." link .

Hinweis: Diese Frage ist eine Folge meiner Frage zum Stackoverflow, die Sie hier finden .

BlueRaja - Danny Pflughoeft
quelle
3
Eine Klarstellung: Sie dürfen keine Knoten entfernen, die Start und Ziel vollständig trennen würden?
David Eppstein
@ David: Ja bearbeitet, sorry für die Verwirrung. Es muss noch eine Lösung geben.
BlueRaja - Danny Pflughoeft

Antworten:

12

sfsfnmm-(n-1)sf(n-1)l+(n-2)sfsf

David Eppstein
quelle
Schöne Ermäßigung!
Marzio De Biasi
Klar, das ist es, was ich mir angesichts der Referenzen in der Frage gedacht habe. aber ich brauche immer noch eine Lösung und ich hoffte auf etwas Besseres als das einfache "Verwenden von Annealing / genetischen Algorithmen / Ähnlichem". Meine Frage ist, gibt es (wie im obigen Fall der zweigliedrigen Permutationsgraphik) eine bekannte pseudo-polynomielle Lösung oder sogar eine halb anständige Näherung, die eine gewisse Bindung garantiert?
BlueRaja - Danny Pflughoeft
3
O(n/pOlylOG)Ω(n1-ϵ)
Ich bin nicht in der Lage, dieser Spur der Logik zu folgen, aber ich nehme Ihr Wort und gebe Ihnen ein sehr trauriges Häkchen :( ✓. Vielen Dank, dass Sie sich die Zeit genommen haben, über diese Frage nachzudenken und sie zu beantworten, Professor Eppstein!
BlueRaja - Danny Pflughoeft
Ein Jahr und viel Lernen (meinerseits) später verstehe ich jetzt diesen Beweis und stimme ihm zu.
Nochmals vielen