Skip to content

费马点怎么用代码找出来:退火、构造与误差 ​

一道 380 年前的题,今天还得靠搜索 ​

1643 年费马写信问托里拆利:平面上有三个点,找一点使得到这三点的距离和最小。这个点后来叫费马点。

上一篇讲了它为什么一定在三个角都是 120° 的位置上,那是纯几何的活。这一篇换个角度:假设你不知道 120° 这件事,只有一台计算机和三行坐标,怎么把它找出来。

这个问题在优化里有意思的地方在于,它是一个凸问题但不可导。距离和是凸函数,所以局部最小就是全局最小,这点很友好。但目标函数在三个顶点处有奇点:如果真的走到顶点上,梯度根本不存在。梯度下降碰到这种地形要专门处理,而随机搜索类方法天然不关心导数存不存在。

三种解法,三种性格 ​

摆在面前的路有三条:

方法需要的先验精确性代价
模拟退火什么都不需要近似(约 1e-5 相对误差)2 万次函数求值
梯度零点法知道"三向单位向量和为零"机器精度一次牛顿迭代
托里拆利构造知道"外作等边三角形"精确(尺规可达)常数次运算

三者需要的先验知识依次增加,精度也依次提高。下面逐个跑一遍,看它们在同一个三角形上给出什么。

先把目标函数写清楚 ​

三种方法共用一个目标:从点 P 到三个顶点的欧氏距离之和。

f(P)=|PA→|+|PB→|+|PC→|=∑i=13(x−xi)2+(y−yi)2

代码里就是三行:

python
def dist_sum(p, A, B, C):
    return np.linalg.norm(p - A) + np.linalg.norm(p - B) + np.linalg.norm(p - C)

这个函数有两个性质,决定了后面所有方法的选型。

它是凸的。 欧氏范数是凸函数,凸函数的和仍然凸。凸性意味着不存在"假的谷底",任何局部最小都是全局最小,所以方法之间的差别只在精度和速度,不在能不能找到对的答案。

它在三个顶点处不可导。 距离函数在原点附近的样子像个圆锥尖,x2+y2 在 (0,0) 处没有导数。三角形平移到哪个顶点,那个顶点就是目标函数的一个尖点。梯度类方法走到尖点附近会因为梯度突然变成无穷大而失效,必须专门打补丁。

这两条合起来解释了为什么这个问题适合拿来比较方法:它简单到能验证,又不平凡到能暴露方法的差异。

模拟退火:什么都不假设 ​

思路很朴素:从重心出发,每一步在当前点附近随机跳一下,新位置更好就接受,更差也按一定概率接受。接受概率随温度衰减,温度从高到低意味着从"到处乱走"过渡到"只往好里走"。

python
def simulated_annealing(A, B, C, n_iter=20000, T0=5.0, T1=1e-4):
    cur = (A + B + C) / 3
    cur_s = dist_sum(cur, A, B, C)
    best, best_s = cur.copy(), cur_s
    for t in np.geomspace(T0, T1, n_iter):
        cand = cur + rng.standard_normal(2) * t * 0.35
        cand_s = dist_sum(cand, A, B, C)
        d = cand_s - cur_s
        if d < 0 or rng.random() < np.exp(-d / t):
            cur, cur_s = cand, cand_s
            if cur_s < best_s:
                best, best_s = cur.copy(), cur_s
    return best, best_s

步长取 t * 0.35,高温时一步能跨好几个单位,低温时步长缩到 1e-4 量级做精修。np.geomspace 让温度按几何级数下降,前段走过大半路程,后段慢慢磨。

拿三个三角形试一下,和精确解对照(完整输出见下方代码块,表格只列关键值):

三角形(最大内角)退火相对误差
接近等边(60.8°)0.0010%
细长锐角(109.9°)0.0049%
钝角(122.2°)0.0039%

解析解与退火解的距离和:

三角形        解析解        退火解      相对误差
接近等边    17.261413   17.261582    0.0010%
细长锐角    36.494465   36.496257    0.0049%
钝角        10.641698   10.642115    0.0039%

三行误差都在万分之一到万分之五量级。第一条是最容易的情形,误差最小;剩下两条地形更扁,同等迭代次数下精度差一点,但都还在可接受范围。

