Angenommen eine Menge von Punkten S in einer 2D-Ebene, wie die minimale Anzahl von Punkten von S entfernt werden kann, so dass die Abstände zwischen zwei verbleibenden Punkten nicht kleiner als eine Konstante ist, sagen wir R.Maximale Teilmenge von Punkten mit bestimmter Dichte
Ich denke, das könnte NP-schwer sein. Kann jemand eine schnelle ungefähre Lösung vorschlagen? Vielen Dank!
Mein Freund schlagen eine vernünftige Lösung:
Konstruieren Sie einen Graphen G, in dem alle Kanten sind weniger als R. Die Menge von Punkten ist die gleiche wie die minimale Knotenüberdeckung des Graphen G. Die Annäherung zu entferne der Vertex Cover ist in Polynomialzeit.
Ja, ich habe das gerade selbst geschrieben. Diese Approximation ist eine 2-Approximation, die nicht zu schlecht ist, aber Vertex Cover ist auch fester Parameter in der Lösungsgröße, so dass es bei ziemlich großen Instanzen genau gelöst werden kann, vorausgesetzt, nur eine kleine Anzahl von Vertices muss gelöscht werden . –
@j_random_hacker Sie beide Genie – GilbertLee
Dieser ist schnell, aber nicht die minimale Anzahl von Punkten. Beachten Sie, dass die Schleife Änderungen verarbeiten muss, um S festzulegen, wenn ein Punkt entfernt oder inaktiviert wird.
For each Point P1 in S
{
For each Point P2 after P1 in S
{
If (square(P1.x - P2.x) + square(P1.y - P2.y) < square(R))
{
remove (P2)
}
}
}
Für Minimum, aber teuer:
use double loop to store each P2 closest to P1
example: array [P1][P2]
Sort array based on size of array [P1].numOfElements()
such that largest is at the top
now remove top element P from set S
and in array P1
and all subsequent P in P2 of all P1
If P2 is empty for any element X in P1 then remove it
Remove the next top element and do the process again until array is empty
Resulting set is the answer for minimum points
Wenn es nur zwei Punkte und der Abstand kleiner als R, würde das Ergebnis in 0 Punkten? – Striker
@Striker 1 Punkt entfernen. Sie haben jetzt einen Punkt übrig und es hat keinen anderen Punkt näher als R. –
@Striker Ich denke schon. Es sollte leer gesetzt werden – GilbertLee