Kürzeste Entfernung Reisen - gemeinsame Treffpunkt
Stieß ich auf dieses problem, wobei es gibt eine Reihe von Häusern auf einer 2-D-Gitter (Ihre Koordinaten gegeben sind) und die wir im wesentlichen zu finden, welches Haus genutzt werden kann als Treffpunkt, so dass die Strecke durch alle minimiert. Lassen Sie uns annehmen, dass ein Abstand entlang der x-oder y-Achse 1 Einheit und ein Abstand der diagonalen Nachbarn nimmt (sagen) 1.2 Einheiten.
Ich nicht wirklich glaube, eine gute Optimierungs-Algorithmus für diese.
P. S: Keine Hausaufgaben-problem. Und ich bin nur auf der Suche nach einem Algorithmus (nicht der code) und wenn möglich, die Beweis.
P. S #2: ich bin nicht auf der Suche für die ausführliche Lösung. Ob Sie es glauben oder nicht, das hat mich erschlagen 🙂
- Es ist ein minimierungsproblem über die ganzen zahlen Domäne. Beweise sind in der Regel nicht trivial ...
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wie bereits erwähnt, im Fall von Manhattan-Distanz der median gibt eine Lösung. Dies ist eine offensichtliche Schlussfolgerung, die die gut bekannte Tatsache, dass der median minimiert die mittlere absolute Abweichung:
E|X-c| >= E|X-median(X)|für jede Konstantec.Werden und hier kann man ein Beispiel finden, den Beweis für den diskreten Fall:
https://stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315
Das ist wohl wirklich ineffizient, aber eine Schleife durch alle Häuser, dann eine Schleife durch alle anderen Häuser. (geschachtelten for-Schleifen) Verwenden, die Abstand Formel zu finden, der Abstand zwischen den 2 Häusern. Dann haben Sie den Abstand zwischen jedem Haus. Eine schnelle und einfache Möglichkeit zu finden, das Haus ist der nächste Abstand hinzufügen, um jeden Fuß zusammen für das Haus. Das Haus mit den wenigsten insgesamt zu Fuß ist der Treffpunkt der Wahl.
Distanz-Metrik ist seltsam. Sie würden erwarten, dass Reisen auf die Diagonale sollte mindestens sqrt(2) ~= 1.41-fache der Distanz von einer Fahrt entlang einer Komponente der Richtung, denn das ist, wie viel weiter ist es, wenn Reisen in einer geraden Linie entlang der diagonalen durch den Satz des Pythagoras.
Wenn Sie darauf Bestand, ein manhattan-Distanz (keine diagonalen erlaubt), dann würden Sie wollen, wählen Sie das Haus am nächsten zum Mittelwert(x) + median(y) der Häuser.
Betrachten die 1D-Fall, Sie haben eine Reihe von Punkten auf einer Linie, und Sie möchten Holen Sie den Treffpunkt. Für die Konkretheit/Einfachheit, sagen wir mal es gibt 5 Häuser, keine doppelte.
Überlegen, was passiert, als der Treffpunkt driftet Weg von der Mediane nach rechts. Für jede Einheit Weg, bis Sie den pass das 4. Haus Links nach rechts um, 3 Leute haben in einem weiteren Schritt auf der rechten Seite, und 2 Menschen ein kleiner Schritt, um den linken, also die Kosten geht durch 1. Nach dem 4. Haus, dann 4 Leute haben, um einen zusätzlichen Schritt nach rechts, und eine einzelne person ein kleiner Schritt, um den linken, so dass die Kosten erhöht durch 3. Eine identische argument hält, wie Sie bewegen den Treffpunkt nach Links von der Mediane. Weg von der median stets zu einer Erhöhung der Kosten.
Dem argument verallgemeinert auf eine beliebige Anzahl von Personen, mit oder ohne doppelte Häuser, und sogar in der zum beliebigen Anzahl von Dimensionen, so lange wie Sie sind nicht erlaubt, verwenden Sie die diagonalen.
Ich wurde abgehört, die durch das gleiche problem seit einiger Zeit. Die Lösung ist die offensichtliche Konsens gegeben, der in früheren posts: finde den median (mx, my) unabhängig und suchen Sie dann den nächsten Punkt in der gegebenen N Punkte, und das ist der Treffpunkt. Um zu sehen, warum dies ist eigentlich die Lösung, die Sie sollten zunächst prüfen, die Entfernung.
d = sum(|xi-x|) + sum(|yi-y|) über alle 1<=i<=N,
unabhängig in x und y. Daher können wir lösen die 1-D Fall für die x-und y. Werde ich überspringen, die Erklärung ^^ und daher schließen, dass (mx,my) ist die beste Lösung wenn betrachten wir alle möglichen Punkte.Die größere Herausforderung ist es, zu beweisen, dass wir uns bewegen können, von (mx, my) zum nächsten (xi,yi), so dass (xi, yi) ist einer der gegebenen Punkte, w/o änderung(Erhöhung) der Abstand. Der Beweis geht:
Bedenken Sie, dass wir sortierten x-Koordinaten( für sake für den Nachweis ) und
dass
X1<X2<...<Xn. AuchXj<mx<X(j+1)woj = N/2, lassen Sie uns nun bewegenmxeinen Schritt nach Links, das ist
mx' <- mx-1.Daher
d' = |X1-mx+1| + .. + |Xj-mx+1| + |X(j+1)-mx+1| + .. + |Xn-mx+1|Wir wissen, dass die mx-1 erhöht N/2 Werte( für k>=j+1 und zu verringern
für <=j ) und somit der Effekt ist der gleiche. Damit (mx-1, min) gibt die gleiche
Lösung. Es bedeutet, dass es ist ein Raum, aus
Xj<mx<X(j+1)undYj<my<Y(j+1)wo der Abstand nicht ändert. So können wir finden, dieam nächsten Punkt, das ist die Antwort.
Ich ignorierte die subtilen Fall von geraden/ungeraden Knoten, aber ich hoffe, dass die Mathematik funktioniert selbst, wenn Sie begreifen, dass die grundlegenden Beweis.
Dies ist mein Erster Beitrag, nicht helfen, mich zu verbessern, mein schreiben Fähigkeiten.
Dein problem nennt Optimalen Treffpunkt zu Finden.
Der folgende Beitrag gibt eine Ungefähre Algorithmus, effizienter
http://www.cse.ust.hk/~wilfred/Papier/vldb11.pdf
Gut, man könnte brute-force-it. Nehmen jedes Haus und berechnen Sie die Entfernung zu jedem anderen Haus. Summe der Entfernungen für jedes einzelne Haus. Dann nehmen Sie einfach das Haus, das die niedrigste Summe.