Ich habe N Punkte in einer Menge V gegeben durch ihre Koordinaten und eine Zahl K (0 & lt; K & lt; N). Ich muss K Kreise (Scheiben) mit dem gleichen Radius R bestimmen, mit ihren Zentren in Punkten in der V-Menge. Diese Kreise müssen alle N Punkte "abdecken" und R ist das kleinstmögliche.
Kann mir jemand dabei helfen?
Dieses Problem wird als (diskretes) $ k $ -Zentrenproblem bezeichnet und ist ein bekanntes Problem beim Clustering. Während das Problem im allgemeinen NP-vollständig ist, gibt es einen sehr einfachen Algorithmus, der eine Lösung innerhalb des Faktors 2 der optimalen Lösung in jeder Metrik (einschließlich der implizierten 2-D euklidischen Entfernung der Frage) erzeugt. Es ist wegen Gonzalez, und ist wie folgt
Der Radius R, mit dem Sie enden, ist der Abstand von diesem letzten Punkt zum nächsten entferntesten Punkt. Durch die Konstruktion werden Sie garantiert alle Punkte mit Scheiben mit einem Radius um jeden der k Punkte abdecken, und durch die Dreiecksungleichung liegt dieses R innerhalb eines Faktors von 2 des optimalen Radius.
Wenn Sie wissen, dass Sie in der Ebene sind, können Sie etwas besser in der Theorie tun (einschließlich eines genauen Algorithmus in Zeitpolynom in n und exponentiell in k), aber in der Praxis ist der obige Algorithmus wahrscheinlich der einfachste
Das von Ihnen beschriebene Problem ist ein Beispiel für ein allgemeineres Optimierungsproblem, bekannt als das Problem , das gelöst werden kann mit einer linearen Entspannungsprogrammierung . Sie können möglicherweise eine Kostenfunktion definieren, die im Radius R Ihrer Kreise linear ist (z. B. die Summe der Radien für alle Kreise), und in Anzeigenvariablen , die auswählen, welche Punkte zum Zeichnen der Kreise ausgewählt wurden. Diese Kostenfunktion würde unter Bedingungen definiert werden, die die Kreise zwingen, alle Punkte in Ihrem Set abzudecken (siehe Wikipedia-Artikel auf LP für Beispiele)
Sobald Sie die Kostenfunktion und die Einschränkungen definiert haben, gibt es mehrere Solver (viele von ihnen frei), die Sie verwenden können, um das Optimierungsproblem zu lösen.