洛谷-P1337 [JSOI2004] 平衡点 题解

· · 题解

梯度下降法的题解！

Problem

给定平面上 n 个点 (x_1,y_1)\sim (x_n,y_n)。求一个点 (x,y) 使得

\sum_{i=1}^n w_i\sqrt{(x_i-x)^2+(y_i-y)^2}

最小。

Solution

我们使用梯度下降法。

目标函数显然就是：

J(x,y)=\sum_{i=1}^n w_i\sqrt{(x_i-x)^2+(y_i-y)^2}

每个距离函数是凸函数，因此加权和也是凸函数，梯度下降保证收敛到全局最小值。

求出偏导数：

\frac{\partial J}{\partial x}=\sum_{i=1}^n w_i \cdot\frac{x-x_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}},\quad \frac{\partial J}{\partial y}=\sum_{i=1}^n w_i \cdot\frac{y-y_i}{\sqrt{(x-x_i)^2+(y-y_i)^2}}

当分母为 0 时（即当前点与某给定点重合）不可导，不妨规定该项偏导为 0。

迭代更新：

x_{t+1}=x_t-\eta_t\frac{\partial J}{\partial x},\quad y_{t+1}=y_t-\eta_t\frac{\partial J}{\partial y}

学习率采用指数衰减调度：

\eta_{t+1}=r \cdot \eta_t \quad (0<r<1)

终止条件为 \eta<eps 或 \left\|\nabla J(x,y)\right\|<eps。

初始点取加权平均：

x_0=\frac{\sum w_ix_i}{\sum w_i},\quad y_0=\frac{\sum w_iy_i}{\sum w_i}

超参数：\eta_0=100,r=0.99,eps=10^{-6}

Code

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
constexpr int N=1005;
constexpr double LR=100.0,DECAY=0.99,EPS=1e-6;  // 超参数
double x[N],y[N],w[N];
int n;
pair<double,double> gradient(double curX,double curY){
    pair<double,double> grad={0.0,0.0};
    for(int i=0;i<n;++i){
        double dx=curX-x[i];
        double dy=curY-y[i];
        double dist=sqrt(dx*dx+dy*dy);
        if(dist<EPS) continue;  // 该处偏导数规定为0，避免数值爆炸
        grad.first+=w[i]*dx/dist;
        grad.second+=w[i]*dy/dist;
    }
    return grad;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    double curX=0.0,curY=0.0,sumW=0.0,lr=LR;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>x[i]>>y[i]>>w[i];
        curX+=x[i]*w[i],curY+=y[i]*w[i],sumW+=w[i];
    }
    curX/=sumW,curY/=sumW;
    while(lr>EPS){
        pair<double,double> grad=gradient(curX,curY);  // 计算梯度向量
        double gradLen=sqrt(grad.first*grad.first+grad.second*grad.second);
        if(gradLen<EPS) break;
        curX-=lr*grad.first;
        curY-=lr*grad.second;
        lr*=DECAY;
    }
    cout<<fixed<<setprecision(3)<<curX<<' '<<curY;
    return 0;
}

Update 2025.6.16：修改一处公式错误。