algorithm - 最小皮带，已知距离

Question

让我们假设我们有 2 条曲线，曲线 P 和曲线 Q。曲线 P 由点 p1 ,p2 ...pn 组成，曲线 Q 由点 q1,q2...qm 组成。一个人从 p1 开始到 pn 结束，在访问了所有点 p1,p2,..pn 之后。一条狗从 q1 开始到 qm 结束，在访问了所有 q1,q2...qm 之后。

附加限制:点必须连续访问。举个例子，如果人在p3，他可以在p3等到狗移动，他可以移动到p4，但他永远不能回去到 p2 。这同样适用于狗。

我们将 2 个点的距离定义为 d(pi,qj) 。我们假设 d(pi,qj) 的计算复杂度为 O(1)。所有距离 d(pi,qj) 都是已知的。

我们的任务是找到人和狗向 pn 和 qm 移动时发生的最小可能最大距离(最小牵引绳)d。

举个例子，如果 d(p1,q1) =1 , d(p1,q2)=2 , d(p1,q3)=3 ,d(q2,p1)=2.5 ,d(p2,q2 )=2.2 和 d(p2,q3)=1.8 ，则最小最大距离为 2 。

第 1 步:人和狗在 p1 和 q1 处。当前最大距离为 1。

第 2 步:人留在 p1，狗移动到 q2。当前最大距离为 2。

第3步:人和狗分别同时移动到p2和q3，最大距离保持2。

哪个算法最适合这个任务？它看起来像一个 frechet 距离问题......

Answer 1

我建议使用动态规划。每个步骤最多有三个可能的先前位置。设 f(i,j) 是从 (p1,q1) 到 (pi,pj) 的最大最小牵引距离。

然后:

f(i,j) = max( d(pi,qj), min(f(i-1,j), f(i,j-1), f(i-1,j-1)) )

您可以考虑构建一个矩阵来进行自下而上的计算(实际上是从左上角发出的三角形)，或者另一种选择可能是内存递归函数。可以在O(m*n) 时间内构造矩阵，而实际上只需要两行的空间。以您的例子为例，我们有:

d(p1,q1) =1 , d(p1,q2)=2 , d(p1,q3)=3 ,d(q2,p1)=2.5 ,d(p2,q2)=2.2 and d(p2,q3)=1.8

f(2,3) = max(1.8, min(f(1,3),f(2,2),f(1,2)))

显然 f(1,2) 将是最小评估中的最低值，导致 2 作为解决方案。

dp 构造的顺序看起来像这样，因为 f(i-1,j-1) 是 f(i- 1,j) 和 f(i,j-1) 但是 f(i,j) 需要这三个:

            1,1
         2,1   1,2
      3,1   2,2   1,3
   4,1   3,2   2,3   1,4
5,1   4,2   3,3   2,4   1,5

显然有一些关于计算更有效解决方案的已发表作品。例如:Agarwal et al. Computing the discrete Fréchet distance in subquadratic time

这里有一篇文章对上述 dp 算法进行了正式处理:Eiter & Mannila. Computing Discrete Frechet Distance