数优化

爬山法

字数统计: 1.2k字   |   阅读时长: 4分
, ,

摘要: 介绍爬山法的原理并解决力扣 1515

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，在文章 梯度下降 中我们学习了梯度下降并解决了力扣 1515，本文介绍另一个在目标函数上找最优解的算法：爬山法。简要介绍爬山法的思想之后，解决力扣 1515，题解的代码可以作为爬山法的代码模板。

$1 爬山法

爬山法是一种贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

优点是实现简单，在各种空间中的搜索问题都可以快速实现。

缺点是很可能会陷入局部最优。

假设 C 点为当前解，爬山法搜索到 A 点这个局部最优解就会停止搜索而不会继续搜索到 B，因为在 A 点无论向那个方向小幅度移动都不能得到更优的解。

爬山法

$2 题目

一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。

给你一个数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个客户在二维地图上的位置，返回到所有客户的 欧几里得距离的最小总和 。

换句话说，请你为服务中心选址，该位置的坐标 [xcentre, ycentre] 需要使下面的公式取到最小值：

与真实值误差在 1e-5 之内的答案将被视作正确答案。

示例 1：
输入：positions = [[0,1],[1,0],[1,2],[2,1]]
输出：4.00000
解释：如图所示，你可以选 [xcentre, ycentre] = [1, 1] 作为新中心的位置，这样一来到每个客户的距离就都是 1，所有距离之和为 4 ，这也是可以找到的最小值。

示例 2：
输入：positions = [[1,1],[3,3]]
输出：2.82843
解释：欧几里得距离可能的最小总和为 sqrt(2) + sqrt(2) = 2.82843

提示：

1
2
3
1 <= positions.length <= 50
positions[i].length == 2
0 <= xi, yi <= 100

算法：爬山法

首先写出目标函数如下：

当凸函数很难求导的时候，可以考虑用爬山法找最值。

对于二元函数，梯度可以分为 x 和 y 两个方向：$\nabla = (\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y})$

当前点在 (x, y)，下一步考虑四个方向，每个方向向前移动一点，移动的长度记为 step。

1
2
dx = {0, 1, 0, -1}
dy = {1, 0, -1, 0}

这样 (x + step * dx + y + step * dy) 就是一个候选点，如果该点的函数值更小，就走到这个点，这样就可以像梯度下降一样得到本轮迭代的下一个点。

如果候选点的函数值没有更小，就考察下一个方向，如果四个方向都没有找到函数值更小的点，就衰减步长。

当步长小于 EPS 时，搜索结束。

代码 (C++)

使用了向量的代码模板，参考文章 向量的实现。

参数设置：

  • 初始点 : 所有带你的算术平均值
  • 步长：step = 1
  • 步长衰减 : $\eta = 5e-1$
  • EPS : 1e-9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct Function
{
    // 二元函数
    vector<Vector2> *points;
    Function(vector<Vector2>* p):points(p){}
    double operator()(Vector2& p0) const
    {
        double ans = 0;
        for(Vector2 p: *points)
            ans += (p0 - p).norm();
        return ans;
    }
};


class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        int n = positions.size();
        Vector2 vec; // 初始值
        vector<Vector2> data; // 训练数据
        for(vector<int>& p: positions)
        {
            vec.x += p[0];
            vec.y += p[1];
            data.emplace_back(p[0], p[1]);
        }
        Function f(&data);
        vec = vec * (1 / (double)n);
        double step = 1.0; // 步长
        double decay = 5e-1; // 步长衰减
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        Vector2 nxt_vec;
        while(step > EPS)
        {
            bool flag = false;
            for(int d = 0; d < 4; ++d)
            {
                nxt_vec.x = vec.x + step * dx[d];
                nxt_vec.y = vec.y + step * dy[d];
                if(f(nxt_vec) < f(vec))
                {
                    vec = nxt_vec;
                    flag = true;
                    break;
                }
            }
            if(!flag)
                step *= (1 - decay);
        }
        return f(vec);
    }
};
Share