Ein genetischer Algorithmus kann hier wahrscheinlich gute Ergebnisse liefern.

update :

Ich habe ein wenig mit diesem Problem gespielt und das sind meine Ergebnisse:

Eine einfache Methode (nennen wir es Zufallsauswahl), um eine Menge von Punkten zu erhalten, die die angegebene Bedingung erfüllen, ist wie folgt:

1. Beginnen Sie mit B leer
2. wähle einen zufälligen Punkt x von A und lege ihn in B
3. entferne von A an jedem Punkt y so dass dist (x, y) & lt; d
4. während A nicht leer ist, gehe zu 2

Ein kd-Baum kann benutzt werden, um die Suche in Schritt 3 relativ schnell durchzuführen.

Die Experimente, die ich in 2D durchgeführt habe, zeigen, dass die generierten Teilmengen etwa halb so groß sind wie die, die von Ihrem Top-Down-Ansatz generiert werden.

Dann habe ich diesen Random-Selection-Algorithmus verwendet, um einen genetischen Algorithmus zu erzeugen, der zu einer weiteren 25% igen Reduktion der Größe der Teilmengen führte.

Für die Mutation, indem ich ein Chromosom gebe, das eine Teilmenge B darstellt, wähle ich zufällig einen Hyperball innerhalb der minimalen Achse-ausgerichteten Hyperbox, die alle Punkte in A abdeckt. Dann entferne ich alle Punkte, die sich auch im Hyperball befinden Verwenden Sie die Zufallsauswahl, um es erneut zu vervollständigen.

Beim Crossover verwende ich einen ähnlichen Ansatz und verwende einen zufälligen Hyperball, um die Mutter- und Vaterchromosomen zu teilen.

Ich habe alles in Perl mit meinem Wrapper für GAUL Bibliothek (GAUL kann von hier bezogen werden.

Das Skript ist hier: Ссылка

Es akzeptiert eine Liste von n-dimensionalen Punkten von stdin und erzeugt eine Sammlung von Bildern, die die beste Lösung für jede Iteration des genetischen Algorithmus zeigt. Das Begleitskript Ссылка kann verwendet werden, um die zufälligen Punkte mit a zu erzeugen gleichmäßige Verteilung.

Sie können Ihr Problem mit Graphen modellieren, Punkte als Knoten annehmen und zwei Knoten mit Kante verbinden, wenn ihre Entfernung kleiner als d ist. Jetzt sollten Sie die Mindestanzahl von Scheitelpunkten finden, so wie sie sind mit ihren verbundenen Knoten decken alle Knoten des Graphen, dies ist minimale Vertex Abdeckung Problem (die NP-Hard im Allgemeinen ist), aber Sie können schnelle 2-Approximation verwenden: wiederholt beide Endpunkte einer Kante in die Eckenabdeckung und entfernt sie dann aus dem Graph.

P.S: sicher, dass Sie Knoten auswählen sollten, die vollständig vom Graphen getrennt sind. Nachdem Sie diese Knoten entfernt haben (dh sie ausgewählt haben), ist Ihr Problem die Vertex-Abdeckung.

Hier ist ein Vorschlag, der eine Annahme der Manhattan-Distanz-Metrik macht:

1. Teilen Sie den gesamten Raum in ein Raster der Granularität auf d. Formal: Partition A, so dass die Punkte (x1, ..., xn) und (y1, ..., yn) genau dann in derselben Partition liegen, wenn (Boden (x1 / d), ..., Boden (xn / d )) = (Boden (y1 / d), ..., Boden (yn / d)).
2. Wählen Sie einen Punkt (beliebig) aus jedem Rasterbereich aus, dh wählen Sie einen Vertreter aus jedem Satz in der in Schritt 1 erstellten Partition. Machen Sie sich keine Sorgen, wenn einige Rasterfelder leer sind! Wählen Sie einfach keinen Vertreter für diesen Bereich.

Tatsächlich muss die Implementierung keine wirkliche Arbeit leisten, um Schritt eins zu machen, und Schritt zwei kann in einem Durchgang durch die Punkte ausgeführt werden, wobei ein Hash der Partitionskennung (der (floor (x1 / d) , ..., floor (xn / d))), um zu überprüfen, ob wir bereits einen Vertreter für einen bestimmten Rasterraum ausgewählt haben, dies kann sehr, sehr schnell erfolgen.

Einige andere Entfernungsmetriken können möglicherweise einen angepassten Ansatz verwenden. Zum Beispiel könnte die euklidische Metrik d / sqrt (n) -Größe verwenden. In diesem Fall möchten Sie möglicherweise einen Nachbearbeitungsschritt hinzufügen, der versucht, die Deckung ein wenig zu reduzieren (da die oben beschriebenen Gitter nicht mehr genau die Kugeln mit Radius-d sind - die Kugeln überlappen benachbarte Gitter etwas), aber ich ' Ich bin mir nicht sicher, wie dieser Teil aussehen würde.