0

此问题是 ACM ICPC 坎普尔地区淘汰赛中提出的问题的子问题：

(Pa, Pb)给定由 2D 点和(Pc, Pd)分别界定的 2 条线段，找到最小化函数的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和中的至少一个为q0 或 1
  2. 相交的线段总是会导致p和q定位线段的交点（可以应用三角不等式来证明这一点）

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

4

1 回答 1

1

我认为您应该能够对fandp取偏导数q，将它们设置为 0，然后求解pand q。这将为您提供（本地）最低限度。如果最小值有0 <= p <= 1和0 <= q <= 1，你就完成了，否则检查四个端点（p=0,q=1，等等）。

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

于 2010-10-30T22:03:43.050 回答