Minimale Anzahl der Kreise mit radius r um die n-Punkte
Was ist die minimale Anzahl von Kreisen mit radius r benötigt, um alle n Punkte?
r und n gegeben werden, die als Eingabe, gefolgt von der n Paare von Ganzzahlen, die die x-y-Koordinaten der n Punkte.
r ist eine reelle Zahl und größer als 0 ist. n < 20.
Kreis deckt einen Punkt, wenn der Punkt liegt innerhalb des Kreises.
Ein Punkt liegt in einem Kreis, falls der Abstand zwischen dem Punkt und dem Kreismittelpunkt kleiner als oder gleich r.
- Dies ist nicht eine Frage der Programmierung? Wissen Sie, es gibt eine Sache, genannt wettbewerbsfähige Programmierung? Ich versuche, ein problem zu lösen, und ich erkannte, dass ich zur Lösung dieses sub-problem zunächst. Warum denkst du, jeder fragt Sie um Ihre Hausaufgaben zu tun für Sie?
- Fragen wie diese sind in der Regel akzeptabel, aber es hilft immer, um zu zeigen, einige versuchen zu lösen das problem selbst zuerst. @PhillipSchmidt Das klingt wie eine Programmierung Frage an mich.
- Ich dachte an eine 2^n * 2^n-Lösung, aber das ist nicht zur Arbeit zu gehen, als n werden kann, 20. Ich denke, es existiert ein n * 2^n oder n^2 * 2^n-Algorithmus, kann aber nicht herausfinden.
- Die VC-dimension der Platten ist 3, also gibt es O(n^3) unterschiedliche Kreise mit Bezug auf die die angegebenen Punkte...
- Eisenstat, was soll das bedeuten? O(n^3) verschiedene Kreise? Von wo hast du das?
- Sauer ' s lemma
- Danke, aber ich weiß nicht wirklich verstehen, was das bedeutet. Können Sie erklären, wie aufwändig das löst mein problem?
- Sie haben immer zu Fragen, wenn etwas ausgelassen wird beim kopieren ein problem wie dieses. Die x -, y-Punkte Ganzzahlen scheint nicht zu helfen, aber natürlich würde es helfen, eine Tonne, wenn zum Beispiel die Kreis-Zentren wurden intergral.
- Fragen auf, SO sollen in der Lage sein, zu beantworten in einem Programmier-Kontext. Siehe hier. Diese Frage wäre wesentlich besser geeignet für Mathematik.SO
- Ich habe gesehen, 1000er ähnlich (nicht geschlossene) Fragen (es ist "ein software-Algorithmus"). Diese Probleme sind wahrscheinlich 100 mal schwieriger zu lösen, mit der Mathematik als algorithmen, so Mathematik ist wahrscheinlich nicht der richtige Ort. Wenn Sie jemals Lesen ein Buch algorithmen, dann sollten Sie wissen, dass diese Arten von Problemen sind ein großer Teil der Computer-Wissenschaft, und Sie braucht auf jeden Fall ein Ort, der vor allem hier zur Zeit (auch on-topic für informatik, aber Sie sind etwas ungewöhnlich, es). Es kann nicht eine echte Frage, der aktuelle Zustand, aber das bedeutet nicht, es ist off-topic.
- Ich wäre glücklich mit entweder einigen Aufwand gezeigt, oder den Zusammenhang, um zu zeigen, dass dies nicht nur "bitte mache meine Hausaufgaben'.
- wow vielen Diskussionen -- jemand darauf, zu versuchen, Ihren code auf dieses Beispiel..r=3 Punkte = {{3, 7}, { -6, -10}, {4, -7}, { -9,2}, { -4,-4}, {3, -1}, {7, -3}, {10, -1}, { -1, -6}, { -1, 3}, { -9, -3}, {9, -4}, { -4, 7}, {2, -7}, { -2, -10}, { -10,6}, {9, -8}, { -5, 5}, {6, 4}, { -4, -7}} Meine Antwort N=9 ..
- Bekomme ich 10 Kreise.
- Denken Sie an diese relative, aber einfacheres problem: mit n Punkten in einer Linie, finden Sie die minimale Anzahl der Liniensegmente der Länge l, die alle Punkte.
- Sie sind bereit, die ein etwas anderes problem, es sollte wohl eine neue Frage. Sie sind ok mit der
n<20
Bestimmung??? - Ich dachte, ich würde bounty hier, weil das ist, wo die Diskussion ist. n < 1000 wäre meine persönliche Bedingung. Eine Lösung für alle n wäre toll, obwohl, ich weiß, das ist ein sehr teures problem.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist nicht die beste Lösung ist wahrscheinlich, aber, und versuchen, es zu optimieren.
Algorithmus basiert auf der zufälligen Stichprobe:
Hier ist der code, können Sie eine Vorschau Leben: http://jsfiddle.net/rpr8qq4t/ Beispiel Ergebnis (13 Kreise je 30 Punkte):
Parametrisierungen:
Einige Optimierungen Hinzugefügt werden kann (zum Beispiel einige Kreise können von der Liste ausgenommen zu früh)
Bearbeiten:
Neue version: http://jsfiddle.net/nwvao72r/3/
Edit 2 (final-Algorithmus)
Schließlich:
Hier ist die version, die Sie bringt die besten Ergebnisse für mich, Sie können überprüfen Sie es hier http://jsfiddle.net/nwvao72r/4/
durchschnittlich 12 Kreise pro 30 Punkte hier.
Ich bin mir sicher, dieses problem ist NP-schwer, aber ich werde nicht versuchen und beweisen, dass hier.
Wenn es NP-hart, dann finden garantiert die optimale Lösung empfehle ich die folgende Vorgehensweise:
Guten Kreis Platzierungen
Gegeben, 2 Punkte weniger als 2r abgesehen, gibt es genau zwei Kreise mit dem radius r, die gehen durch diese Punkte:
[EDIT: Meine ursprüngliche Beschreibung von "best-möglich" - Kreisen war falsch, obwohl dies nicht zu Problemen führen, die Dank der Kommentator george für die Beschreibung der richtige Weg, um darüber nachzudenken.]
Wenn ein Kreis umfasst eine maximale Anzahl von Punkten (dies bedeutet, dass der Kreis kann nicht neu positioniert werden, um denselben Satz von Punkten plus mindestens 1 mehr), dann wird dieser Kreis kann aufgeschoben werden, um bis zu seiner Grenze berührt, die genau zwei der Punkte, die es abdeckt-sagen, durch schieben nach Links, bis es berührt, eine bereits gedeckte Stelle, und dann drehen Sie es im Uhrzeigersinn um diesen Punkt berührt, bis es berührt einen anderen bereits abgedeckt, Punkt. Dieser Kreis bewegt wird, decken genau die Punkte, die der ursprüngliche Kreis abgedeckt. Zudem haben wir nie überlegen müssen Kreise, dass bei nicht-maximalen Mengen von Punkten, da die maximale Kreis-über diese Punkte und mehr ist mindestens ebenso nützlich und kostet nicht mehr. Dies bedeutet, dass wir nur jemals brauchen, um Bedenken Kreise, berühren Sie zwei Punkte. Vorausgesetzt, wir erzeugen die beiden Kreise für jeden ausreichend-in der Nähe paar Punkte in den input, wir werden erzeugt haben alle die Kreise, wir könnten potenziell brauchen.
Also unser pool von potentiellen Kreise enthält höchstens 2 Kreise pro paar Punkte, maximal n*(n-1) mögliche Kreise insgesamt. (Wird es in der Regel weniger, da einige Paare der Punkte wird in der Regel weiter als 2r auseinander und somit nicht gedeckt werden kann, durch einen Kreis mit radius r.) Darüber hinaus brauchen wir ein extra Kreis für jeden Punkt, der weiter als 2r von alle anderen Punkt -- diese Kreise könnten auch mittig auf der entfernten Punkte.
Set cover
Alles, was wir eigentlich interessiert, ist die Menge der Punkte von jedem potenziellen Kreis. Also für jeden potenziellen Kreis, finden die Punkte, die es abdeckt. Dies kann durchgeführt werden in O(n^3) insgesamt mit O(n) pass für jeden potenziellen Kreis. Um die Dinge zu beschleunigen leicht, wenn wir feststellen, dass zwei verschiedene Kreise decken genau den gleichen Satz von Punkten, wir müssen nur zu halten eine von diesen Kreisen (Mengen bedeckt Punkte). Auch können wir verwerfen jede gedeckten Punkt zu setzen, das eine Untermenge einige andere bedeckt, zeigen Sie Satz -- es ist immer besser, wählen Sie die größere überdachte Punkt-Satz in diesem Fall.
Schließlich haben wir eine Sammlung der erfassten Punkt setzt, und wir wollen, zu finden, die minimale Teilmenge dieser Gruppen, die deckt jeden Punkt. Dies ist die set cover problem. Ich weiß nicht, von einem bestimmten Algorithmus um dieses Problem zu lösen, aber branch-and-bound ist die standard-Vorgehensweise für solche Probleme -- es ist Häufig sehr viel schneller als ein einfacher erschöpfend backtracking-Suche. Ich würde zuerst Grundieren Sie die Suche durch das finden einer (oder mehr) heuristische Lösungen erste, hoffentlich was eine gute Obere Schranke, die die branch-and-bound-Suche Zeit. Ich denke, dass selbst die besten algorithmen für diese exponentielle Zeit im schlimmsten Fall, obwohl ich denke, das wird überschaubar sein, für die n < 20 wie es bei den meisten 19*18 = 342 unterschiedliche Mengen von Punkten.
Mir ist klar, dass die Kreise müssen nicht zentriert werden an die Punkte und so berechnen Sie alle Kreise, die durch keine Kombination von zwei Punkten, einschließlich Kreise zentriert an jedem Punkt.
Wie finde ich dann die Punkte jeder Kreis umfasst und die Verwendung eines greedy-Algorithmus zum finden einer minimalen Anzahl von Kreisen zur Abdeckung aller Punkte, aber wieder, es kann nicht sein die minimalen Satz von Kreisen, aber ist ziemlich einfach zu berechnen.
Die Ausgabe zeigt die drei Läufe:
Kachel, dann wackeln
Schritt 2, die Fliesen könnte optimiert werden durch den ausbau Trog jeden Punkt und Berechnung/halten nur jene Kreise, die enthalten würde, ein Punkt, wenn die Fliesen wäre sehr spärlich.
Vom Papier "Auf der Diskreten Unit Disk Cover Problem" von Gautam K. Das et. al.:
Referenzen:
Wenn Kreis mit Mittelpunkt
C(cx, cy)
deckt PunktP(px, py)
dann Abstand|CP| < r
(r
- radius).So-region, wo Mitte des Kreises werden könnte, deckt Punkt
P
ist ein Kreis mit Mittelpunkt inP
und radiusr
. Jetzt ziehen lässt alle Kreise mit Zentren in der gegebenen Punkte und radiusr
. Wenn einige Kreise schneidet, dann können wir zeichnen den neuen Kreis mit Mittelpunkt in einer solchen Kreuzung, deckt die entsprechenden Punkte.Also für jedes paar von Eingang Punkte, die wir überprüfen, ob die Kreise schneidet.
Angenommen Eingabe Punkte sind Eckpunkte und den Schnittpunkt bekommt Kante zwischen Ihnen.
Jetzt haben wir eine bekannte Grafik problem minimum edge-Abdeckung http://en.wikipedia.org/wiki/Edge_cover, die gelöst werden konnten, die in polynomieller Zeit (wenn auch mit Einschränkung
n < 20
brute-force-wahrscheinlich wäre akzeptabel)UPDATE. Das ist nicht edge-Abdeckung. Mein Fehler.
Dies ist meine erste Antwort die ich verlassen, wie es genannt wird, von einem anderen beantworten. Aber siehe meine später Antwort der Auffassung, dass die Kreise zwischen zwei Punkten anstatt dieser.
Hier ist ein greedy-Algorithmus, codiert in Python finden eine minima, aber ich weiß nicht, ob es ist die minimal-Lösung.
Und hier ist ein Beispiel ausgeführt:
Hinweis: die Daten-i/o ist rudimentär, aber der algo sollte klar sein
Ich bin mir nicht sicher ob das stimmt, aber wenn wir das nicht tun, müssen die genauen Standorte der Lösung-Kreise, es scheint mir, dass wir möglicherweise in der Lage, dies zu lösen, durch das betrachten von Punkt-Clustern: in jedem der Lösung-Kreise, die die Entfernung zwischen zwei Punkten sollte sein weniger als oder gleich 2 ist,*r.
Algorithmus:
Ausgang für gleichseitiges Dreieck, r=3, [(0,0),(5.196152422706632,3),(5.196152422706632,-3)]
Ausgang für Paddy3118 Beispiel, r=3, [(1,3),(0,2),(4,5),(2,4),(0,3)]:
Ausgang für r=3, [(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)]:
Haskell-Code:
r=3, [(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)]
von 4 auf 3 Kreise.Wenn Sie
n
Kreise (mit radiusr
) zentriert an jedem Punkt der finden Regionen/Punkte der maximalen überlappung und neue Kreise (mit radiusr
) zentriert in dieser region. Ich bin mir nicht sicher, ob dies der beste Weg ist, die Lösung die Lösung (wenn dies ist ein Weg, es zu lösen, außer der brute-force-Weg), ich bin mir sicher, dass Sie implementieren können, mit einem Recht anständigen Betrag der Mathematik, und somit die Reduzierung der Laufzeit-Komplexität der Lösung. Hoffe, das hilft. Bitte geben Sie feedback.