Suche Implementierung zum Two-Center Problem


manu8

Grünschnabel
#1
Hallo, ich suche nach einer fertigen Implementierung (vorzugsweise in Python oder Java) zum Two-Center Problem.
Leider fand ich bisher nur eine in C++.
Kann mir jemand einen Tipp geben?

Vielen Dank im voraus
 

manu8

Grünschnabel
#3
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
 

Technipion

Erfahrenes Mitglied
#4
Hi,
Leider fand ich bisher nur eine in C++.
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.

Beim Two-Center Problem sind es 2 Kreise. Wird verwendet um z.B. den optimalen Ort für die Errichtung eines Krankenhauses zu finden
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
 

manu8

Grünschnabel
#5
Vielen Dank für die Rückmeldung.

Hi,

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.
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).


Hi,

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.
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.



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
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