Gitteralgorithmus puzzle
Ich habe ein Raster von einiger Breite und Höhe, wobei jede Zelle drei mögliche Werte haben kann (in dieser Abbildung als weiß, grün und rot dargestellt):
Illustration http://corexii.com/grid-algorithm-problem-2.png
Sie können eine beliebige Anzahl grüner Zellen auswählen (in der folgenden Abbildung blau markiert), die alle roten Zellen (gelb markiert) in einem vorbestimmten quadratischen Radius (hier 2 <) abdecken / strong>) um die ausgewählten Zellen:
Illustration http://corexii.com/grid-algorithm-problem-3.png
Das Ziel ist:
- Bedecke so viele rote Zellen wie möglich
- Verwenden Sie so wenig blaue Zellen wie möglich
- Mach es so schnell wie möglich
Hat jemand Ideen für einen Algorithmus?
Ich betrachte eine Menge Theorie, aber am meisten interessiert mich eine Annäherung, um das schnell zu tun, anstatt genau. Ein schnelles, vernünftiges Ergebnis ist besser als das Berechnen des optimalen Tages.
(Die obigen Abbildungen stellen möglicherweise die normalste Verteilung dieser Zellen dar, sollten aber nicht so aussehen, als würden sie allen möglichen Verteilungen ähneln.)
1 Antwort
Dieses Problem ist ein Spezialfall des wichtigen NP-hard Abdeckungsproblems . (Das Universum besteht aus den roten Zellen, und jede Menge besteht aus den roten Zellen innerhalb des Radius einer der grünen Zellen.) Greedy Algorithmus wird innerhalb eines log n Faktors des optimalen Ergebnisses gefunden.
templatetypedef ist richtig, darauf hinzuweisen , dass dieses Problem ein besonderes ist Der Fall eines NP-harten Problems beweist nicht, dass es tatsächlich NP-schwer ist. Deshalb habe ich in meiner obigen Formulierung sorgfältig darauf geachtet, Letzteres nicht zu implizieren. Aber ein Sonderfall eines NP-schweren Problems ist ein Signal, das nicht ignoriert werden sollte: viele Spezialfälle stellen sich bei weiteren Untersuchungen als selbst schwerwiegend heraus.
Also hier ist eine grobe Skizze, dass dieses Problem in der Tat NP-schwer ist, durch eine Reduktion von VERTEX ABDECKUNG FÜR PLANARE GRAPHICS OF DEGREE AUF VIER VIER.
Nehmen wir an, wir haben einen ebenen Gradgraphen von höchstens vier, zum Beispiel:
Stellen Sie jede Ecke durch ein grünes Quadrat und jede Kante durch eine abwechselnde Kette von roten und grünen Quadraten so dar, dass eine gerade Anzahl von grünen Quadraten, eine ungerade Anzahl von roten Quadraten und jedes grüne Quadrat nur die zwei enthält rote Quadrate auf beiden Seiten, wenn gewählt. Bei einem Radius von 2 ist dies eine mögliche Repräsentation des Graphen:
Um alle roten Quadrate abzudecken, müssen wir mindestens die Hälfte der grünen Quadrate in jeder Kette wählen, die einer Kante des ursprünglichen Graphen entsprechen. Wenn wir genau die Hälfte der grünen Quadrate an jeder Kette wählen, bleibt ein unbedecktes rotes Quadrat an einem Ende jeder Kante übrig (und wir können wählen, welches Ende). Wir erhalten also die minimale Menge an grünen Quadraten, wenn wir die Mindestmenge von Scheitelpunkten finden können, so dass jede Kante auf einen Scheitelpunkt in dieser Menge trifft.
Im Beispiel können wir die roten Quadrate mit acht grünen Quadraten abdecken, wenn wir die Scheitelpunkte a und d :
wählen 
Und dies entspricht der minimalen Vertex-Abdeckung im ursprünglichen Graphen:
