最小皮带，已知距离

让我们假设我们有2条曲线，曲线P和曲线Q.曲线P由点p1，p2 ... pn组成，曲线Q由点q1，q2 ... qm组成。一个男人在p1，p2，... pn之后，从p1开始，到pn结束。一只狗在q1，q2 ... qm之后，从q1开始，在qm结束。举例来说，如果该男子在P3，他可以在P3等待，直到狗移动，他可以移动到P4，但他永远不能去回到p2。这同样适用于狗。最小皮带，已知距离

我们将2点的距离定义为d（pi，qj）。我们假设在O（1）处计算d（pi，qj）。所有距离d（pi，qj）是已知的。

我们的任务是找到人和狗之间发生的最小可能的最大距离（最小牵引）d，同时它们朝向pn和qm。例如，如果d（p1，q1）= 1，d（p1，q2）= 2，d（p1，q3）= 3，d（q2，p1）= 2.5，d（p2，q2） q2）= 2.2和d（p2，q3）= 1.8，则最小最大距离为2。

步骤1：男人和狗在p1和q1。当前最大距离为1.

第2步：男子仍然在p1，狗移动到q2。目前的最大距离为2

第3步：连人带狗simultaneuosly移动到P2和Q3 respectively.Maximum距离保持2

这是该任务的最合适的算法它看起来像一个弗雷谢距离？问题...

来源

2016-11-19 user3697730

“我们的任务是找到人与狗之间occures最小可能的最大距离（最小皮带）d ，而他们走向pn和qm。“不清楚：是否意味着”使任何双向步行成为可能“或”至少有一次双向步行“？ –

我会建议动态编程。每一步最多有三个可能的位置。假设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,j)的f(i-1,j)和f(i,j-1)，但所有三个父：

  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

来源

2016-11-20 02:20:50

假设以下步骤序列 - 所有者（p位置）始终停留在p1中，狗q POS）向前走3倍。 - 。后两个步骤达到P3为2的皮带，我不得不打电话的地方动物保护机构，你就会窒息可怜的狗 –

姑且+1，但到目前为止，还没有真正回答*算法*的问题，你刚刚给一个乘递推公式。你需要谈谈“动态规划”或“记忆化”或类似。 – ruakh

@ruakh感谢您的评论（和暂定投票），我添加了“动态编程”这个词，这是否符合你的想法？ –

最小皮带，已知距离

回答

相关问题