前言
自己YY的,感觉挺好理解的
直奔主题,证明三者中任意两者相加都能构成单峰函数
min{PAM+qMN+mNM}
当 M 给定时, 我们来看 qMN+mNM 存在怎么样的性质。
我们坐标表示:
M:(E,F)
N:(A,B)
D:(C,D)
根据欧几里得距离公式我们可以写出一个优美的二元二次方程,显然从方程中看不出单峰的性质,因为它是一个园。
我们只需要保证点与点之间的距离不变,那么最小值也就不会变。这启发我们更新坐标。
我们的目的是证明出qMN+mNM是一个单峰函数,那么我将坐标变化成理想状态,并保证点点之间距离不变,那么答案不会影响。因此我们希望将 N 和 D 的x 或者 y 相同。所以旋转坐标系,如下图

那么他们的坐标就变成:
M:(E,F)
N:(A,D)
D:(C,D)
可以发现 N,D 纵坐标 y 相同,设 f(M) 为当 M 点坐标 为(E,F) 时的最小值,我们将柿子列出来
f(M)=q(E−A)2+(F−D)2+m(A−C)2+(D−D)2
E,F,D 是常量,那么柿子只有 A 一个变量,那么就变成一个抛物线问题,显然是一个单峰函数。
我们再考虑 M 是变量的时候。
同理,E,F 成为了变量,需要证明的是 f(M)+PAM 是单峰函数。
f(M)已经知道了,只求 PAM就好了, 即存在 E,F 两个变量,我们依旧用坐标变换,将 F 消去,原理和上面相同。这样只剩下 E 一个变量,又是一个单峰函数抛物线。
所以才有了三分套三分的做法。因为例外都是单峰函数