欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeeCode 1515 模拟退火

程序员文章站 2022-05-11 23:17:35
...
题意

传送门 LeeCode 1515. 服务中心的最佳位置

题解

二维区域上求到所有客户的欧几里得距离的总和最小位置的服务中心的位置,可以使用模拟退火法求解。在客户区域随机初始化较多的点,那么模拟退火时可以简单地当答案更优时进行转移,而不用依概率转移。二维区域转移的方法是将下一步转移的半径看作一般模拟退火时的温度,固定半径下多次随机地选取转移的角度。

class Solution
{
#define maxn 50
#define maxl 100
public:
    struct P
    {
        double x, y, d;
    } ct[maxn], sv[maxn];
    int nc, ns;
    double minx = maxl, maxx = 0, miny = maxl, maxy = 0;
    double R, eps = 1e-5, delta = 0.75;
    
    double dis(double x, double y)
    {
        double s = 0;
        for (int i = 0; i < nc; ++i)
        {
            double dx = x - ct[i].x, dy = y - ct[i].y;
            s += sqrt(dx * dx + dy * dy);
        }
        return s;
    }
    bool judge(double x, double y)
    {
        return minx <= x && x <= maxx && miny <= y && y <= maxy;
    }
    double getMinDistSum(vector<vector<int>> &positions)
    {
        ns = nc = positions.size();
        for (int i = 0; i < nc; ++i)
        {
            double x = positions[i][0], y = positions[i][1];
            ct[i] = P{x, y, 0};
            minx = min(minx, x), maxx = max(maxx, x);
            miny = min(miny, y), maxy = max(maxy, y);
        }
        double _x = maxx - minx, _y = maxy - miny;
        for (int i = 0; i < ns; ++i)
        {
            sv[i].x = minx + (fabs(_x) < eps ? 0 : rand() % (int)_x);
            sv[i].y = miny + (fabs(_y) < eps ? 0 : rand() % (int)_y);
            sv[i].d = dis(sv[i].x, sv[i].y);
        }
        double R = sqrt(_x * _x + _y * _y);
        while (R > eps)
        {
            for (int i = 0; i < ns; ++i)
                for (int j = 0; j < ns; ++j)
                {
                    double a = rand() % 360 / 180.0 * M_PI;
                    double nx = sv[i].x + R * cos(a), ny = sv[i].y + R * sin(a);
                    if (!judge(nx, ny))
                        continue;
                    double nd = dis(nx, ny);
                    if (nd < sv[i].d)
                        sv[i].x = nx, sv[i].y = ny, sv[i].d = nd;
                }
            R *= delta;
        }
        double res = maxl * maxl;
        for (int i = 0; i < ns; ++i)
            res = min(res, sv[i].d);
        return res;
    }
};
相关标签: SA