Das Problem besteht hier darin, eine Menge aller ganzzahligen Punkte zu finden, die eine minimale Summe über alle Manhattan-Distanzen von einer gegebenen Menge von Punkten ergibt!
Zum Beispiel:
hat eine gegebene Menge von Punkten {P1, P2, P3 ... Pn}
Grundlegendes Problem ist, einen Punkt zu finden, der X sagt, der minimale Summe über alle Entfernungen von Punkten {P1, P2, P3 ... Pn} haben würde.
d. | P1-X | + | P2-X | + .... + | Pn-X | = D, wobei D über alle X minimal ist.
Wenn Sie einen Schritt weiter gehen, kann es mehr als einen Wert von X geben, der obige Bedingung erfüllt. d. h. es können mehr als ein X möglich sein, die den gleichen Wert D ergeben würden. Also müssen wir alle solche X finden.
Ein grundlegender Ansatz, an den sich jeder wenden kann, ist es, den Median der Eingaben und dann die rohe Gewalt der Koordinaten zu finden, die in Dieser Beitrag
Aber das Problem bei einem solchen Ansatz ist: Wenn der Median zwei sehr weit voneinander entfernte Werte ergibt, dann werden wir alle auf Brute treffen, die niemals in einer bestimmten Zeit laufen.
Gibt es also einen anderen Ansatz, der das Ergebnis auch dann liefern würde, wenn die Punkte sehr weit auseinander liegen (wobei der Median einen Bereich in der Größenordnung von 10 ^ 9 ergibt).
Wenn der Median ein Intervall in der Größenordnung von 10 ^ 9 ergibt, ist jeder Punkt in diesem Intervall so gut wie jeder andere.
Je nachdem, was Sie später mit diesen Punkten machen wollen, können Sie entweder den Bereich zurückgeben oder Punkte in diesem Bereich aufzählen. Kein Weg in der Nähe ..
Offensichtlich in zwei Dimensionen erhalten Sie ein Bouding-Rechteck, in drei Dimensionen einen umschließenden Quader usw ..
Das Ergebnis ist immer ein kartesisches Produkt von Bereichen, die für jede Dimension erhalten wurden, sodass Sie als Ergebnis eine Liste dieser Bereiche zurückgeben können.
Sie können X und Y getrennt betrachten, da sie sich unabhängig voneinander zum Abstand addieren. Dies reduziert die Frage, ob bei n Punkten auf einer Linie ein Punkt mit der minimalen Summe der Abstände zu den anderen Punkten gefunden wird. Dies ist einfach: jeder Punkt zwischen den beiden Medianen (einschließlich) wird dies erfüllen.
Beweis : Wenn wir eine gerade Anzahl von Punkten haben, wird es zwei Mediane geben. Ein Punkt zwischen den beiden Medianen hat n / 2 Punkte nach links und n / 2 Punkte nach rechts und eine Gesamtsumme der Abstände zu diesen Punkten von S.
Wenn wir es um einen Punkt nach links bewegen, wird S um n / 2 (da wir uns von den rechtesten Punkten entfernen) und um n / 2 (da wir uns in Richtung der am weitesten links liegenden Punkte bewegen) , so bleibt S insgesamt gleich. Dies trifft zu, bis wir den am weitesten links liegenden Medianpunkt erreicht haben. Wenn wir uns vom linken mittleren Punkt nach links bewegen, haben wir nun (n / 2 + 1) Punkte nach rechts und (n / 2 - 1) Punkte nach links, so dass S um zwei nach oben geht. Weiter nach links wird S nur weiter erhöhen.
Mit der gleichen Logik haben auch alle Punkte rechts vom rechten Median einen höheren S-Wert.
Wenn wir eine ungerade Anzahl von Punkten haben, gibt es nur einen Median. Mit der gleichen Logik wie oben können wir zeigen, dass es den niedrigsten Wert von S hat.
Da in Manhattan Entfernung jede Komponente separat beiträgt, können Sie diese auch separat betrachten. Die optimale Antwort ist (Median (x), Median (y)). Sie müssen diesen Punkt nach ganzzahligen Lösungen durchsuchen.
HINWEIS : Ich habe Ihre Frage während der Antwort nicht richtig gelesen. Meine Antwort gilt immer noch, aber wahrscheinlich wussten Sie bereits von dieser Lösung.
Ja, ich denke auch, dass es für eine ungerade Anzahl von N Punkten auf einem Gitter nur einen einzigen Punkt geben wird (d. h. den MEDIAN), der sich bei allen anderen Punkten auf der minimalen Summe von Manhattan befindet.
Für den geraden Wert von N wird das Szenario ein wenig anders sein.
Nach mir, wenn zwei Sets X = {1,2} and Y= {3,4} ihr kartesisches Produkt immer 4 sind.
d. h. X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)} . Das habe ich bisher verstanden.
Wie bei der Anzahl der EVEN Werte nehmen wir immer "MIDDLE TWO" Werte als MEDIAN. Nimmt man 2 von X und 2 von Y, wird immer ein kartesisches Produkt von 4 Punkten zurückgegeben.
Korrigiere mich, wenn ich falsch liege.
Tags und Links algorithm optimization