let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

Thuật toán Gradient Descent

main.cpp
Open in Github Download
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;

struct vec {
    double x, y;
    vec& operator+=(vec v) {
        this->x += v.x, this->y += v.y;
        return *this;
    }
    vec& operator-=(vec v) {
        this->x -= v.x, this->y -= v.y;
        return *this;
    }
    vec& operator*=(double k) {
        this->x *= k, this->y *= k;
        return *this;
    }
    vec& operator/=(double k) {
        this->x /= k, this->y /= k;
        return *this;
    }
};
vec operator+(vec u, vec v) { return u += v; }
vec operator-(vec u, vec v) { return u -= v; }
double operator*(vec u, vec v) { return u.x*v.x + u.y*v.y; }
vec operator*(vec v, double u) { return v *= u; }
vec operator/(vec v, double u) { return v /= u; }
double magnitude(vec u) { return sqrt(u.x*u.x + u.y*u.y); }
double sqr(double d) { return d*d; }

vec gradient(const vector<vec> &a, vec x) {
    vec tmp, res = {0, 0};
    for (auto &u: a) {
        tmp = x - u;
        res += tmp / magnitude(tmp);
    }
    return res;
}

double f(const vector<vec> &a, vec x) {
    double res = 0;
    for (auto& u: a) res += magnitude(x - u);
    return res;
}

double compute(const vector<vec> &a) {
    const double epsilon = 1e-7;
    double gamma = 0.01;
    vec x0, x1 = {0, 0};
    for (auto& u: a) x1 += u;
    x1 /= (double) a.size();
    double f0, f1 = f(a, x1);
    vec g0, g1 = gradient(a, x1);
    do {
        x0 = x1, x1 -= g1 * gamma;
        f0 = f1, f1 = f(a, x1);
        g0 = g1, g1 = gradient(a, x1);
        gamma = (x1 - x0) * (g1 - g0) / sqr(magnitude(g1 - g0));
    } while (abs(f1 - f0) > epsilon);
    return f1;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n; cin >> n;
    vector<vec> a(n);
    for (auto& u: a) cin >> u.x >> u.y;
    cout << compute(a) << "\n";
    return 0;
}
Comments