Suche Implementierung zum Two-Center Problem
- Themenstarter manu8
- Beginndatum
Hi,
kenne das Problem nicht, hast du hier bitte einen Wikipedia Artikel o.ä? Finde da bei Google mehrere Möglichkeiten / andere Namen.
Grüsse,
BK
kenne das Problem nicht, hast du hier bitte einen Wikipedia Artikel o.ä? Finde da bei Google mehrere Möglichkeiten / andere Namen.
Grüsse,
BK
Hi, es gibt auch das k-Center Problem auch facility location problem genannt. Es gibt auch das One-Center Problem Smallest-circle problem - Wikipedia. Alle haben gemeinsam, dass z.B. eine Punktmenge in der Ebene vollständig durch Kreise abgedeckt werden soll. Beim Two-Center Problem sind es 2 Kreise. Wird verwendet um z.B. den optimalen Ort für die Errichtung eines Krankenhauses zu finden (Krankenhaus wird dann genau im Zentrum dieses Kreises errichtet), sodass alle umliegenden Einwohner einen möglichst kurzen Anfahrtsweg haben bzw. die Entfernung des am weitesten entfernten Einwohners minimal ist. 2-center problem - Google-Suche
Grüsse
Grüsse
Technipion
Erfahrenes Mitglied
Hi,
Gruß Technipion
Bei sowas bitte immer nen Link (oder ggf. den Code selbst) dazu posten. Beim Programmieren gibt es viele Schritte, und das eigentlich Umschreiben in die Zielsprache kommt erst relativ zum Schluss. Wenn du also schon einen fertigen Algorithmus hast (der ggf. in C++ implementiert ist), bringt es einen Vorteil, den einfach nur in eine Programmiersprache zu übersetzen (in deinem Fall Python/Java), anstatt sich einen komplett neuen Algo auszudenken. Kurz gesagt: Jemand der C++ und Python/Java kann (z.B. ich), kann dir dann den Algo schnell übersetzen.
Okay, also du hast eine Menge von Punkten (scheinbar im 2D) und möchtest die Mittelpunkte/Radien von 2 Kreisen bestimmen, sodass ...? Sollen alle Punkte in den beiden Kreisen eingeschlossen sein und die Fläche minimal? Oder soll z.B. die Schnittmenge beider Kreise maximiert werden? Oder sollen die Kreise sich nicht überlappen? Am besten erklärst du kurz, was du willst.
Ich finde das ein bisschen frech, wenn der Fragesteller Google-Links postet. Damit unterstellst du uns ja, wir hätten unsere Hausaufgaben nicht gemacht. Aber wenn du die Frage hast und Hilfe von uns willst, müsstest du uns dann nicht die nötigen Informationen liefern, statt uns an Google zu verweisen?
Gruß Technipion
Vielen Dank für die Rückmeldung.
welcher in C++ implementiert wurde (Link: yuantailing/2-center).
Es sollen zwei möglichst kleine Kreise bestimmt werden, welche vereinigt aber die gesamte Punktmenge enthalten, d.h. die Radien der Kreise sollen minimal sein (und damit soll auch die Fläche minimal sein). Die Zentren stellen somit den Ort dar, welcher zu den Punkten im entsprechenden Kreis die minimale Entfernung darstellen. Die Kreise können sich dabei auch überlappen (damit kann auch eine Schnittmenge existieren, welche aber nicht maximiert werden soll), können aber auch separariert sein. Oder in anderen Worten: die maximale Distanz, welche ein Punkt zum Zentrum des Kreises, in welchem er sich befindet, soll minimal sein.
Sorry, aber das war nicht meine Absicht jemanden zu unterstellen er hätte seine Hausaufgaben nicht gemacht. Den Google-Link hatte ich gepostet da er viele Zeichnungen zum k-Center Problem enthält und man es sich dadurch evtl. leichter vorstellen kann.
The k-Center Problem
Es handelt sich um folgenden Algorithmus https://link.springer.com/content/pdf/10.1007/PL00009311.pdf
welcher in C++ implementiert wurde (Link: yuantailing/2-center).
Es sollen zwei möglichst kleine Kreise bestimmt werden, welche vereinigt aber die gesamte Punktmenge enthalten, d.h. die Radien der Kreise sollen minimal sein (und damit soll auch die Fläche minimal sein). Die Zentren stellen somit den Ort dar, welcher zu den Punkten im entsprechenden Kreis die minimale Entfernung darstellen. Die Kreise können sich dabei auch überlappen (damit kann auch eine Schnittmenge existieren, welche aber nicht maximiert werden soll), können aber auch separariert sein. Oder in anderen Worten: die maximale Distanz, welche ein Punkt zum Zentrum des Kreises, in welchem er sich befindet, soll minimal sein.
Sorry, aber das war nicht meine Absicht jemanden zu unterstellen er hätte seine Hausaufgaben nicht gemacht. Den Google-Link hatte ich gepostet da er viele Zeichnungen zum k-Center Problem enthält und man es sich dadurch evtl. leichter vorstellen kann.
The k-Center Problem
