最小皮帶，已知距離

讓我們假設我們有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感謝您的評論（和暫定投票），我添加了「動態編程」這個詞，這是否符合你的想法？ –

最小皮帶，已知距離

回答

相關問題