梯度下降（easy）

学习资料https://www.cnblogs.com/qswg/p/9286337.html

先我用梯度下降的骚操作来解决一些有趣的问题。

费马点问题： 所谓费马点，是指搭配到给定的n个点的距离之和最小的那个点。

现在给你n个点，求这个n个点的费马点。（费马点可能不唯一，可能出现一条线段上的点都是费马点的情况，比如当只有两个点时）

这题的梯度如果按照公式求

，

偏导过程将比较复杂，因为偏导不连续。

但是如果按照梯度下降的定义，我们可以单独考虑每个点对于点θ处梯度的贡献（梯度分量）。

首先，我们应该尽可能地靠近每一个点的。故在只有一个点的时候，直接朝这个点走下降速度是最快的

所以对某个点X，X贡献的梯度分量的方向，应该是θ到X的反方向（梯度是代价函数上升的方向）。

而贡献梯度分量的模长应该是1，因为不论X里θ多远，往X前进dx，距离之和也只会下降dx.。所以对偏导的贡献永远是1。

接着合成所有梯度分量即可得到，点θ梯度为【θ到所有点的单位方向向量之和】取反（因为梯度是上升方向）。

所以下降方向为【所有点的单位方向向量之和】

即迭代公式为：

emmmmm  我们知道一维绝对值求导得到的是符号函数sign().  而对多维函数的来说，求导结果就是单位方向向量啦，而sign可以看一维单位方向向量，所以还是求导好

为保证的梯度下降的快速收敛，一般需要进行尺度归一化，以消除大尺度的维度收敛慢的问题。

接着为了能快速和正确的收敛，往往还要动态地选择学习因子α

一般有3种常用的策略(下面均是针对归一化的后梯度下降)：

（1）指数模型 α=C^t  其中C为常数且 0<c<1, t为迭代次数

（2）倒数模型α=C/t   其中C为常数且 0<c<1, t为迭代次数

（3）自适应模型：若代价函数最小值连续k次不变，令α=α/2，若代价函数的最小值连续m次减小，令α=2α

而对于迭代终点的选择，一般会先用固定次数迭代，先迭代个几百次看是否收敛，不收敛的话可能细节写错了，或者参数不合适。

看到明确收敛现象后，再采用各种提前判断是否收敛的方法，提前终止迭代，以提高计算效率。

比如看代价函数的增量，增量小于一定程度则认为收敛。

多组数据每组数据包含一个整数n.

接下n行，每行有两个整数 x,y代表点的坐标。

n<=100 ，0<=x,y<=10000

数据组数不超过10

对于每组数据输出一行，代表费马点到所有点的距离之和，保留两位小数

1
8 2
6
2 8
9 9
8 8
10 9
9 1
3 3
3
2 8
3 0
2 9
5
1 3
10 9
8 8
8 5
7 5

0.00
23.79
9.06
15.22

hint
样例的四个费马点分别为:
8.00 2.00

8.00 8.00

2.00 8.00

7.42 5.50