Question

平面内一点到另两点距离之和最小的求法

Answer 1

怎样“求空间内一点到其它所有点的距离之和最小”？首先将这个问题形式化：
 公式代码：
\min f(x,y) = \min \sum_i \sqrt {(x - x_i)^2 + (y - y_i)^2}
这里是距离之和，而不是平方和。Kmeans聚类中用的评价标准是平方和，如果只有一个类中心，那么可以直接求偏导得到使得平方和最小的点就是中心。这里问题与平方和的解是不是一样的，比如三角形到三个顶点距离之和最短的点就是费马点。
这里可以用最优化方法中的“搜索”来求解，这一系列方法包括了梯度下降法、牛顿法和共轭梯度法等。在这里用梯度下降法是最简单的，通过这个例子我也明白了为什么实际运用中梯度下降法是应用最广的。相比梯度下降法，牛顿法需要求Hesse矩阵，还是相对麻 烦不少。梯度下降法搜索步骤就是每一步都向导数的逆方向将自变量前进一个步长（可变），在这里导数方向就是
 
公式代码：
abla f(x,y) =
\left[
\begin{array} {lcr}
\displaystyle \sum_i \frac{x - x_i}{\sqrt{(x - x_i)^2 + (y - y_i)^2pan >}} \\
\displaystyle \sum_i \frac{y - y_i}{\sqrt{(x - x_i)^2 + (y - y_i)^2}}
\end{array}
\right]
梯度下降法也有它使用起来让人比较为难的地方，那就是步长很难选取，课本上所给出的例子一般都是针对较简单表达式提出的可变步长计算。在本问题的求解中为简单起见，步长是取的定值。整个过程用Python3实现（起初想用R来做，但是R没法调试……归根结底还是功力不够）实现，结合了scipy和matplotlib两个包，结果看起来还是比较靠谱：

最后附上源代码：
Python 3语言: 高亮代码由发芽网提供
from scipy import *
import pylab
def f(p, pts):
return sum(sum((p - pts) ** 2, axis=1) ** 0.5)
def fd(p, pts):
dx = sum((p[0] - pts[:, 0]) / sum((p - pts) ** 2, axis=1) ** 0.5)
dy = sum((p[1] - pts[:, 1]) / sum((p - pts) ** 2, axis=1) ** 0.5)
s = (dx ** 2 + dy ** 2) ** 0.5
br> dx /= s
dy /= s
return array([dx, dy])

pts = rand(10, 2)
x = array([0, 0])
t = 0.1
xstep = x
for k in range(100):
y = f(x, pts)
xk = x - t * fd(x, pts)
yk = f(xk, pts)
if y - yk > 1e-8:
x = xk
y = yk
elif yk - y > 1e-8:
t *= 0.5
else:
break
xstep = vstack((xstep, x))
print(x, y)
pylab.plot(pts[:, 0], pts[:, 1], 'bo')
pylab.plot(xstep[:, 0], xstep[:, 1], 'ro')
pylab.plot(xstep[:, 0], xstep[:, 1], 'k-')
pylab.xlabel('iter = %d, Min = %.3f, p = (%.3f, %.3f), t = %f' % (k, y, x[0], x[1], t))
pylab.show()

Answer 2

怎样“求空间内一点到其它所有点的距离之和最小”？首先将这个问题形式化：
 公式代码：
\min f(x,y) = \min \sum_i \sqrt {(x - x_i)^2 + (y - y_i)^2}
这里是距离之和，而不是平方和。Kmeans聚类中用的评价标准是平方和，如果只有一个类中心，那么可以直接求偏导得到使得平方和最小的点就是中心。这里问题与平方和的解是不是一样的，比如三角形到三个顶点距离之和最短的点就是费马点。
这里可以用最优化方法中的“搜索”来求解，这一系列方法包括了梯度下降法、牛顿法和共轭梯度法等。在这里用梯度下降法是最简单的，通过这个例子我也明白了为什么实际运用中梯度下降法是应用最广的。相比梯度下降法，牛顿法需要求Hesse矩阵，还是相对麻 烦不少。梯度下降法搜索步骤就是每一步都向导数的逆方向将自变量前进一个步长（可变），在这里导数方向就是
 
公式代码：
abla f(x,y) =
\left[
\begin{array} {lcr}
\displaystyle \sum_i \frac{x - x_i}{\sqrt{(x - x_i)^2 + (y - y_i)^

Answer 3

一点到两点的距离的和最小，则此点必在两点连线上，这种点有无数个，距离之和最小就是两点连线的线段的长。希望能帮到你…

Answer 4

以河流为对称轴，作A点的对称点，记为A',连接A'与B，直线A'B与河流的交点，建中转站，到A点B点的距离相等，原理是两点之间线段最短