Gegeben gewichteten Punkte auf einer Ebene, finden Plätze für U Plätze, so dass das Gesamtgewicht eingeschlossen maximiert werden würde

mich mit folgendem Problem konfrontiert:Gegeben gewichteten Punkte auf einer Ebene, finden Plätze für U Plätze, so dass das Gesamtgewicht eingeschlossen maximiert werden würde

Eine Reihe von Punkten Gegeben Auf einer euklidischen Ebene hat jeder Punkt P (x, y, w) Koordinaten und ein zugeordnetes positives Gewicht.
Eine Reihe von U Quadrate, die alle die gleiche Größe aufweisen Länge L.

Ziel:

Assign (Finden Plätze für) die Quadrate, so dass das Gewicht umschlossen Gesamtpunkte innerhalb Alle Quadrate wären maximiert.

Anmerkungen:

Die Quadrate sollte achsparallelen
Die Quadrate können sich überlappen, aber die eingeschlossenen Gewichte nicht mehr als einmal gezählt werden.

Ich bin auf der Suche nach einer optimale Zuordnung.

Meine Fragen:

Ist das ein bekanntes Problem (Hat es einen Namen hat es vorher erforscht worden?).
Irgendwelche Ideen, wie man es angehen kann?

(I erwartet werden kann, erwähnen, was habe ich versucht. Da ich für eine optimale Zuordnung bin auf der Suche, meine heuristische Ideen sind nicht wirklich relevant. An dieser Stelle habe ich keine Ahnung, wie die optimale finden Zuordnung).

Quelle

2013-08-27 Lior Kogan

Bitte erläutern Sie Ihre Definition eines U-Quadrats. Und durch eingeschlossen innerhalb aller Quadrate, meinen Sie nicht, dass die Punkte in der Ebene des Quadrats sein sollten, aber in einigen Kästen enthalten, wo jede Seite aus diesen achsparallelen Quadraten gemacht wird, oder sich mit anderen schneidet solche Boxen? –

@ RobertJørgensgaardEngdahl: U ist die Anzahl der gleich großen Quadrate, für die ich optimale Standorte finden möchte. Die Quadrate befinden sich auf derselben Ebene wie die Punkte (dies ist ein 2D-Problem). –

Können Sie ein Bild hinzufügen, was das Programm in 2D tun soll? – jambono

Es ist ein geometrischer Sonderfall der gewichteten maximum coverage problem. Der allgemeine MCP ist NP-schwer, und ich vermute, dass dieser Sonderfall auch so ist, obwohl er im Gegensatz zum allgemeinen Fall wahrscheinlich ein effizientes Polynom-Zeit-Approximationsschema hat. Sie möchten jedoch eine optimale Lösung, daher ist das erste, was ich empfehlen würde, die Ganzzahl-Linear-Programmierung-Formulierung in dem verlinkten Wikipedia-Artikel zu einem LP-Solver zu füttern.

maximize sum_j (w_j * y_j) 
subject to 
for all i, sum_i x_i <= U 
for all j, sum_{i : j in S_i} x_i - y_j >= 0 
for all i, x_i in {0, 1} 
for all j, 0 <= y_j <= 1

Das Gewicht w_j jeden Punkt j gegeben wird, und die Sätze S_i sind alle Möglichkeiten für die Punkte mit einer Breite L Quadrat abdeckt. Die Bedeutung von x_i ist, ob S_i gewählt ist. Die Bedeutung von y_j ist, ob Punkt j abgedeckt ist. Der einfachste kubische Algorithmus zum Konstruieren der S_i s ist das Aufzählen aller Quadrate, deren unterer linker Scheitelpunkt eine x-Koordinate hat, die gleich der eines Punktes ist, und y-Koordinate gleich der eines (möglicherweise anderen) Punkts, da jedes andere Quadrat nach oben und nach unten geschoben werden kann/oder nach rechts, ohne die Abdeckung zu opfern.

Quelle

2013-08-27 13:31:16

Dank David: Haben Sie zufällig einen Hinweis auf eine ausführlichere Beschreibung einer Methode zum Aufbau von S_i? (Welche Datenstrukturen zu verwenden, etc.) –

@LiorKogan Ich habe keine Referenz handy, da ich gerade darüber nachgedacht.In etwas mehr Details ist der Algorithmus zu sammeln und sortieren die x-Koordinaten der Punkte sammeln und sortiere die y-Koordinaten der Punkte, für x in den x-Koordinaten, für y in den y-Koordinaten, scanne durch die anderen Punkte, um zu sehen, welche zu dem Quadrat der Breite L gehören, deren linke Seite die x-Koordinate x und hat wessen Unterseite hat y-Koordinate y. Ich vermute, dass es kontraproduktiv wäre, Datenstrukturen hier zu verwenden, da das Lösen des ganzzahligen Programms eine Weile dauern wird. –

Gegeben gewichteten Punkte auf einer Ebene, finden Plätze für U Plätze, so dass das Gesamtgewicht eingeschlossen maximiert werden würde

Antwort

Verwandte Themen