So finden Sie Geometric Median heraus

Ich gelöst, etwas ähnliches für einen lokalen online-Richter einmal mit simulated annealing. Das war die offizielle Lösung als gut und das Programm hat AC.

Der einzige Unterschied war, dass der Punkt, den ich zu finden war nicht Teil der N Punkte gegeben.

Dies war mein C++ - code, und N könnte so groß wie 50000. Das Programm führt in 0.1s auf einem 2-GHz pentium 4.

//header files for IO functions and math
#include <cstdio>
#include <cmath>

//the maximul value n can take
const int maxn = 50001;

//given a point (x, y) on a grid, we can find its left/right/up/down neighbors
//by using these constants: (x + dx[0], y + dy[0]) = upper neighbor etc.
const int dx[] = { -1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

//controls the precision - this should give you an answer accurate to 3 decimals
const double eps = 0.001;

//input and output files
FILE *in = fopen("adapost2.in","r"), *out = fopen("adapost2.out","w");

//stores a point in 2d space
struct punct
{
    double x, y;
};

//how many points are in the input file
int n;

//stores the points in the input file
punct a[maxn];

//stores the answer to the question
double x, y;

//finds the sum of (euclidean) distances from each input point to (x, y)
double dist(double x, double y)
{
    double ret = 0;

    for ( int i = 1; i <= n; ++i )
    {
        double dx = a[i].x - x;
        double dy = a[i].y - y;

        ret += sqrt(dx*dx + dy*dy); //classical distance formula
    }

    return ret;
}

//reads the input
void read()
{
    fscanf(in, "%d", &n); //read n from the first 

    //read n points next, one on each line
    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%lf %lf", &a[i].x, &a[i].y), //reads a point
        x += a[i].x,
        y += a[i].y; //we add the x and y at first, because we will start by approximating the answer as the center of gravity

    //divide by the number of points (n) to get the center of gravity
    x /= n; 
    y /= n;
}

//implements the solving algorithm
void go()
{
    //start by finding the sum of distances to the center of gravity
    double d = dist(x, y);

    //our step value, chosen by experimentation
    double step = 100.0;

    //done is used to keep track of updates: if none of the neighbors of the current
    //point that are *step* steps away improve the solution, then *step* is too big
    //and we need to look closer to the current point, so we must half *step*.
    int done = 0;

    //while we still need a more precise answer
    while ( step > eps )
    {
        done = 0;
        for ( int i = 0; i < 4; ++i )
        {
            //check the neighbors in all 4 directions.
            double nx = (double)x + step*dx[i];
            double ny = (double)y + step*dy[i];

            //find the sum of distances to each neighbor
            double t = dist(nx, ny);

            //if a neighbor offers a better sum of distances
            if ( t < d )
            {
                update the current minimum
                d = t;
                x = nx;
                y = ny;

                //an improvement has been made, so
                //don't half step in the next iteration, because we might need
                //to jump the same amount again
                done = 1;
                break;
            }
        }

        //half the step size, because no update has been made, so we might have
        //jumped too much, and now we need to head back some.
        if ( !done )
            step /= 2;
    }
}

int main()
{
    read();
    go();

    //print the answer with 4 decimal points
    fprintf(out, "%.4lf %.4lf\n", x, y);

    return 0;
}

Dann denke ich, ist Es richtig zu wählen aus Ihrer Liste, die am nächsten an der (x, y) zurückgegeben, die von diesem Algorithmus.

Dieser Algorithmus nutzt, was diesen wikipedia-Absatz auf den geometrischen median sagt:

Es ist allerdings einfach zu berechnen, eine Annäherung an die
geometrische median mit einem iterativen Verfahren, in dem jeder Schritt
produziert eine genauere approximation. Verfahren dieser Art können sein
aus der Tatsache abgeleitet, dass die Summe der Entfernungen zu den sample-Punkte
ist eine konvexe Funktion, da der Abstand zu jedem sample-point ist
konvex und die Summe von konvexen Funktionen bleibt konvex. Daher
Verfahren, die Abnahme der Summe der Entfernungen bei jedem Schritt nicht bekommen
gefangen in einem lokalen optimum.

Einen gemeinsamen Ansatz dieser Art, genannt
Weiszfeld-Algorithmus nach der Arbeit von Endre Weiszfeld,[4] ist eine form
der iterativ neu gewichtete kleinste Quadrate. Dieser Algorithmus definiert einen Satz
GEWICHTE sind Umgekehrt proportional zu den Entfernungen von der
aktuelle Einschätzung zu den Proben, und erstellt eine neue Schätzung, dass ist
der gewichtete Mittelwert der Proben nach diesen gewichten. Dass
ist,

Den ersten Absatz oben erklärt, warum das funktioniert: weil die Funktion, die wir versuchen, zu optimieren, hat keine lokalen minima, so können Sie gierig suchen das minimum iterativ zu verbessern.

Betrachten Sie dies als eine Art binäre Suche. Erste, Sie annähernd das Ergebnis. Eine gute Näherung wird das Zentrum der Schwerkraft, die meinen code berechnet, wenn die Eingabe gelesen. Dann, sehen Sie, wenn die angrenzenden Punkte zu geben Ihnen eine bessere Lösung. In diesem Fall wird ein Punkt benachbart, wenn es eine Distanz von step Weg vom aktuellen Punkt. Wenn es besser ist, dann ist es gut, verwerfen Sie Ihren aktuellen Punkt, weil, wie ich schon sagte, dies wird nicht Sie in die Falle ein lokales minimum, da von der Natur der Funktion, die Sie versuchen zu minimieren.

Nachdem Sie die Hälfte der Schrittweite, wie in binäre Suche, und weiter, bis Sie haben, was Sie betrachten, um eine ausreichend gute Näherung (gesteuert durch die eps Konstante).

Die Komplexität des Algorithmus hängt also wie genau wollen Sie das Ergebnis zu sein.

InformationsquelleAutor der Antwort IVlad

Wie bereits erwähnt, die Art des Algorithmus zu verwenden, hängt von der Art und Weise Sie den Abstand Messen. Seit Ihrer Frage nicht angeben, diese Maßnahme, hier werden C-Implementierungen sowohl für die Manhattan Distanz und die Quadrierte euklidische Distanz. Verwenden dim = 2 für 2D-Punkte. Komplexität O(n log n).

Manhattan Distanz

double * geometric_median_with_manhattan(double **points, int N, int dim) {
    for (d = 0; d < dim; d++) {
        qsort(points, N, sizeof(double *), compare);
        double S = 0;
        for (int i = 0; i < N; i++) {
            double v = points[i][d];
            points[i][dim] += (2 * i - N) * v - 2 * S;
            S += v;
        }
    }
    return min(points, N, dim);
}

Kurze Erklärung: Wir können die Summe, die die Strecke pro dimension, 2 in deinem Fall. Sagen wir, wir haben N Punkte und die Werte in einer dimension sind v_0.., v_(N-1) und T = v_0 + .. + v_(N-1). Dann für jeden Wert v_i wir haben S_i = v_0 .. v_(i-1). Jetzt können wir express die Manhattan-Distanz für diesen Wert durch die Summe jener auf der linken Seite: i * v_i - S_i und auf der rechten Seite: T - S_i - (N - i) * v_idie Ergebnisse in (2 * i - N) * v_i - 2 * S_i + T. Hinzufügen T alle Elemente, die nicht die Reihenfolge ändern, also lassen wir das aus. Und S_i berechnet werden kann on-the-fly.

Hier ist der rest von dem code, macht es zu einem wirklichen C-Programm:

#include <stdio.h>
#include <stdlib.h>

int d = 0;
int compare(const void *a, const void *b) {
    return (*(double **)a)[d] - (*(double **)b)[d];
}

double * min(double **points, int N, int dim) {
    double *min = points[0];
    for (int i = 0; i < N; i++) {
        if (min[dim] > points[i][dim]) {
            min = points[i];
        }
    }
    return min;
}

int main(int argc, const char * argv[])
{
    //example 2D coordinates with an additional 0 value
    double a[][3] = {{1.0, 1.0, 0.0}, {3.0, 1.0, 0.0}, {3.0, 2.0, 0.0}, {0.0, 5.0, 0.0}};
    double *b[] = {a[0], a[1], a[2], a[3]};
    double *min = geometric_median_with_manhattan(b, 4, 2);
    printf("geometric median at {%.1f, %.1f}\n", min[0], min[1]);
    return 0;
}

Quadrierte euklidische Distanz

double * geometric_median_with_square(double **points, int N, int dim) {
    for (d = 0; d < dim; d++) {
        qsort(points, N, sizeof(double *), compare);
        double T = 0;
        for (int i = 0; i < N; i++) {
            T += points[i][d];
        }
        for (int i = 0; i < N; i++) {
            double v = points[i][d];
            points[i][dim] += v * (N * v - 2 * T);
        }
    }
    return min(points, N, dim);
}

Kürzere Erklärung: so Ziemlich den gleichen Ansatz wie die Vorherige, aber mit einem etwas komplizierten Herleitung. Sagen TT = v_0^2 + .. + v_(N-1)^2 bekommen wir TT + N * v_i^2 - 2 * v_i^2 * T. Wieder TT ist Hinzugefügt, um alle, so kann es weggelassen werden. Weitere Informationen auf Anfrage.

InformationsquelleAutor der Antwort leo

Schritt 1: Sortieren Sie die Punkte-Sammlung von x-dimension (nlogn)

Schritt 2: Berechnen Sie den x-Abstand zwischen jedem Punkt und alle Punkte LINKS:

xLDist[0] := 0
for i := 1 to n - 1
       xLDist[i] := xLDist[i-1] + ( ( p[i].x - p[i-1].x ) * i)

Schritt 3: Berechnen Sie den x-Abstand zwischen jedem Punkt und alle Punkte RECHTS:

xRDist[n - 1] := 0
for i := n - 2 to 0
       xRDist[i] := xRDist[i+1] + ( ( p[i+1].x - p[i].x ) * i)  

Schritt 4: Summe beide bis Sie bekommen den gesamten x-Entfernung von jedem Punkt zu den anderen N-1 Punkte

for i := 0 to n - 1
       p[i].xDist = xLDist[i] + xRDist[i]

Wiederholen Sie Schritt 1,2,3,4 mit der y-dimension zu bekommen p[i].yDist

Den Punkt mit der kleinsten Summe der xDist und yDist ist die Antwort

Gesamt-Komplexität O(nlogn)

Antwort in C++

Weitere Erklärung:

Die Idee ist die Wiederverwendung der bereits berechnete Gesamt-Distanz von vorhergehenden Punkt.

Angenommen, wir haben 3-Punkt-ABCD sortiert, sehen wir, dass die gesamte linke Abstand D zu den anderen, bevor es sind:

AD + BD + CD = (AC + CD) + (BC + CD) + CD = AC + BC + 3CD

In die (AC + BC) ist die Summe linken Abstand von C zu den anderen, bevor er, nutzten wir diese und müssen nur berechnen ldist(C) + 3CD

InformationsquelleAutor der Antwort rocketspacer