爬山法

  |  

摘要: 介绍爬山法的原理并解决力扣 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