Mittelpunktberechnung

...komplette Frage anzeigen

4 Antworten

Geht es um Entfernung, oder um Fahrzeit ?

Allgemein kannst Du nicht erwarten, dass alle etwa gleiche Strecke oder Zeit haben, manche werden eben mehr in der Mitte wohnen ( im Extremfall könnte es ja sein, dass die 7. Familie grade da wohnt wo für die anderen 6 der günstigste Treffpunkt ist ... )

Es kann auch so liegen, dass es vernünftiger wäre wenn eine der Familien in den sauren Apfel beisst und eine weite Anreise in Kauf nimmt, wenn dadurch die anderen 6 viel Entfernung sparen können ... ( angenommen 6 leben am Rhein und 1 in der Uckermark :-)

Praktisch würd ich so vorgehen: nimm das am weitesten auseinanderliegenden Paare und gib deren Wohnorte in einen Routenplaner, ermittle dann die Mitte "X" der Route (entweder die halbe Strecke oder die halbe Fahrzeit); dann check ab, welche Strecke bzw. Zeit die anderen laut Routenplaner zu diesem Punkt "X" haben. Wenn die 5 anderen es näher nach "X" haben, ist das die Lösung - ansonsten probiert ein anderes Paar.

Die beste Lösung muss so aussehen, dass mindestens 2 Familien es gleich weit haben - denn hätte es nur 1 Familie am weitesten, dann könnst man den Treffpunkt ein bischen näher zu dieser legen und das ergäbe eine bessere Lösung.

Es kann allerdings passieren, dass für kein Paar diese Bedingung erfüllt ist ( d.h. dass es für jedes Paar eine 3. Familie gibt, die es zum "Halben-Weg-Punkt" des Paares noch weiter hat ) - dann hast Du die Situation, dass 3 (oder noch mehr) Familien es gleich weit haben, und Du musst improvisieren, denn Routenplaner können das typischerweise nicht lösen. Es ist aber unwahrscheinlich, dass diese Fall eintritt, und darum würd ich mir den Kopf nicht im Voraus darüber zerbrechen.

Habe mal an einem konkreten Fall mit 6 Orten 4 verschiedene Algorithmen untersucht: siehe http://www.gerdlamprecht.de/GeometrischerSchwerpunkt.htm
0 = Flächenmittelpunkt (der Entfernteste aus Düsseldorf bekommt höchste Wichtung; Nachteil: Orte innerhalb der Fläche ohne Wichtung)
1 = Gravitations-Mittelpunkt (durch 1/r² bekommt der Entfernteste geringste Wichtung; optimal für Wolfsburg)
2 = Durchschnitt aller GPS Koordinaten
3 = minimale Distanz (min Summe aller Entfernungen; optimal für Magdeburg und Berlin)

Subjektiv gefällt mir Fall 0 am besten, da der Entfernteste nur so eine Chance gegen viele Einheimische hat: Beispiel "1 Japaner und 8 Ausralier"

Ökologisch (Benzinverbrauch) ist Fall 3=min(Summe(Distanzen)) natürlich optimal.

Versuch es mit einem Online-Routenplaner wie ViaMichelin o. ä.

rr1957 18.10.2012, 11:31

das ist aber nicht praktikabel - das würde für den Fall von 2 Familien, wenn eine in Lindau und die andere in Konstanz lebt, ein Treffen mittem im Bodensee vorschlagen ...

Es geht hier ja nicht um eine theoretische Aufgabe, sondern um einen Vorschlag der für alle Leute akzeptabel und möglichst überzeugend ist. Man will wahrscheinlich vor allem vermeiden, dass man das Treffen anleiert und vorbereitet, und dann kommt jemand mit einem klar besseren anderen Treffpunkts-Vorschlag und die ganze bisherige Vorbereitung ist dann für die Katz ...

0
Suboptimierer 18.10.2012, 11:50
@rr1957

Das Programm berechnet den mathematischen Mittelpunkt. Es berücksichtigt nicht, ob auf dem Mittelpunkt Gewässer sind oder eine Stadt, ein Wildgehege oder ein Hotel steht. Das dürfte generell schwierig werden, mathematisch zu berechnen.

