Suchen Sie eine Region mit der maximalen Summe der Top-K-Punkte

Sie können dieses Problem reduzieren, indem Sie zwei Punkte im Rechteck finden: ganz rechts und ganz oben. So effektiv können Sie jedes Punktepaar auswählen und das Top-K-Gewicht berechnen (das ist für Sie O (log (N) ^ 2 + k)). Komplexität: O (N ^ 2 * (log (N) ^ 2 + k)).

Wenn Sie nun zwei Punkte angeben, bilden sie möglicherweise kein gültiges Paar: Sie sind möglicherweise zu weit entfernt, oder ein Punkt kann rechts und oben am anderen Punkt liegen. In der Realität wird dies viel schneller sein.

Meine Vermutung ist, dass die optimale Lösung eine Variation des Summenproblems der maximalen Region sein wird. Können Sie auf einen Link verweisen, der diesen Algorithmus beschreibt?

Eine nicht optimale Antwort lautet wie folgt:

1. Generiere alle möglichen k-Punkte von Punkten (sie sind N × N - 1 × ... × N-k + 1, also ist dies O (N )) und kann sein getan durch Rekursion).

2. Filtern Sie diese Liste, indem Sie alle k-plets ausschließen, die nicht in ein aa × b-Rechteck eingeschlossen sind: das ist im schlimmsten Fall ein O (k N ).

3. Finden Sie die k-plet, die das maximale Gewicht hat: das ist im schlimmsten Fall ein O (k N ).

Somit ist dieser Algorithmus O (k N ).

Verbesserung des Algorithmus

Schritt 2 kann in Schritt 1 integriert werden, indem die Verzweigungsrekursion gestoppt wird, wenn eine Menge von Punkten bereits zu groß ist. Dies ändert nichts an der Notwendigkeit, das Element mindestens einmal zu scannen, aber es kann die Anzahl signifikant reduzieren: Denken Sie an Fälle, in denen es keine Lösungen gibt, da alle Punkte mehr als die Größe des Rechtecks ​​getrennt sind, das in O gefunden werden kann. N ² ).

Außerdem kann der Permutationsgenerator in Schritt 1 veranlasst werden, die Punkte in der Reihenfolge nach x- oder y-Koordinaten zurückzugeben, indem das Punktarray entsprechend vorsortiert wird. Dies ist nützlich, weil wir dadurch eine Menge mehr Möglichkeiten im Voraus verwerfen können. Angenommen, das Array ist nach y-Koordinate sortiert, sodass die zurückgegebenen k-plets nach y-Koordinate geordnet sind. Wenn wir jetzt einen Zweig verwerfen, weil er einen Punkt enthält, dessen y-Koordinate außerhalb des maximalen Rechtecks ​​liegt, können wir auch alle nächsten Geschwisterzweige verwerfen, weil ihre y-Koordinate größer ist als die gleiche, die bereits überschritten wurde Grenzen.

Dies fügt O (n log n) für die Sortierung hinzu, aber die Verbesserung kann in vielen Fällen ziemlich signifikant sein - wiederum, wenn es viele Ausreißer gibt. Die Koordinate sollte entsprechend der minimalen Rechteckseite gewählt werden, dividiert durch die entsprechende Seite des 2D-Feldes - womit ich die maximale Koordinate minus der minimalen Koordinate aller Punkte betrachte.

Wenn schließlich alle Punkte innerhalb eines a × b-Rechtecks ​​liegen, dann führt der Algorithmus als O (k N ) durch. Wenn dies eine konkrete Möglichkeit ist, sollte es überprüft werden, eine einfache O (N) -Schleife, und wenn es so ist, dann reicht es, die Punkte mit den oberen N Gewichtungen zurückzugeben, was auch O (N) ist.