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

Overview

Thuật toán Gradient Descent

main.rs
Open in Github Download
extern crate cgmath;

use cgmath::Vector2;
use cgmath::vec2;
use cgmath::prelude::*;

fn f(a: &[Vector2<f64>], x: &Vector2<f64>) -> f64 {
    a.iter().map(|u| (x - u).magnitude()).sum()
}
fn gradient(a: &[Vector2<f64>], x: &Vector2<f64>) -> Vector2<f64> {
    a.iter().map(|u| (x - u).normalize()).sum()
}

fn compute(a: &[Vector2<f64>]) -> f64 {
    let epsilon = 1e-7;
    let mut gamma = 0.01;
    let mut x1 = a.iter().sum();
    x1 /= a.len() as f64;
    let mut f1 = f(a, &x1);
    let mut g1 = gradient(a, &x1);
    loop {
        let x0 = x1;
        let f0 = f1;
        let g0 = g1;
        x1 -= g1 * gamma;
        f1 = f(a, &x1);
        g1 = gradient(a, &x1);
        gamma = (x1 - x0).dot(g1 - g0) / (g1 - g0).magnitude2();
        if f64::abs(f1 - f0) <= epsilon {
            break;
        }
    }
    f1
}

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let a = s.lines().skip(1).map(|s| {
        let mut a = s.split_whitespace();
        vec2(a.next().unwrap().parse::<f64>().unwrap(), a.next().unwrap().parse::<f64>().unwrap())
    }).collect::<Vec<_>>();
    println!("{}", compute(&a));
}
Comments