Ich würde in dem Fall einfach die Bodenseelösung nehmen und schauen, welcher Ort am Bodensee meinen persönlichen Vorlieben am nächsten käme. Vielleicht noch eine oder zwei Alternativen anbieten und gut ist.

0
rr1957 24.10.2012, 11:25
@Suboptimierer

Das ist sehr wohl gut mathematisch behandelbar und nicht weiter schwierig:

  1. Gibt es überhaupt eine Lösung, ist die Aufgabe korrekt gestellt: nein, so wie in der Frage eben nicht - man kann im allgemeinen nicht erwarten, dass alle sieben einen gleich weiten kürzesten Weg haben.

  2. Wie erkennt man eine Lösung: mindestens 2 der Familien haben einen gleichlangen kürzesten Weg, und alle anderen einen noch kürzeren.

  3. Wie findet man eine Lösung: alle Orte in Deutschland durchprobieren, ob einer die Lösungsbedingung erfüllt ( sind ja nur endlich viele :-)

  4. Wie findet man eine Lösung mit weniger Aufwand: dafür sind die Informatiker zuständig ...

0
Suboptimierer 24.10.2012, 12:59
@rr1957

Das ist sehr wohl gut mathematisch behandelbar und nicht weiter schwierig

Die Koordinaten reichen aber alleine dann nicht aus. Als weitere Eingabeparameter müsste man, wie du schon zu Bedenken gegeben hast, die Lage von Gewässern, Gebirgen (hier ist Lufline sowieso schwierig zu nehmen) und sonstigen Hindernissen mit einbeziehen.

Wie erkennt man eine Lösung: mindestens 2 der Familien haben einen gleichlangen kürzesten Weg, und alle anderen einen noch kürzeren.

Das ist aber nur eine Lösungsstrategie. Der Fragesteller wollte den Mittelpunkt haben, von dem alle gleich entfernt liegen. Das geht natürlich nur, solange nicht drei Familien auf einer Geraden liegen, ist aber sonst problemlos (ohne Hindernisse) berechenbar, zum Beispiel mit dem von mir verlinkten App.

Wie erkennt man eine Lösung: mindestens 2 der Familien haben einen gleichlangen kürzesten Weg, und alle anderen einen noch kürzeren.

Dein Ansatz ist ein anderer. Du reduzierst deine Forderung darauf, dass es reicht, wenn zwei Familien einen gleichlangen Weg haben und alle anderen einen kürzeren. Das könnte so aussehen:

F1                                                F3
                                                     T
F2                                                     F4

Deiner Aussage (2.) nach würde man T als Lösung erkennen können, da mindestens zwei Familien einen gleich langen kürzesten Weg haben (F1 und F2), alle anderen einen noch kürzeren (F3 und F4).

man kann im allgemeinen nicht erwarten, dass alle sieben einen gleich weiten kürzesten Weg haben.

Zeige mir ein Beispiel ohne Hindernis (See, usw.) und ohne dass >=3 Familien auf einer Geraden wohnen, bei dem es nicht möglich ist, eine gemeinsame, kürzeste Strecke zu finden.

0
rr1957 07.04.2013, 22:01
@Suboptimierer

yep, da hast Du mich bei einem Fehler erwischt ... man muss dazu noch verlangen (wie ich es in meiner direkten Antwort ja auch getan habe) dass die beiden längsten kürzesten Wege ( also F1-T und F2-T ) zusammen einen kürzesten Weg ( für F1-F2 ) bilden.

Ansonsten ist es eben so, dass man praktisch das Thema Hindernisse hier nur so anpacken kann, dass man einen Routenplaner zugrunde legt; manuell kriegt man die Daten niemals gehandelt. Das ist aber mathematisch kein Problem - ein Routenplaner ist einfach eine Black-Box-Operation, die mir zu 2 beliebigen Orten einen kürzesten Pfad dazwischen liefern kann ( plus ggf. die Mitte dieses Pfades ).

0

Was möchtest Du wissen?