algorithm - 优化线段上的 2 参数距离函数(ACM ICPC Regionals Elim。)

Question

这个问题是 ACM ICPC 坎普尔地区淘汰赛中提出的问题的子问题:

给定由二维点界定的 2 条线段 (Pa, Pb)和 (Pc, Pd)分别找到p和 q (在 [0,1] 范围内)最小化函数

f(p, q) = D(Px, Pa) + D(Py, Pd) + k D(Px, Py) where 
                                2 <= k <= 5, 
                                Px = p Pa + (1-p) Pb, 
                                Py = q Pc + (1-q) Pd and 
 D(x, y) is the euclidean distance between points x and y

(实际上，Px 和 Py 是线段上的点，该函数编码了从 Pa 到 Pd 通过连接链路的成本，其成本是欧氏距离的 k 倍)

关于这个函数的一些观察:

1. 平行线段总是会导致至少一个 p和 q为 0 或 1
2. 相交线段总是会导致 p和 q定位线段的交点(三角不等式可以证明)

问题:在线条倾斜且可能分离的一般情况下，我们如何最小化此功能？

Answer 1

我认为你应该能够对 f 求偏导数关于 p和 q , 将它们设置为 0, 并求解 p和 q .那会给你一个(本地)最低限度。如果最小有0 <= p <= 1和 0 <= q <= 1 ，你就完成了，否则检查四个端点( p=0,q=1 ，依此类推)。

我不确定这会处理所有退化条件，但它应该是一个好的开始。