迭代多少次才够 ​

退火收敛曲线

这是个实际问题。跑 500 次和跑 2 万次,差多少?

   迭代       平均距离和      平均误差      最差误差
    500      17.262047     0.0037%     0.0037%
   2000      17.261874     0.0027%     0.0037%
   5000      17.261849     0.0025%     0.0037%
  20000      17.261429     0.0001%     0.0002%

从 500 次到 5000 次,平均误差只从 0.0037% 降到 0.0025%,几乎没动。到 2 万次才真正往下走一档。

这说明退火在前几百次迭代里就找到了正确答案附近,后面两万次基本是在小数点后面磨。困难的地方在磨准,找到它并不难。

如果只要两位小数,500 次足够。如果要和解析解对到 1e-5,得两万次以上。这中间的性价比断崖,是调参时最该知道的事。

梯度零点法:一步到位 ​

费马点满足一个漂亮的条件:从该点指向三个顶点的三个单位向量,向量和为零。

A→−P→|A→−P→|+B→−P→|B→−P→|+C→−P→|C→−P→|=0→

写成能被数值求解器吃掉的形式,就是从重心出发找这个方程组的零点:

python
def fermat_exact(A, B, C):
    if angles(A, B, C).max() > 120 - 1e-9:
        return [A, B, C][int(np.argmax(angles(A, B, C)))]
    def eqs(p):
        v = [(V - p) / np.linalg.norm(V - p) for V in (A, B, C)]
        return v[0] + v[1] + v[2]
    return fsolve(eqs, (A + B + C) / 3, xtol=1e-13)

这个方法的精度是机器精度级的。用它反算三条夹角:

接近等边  三条夹角 120.00000000°  最大偏差 1.42e-14°
细长锐角  三条夹角 120.00000000°  最大偏差 4.26e-14°

偏差在 1e-14 度。这不是"接近 120°",是在双精度浮点数的极限内等于 120°。

注意第一行那个分支:当某个内角超过 120°,方程组的解会跑向那个顶点,此时费马点退化成顶点本身。这个判断不能省,否则求解器会在奇点附近挣扎。

钝角退化:8000 个三角形验证 ​

上面说"内角超过 120°,最优解退化成顶点",这句话值得单独验。

随机撒 2 万个三角形,筛出其中最大内角超过 120° 的 8100 个,对每一个用 200×200 的网格暴力搜索,看能不能找到比"最大角顶点"更优的位置:

随机三角形 20000 个 / 钝角 8100 个
网格搜索找到比"最大角顶点"更优的点: 0 个
最大反例: 0.000e+00

8100 个样本,零反例。

这个验证方式很笨,但它没有依赖任何理论推导,纯粹是"遍历一遍看有没有"。如果定理错了,这里就会冒出反例。

重心差多少 ​

重心与费马点差距

费马点经常被和重心搞混,两者在最简单的三角形里长得差不多。实际差多少:

三角形                费马点        重心         差      差距%
接近等边          17.261413   17.262047   0.000635   0.004%
细长锐角          36.494465   37.837891   1.343425   3.550%
钝角(>120°)       10.641698   12.818454   2.176757  16.981%

接近等边时,两者只差 0.004%,肉眼看不出来。三角形越扁,差距越大:细长锐角到 3.55%,钝角到 16.98%。

这条结论有实用含义:如果你的三角形接近等边,用重心近似费马点几乎没损失;一旦变扁,这个近似就不能用了。

什么时候用哪个 ​

场景推荐理由
只想快速拿个近似值模拟退火 500 次误差千分之几,几十毫秒
要 1e-6 以内的精度梯度零点法一次牛顿迭代到位
几何作图画在纸上托里拆利构造尺规可达,不需要计算
三角形可能钝角先判内角否则解会跑向顶点

一篇 380 年前的问题,三种解法从"什么都不假设"到"知道定理长什么样",精度差了好几个数量级。先验知识换精度,这个交换在优化里到处都是。

完整代码和验证脚本在下面的仓库里,两个随机种子都写死了,跑出来和上面一模一样。

关注公众号:QIAN数据