minimale Leine, bekannte Abstände

Question

Nehmen wir an, wir haben 2 Kurven, Kurve P und Kurve Q. Die Kurve P besteht aus den Punkten p1, p2 ... pn und die Kurve Q besteht aus den Punkten q1, q2 ... qm. Ein Mann beginnt bei p1 und endet bei pn, nachdem er alle Punkte p1, p2, .. pn besucht hat. Ein Hund beginnt bei q1 und endet bei qm, nachdem er alle q1, q2 ... qm besucht hat.

Zusätzliche Einschränkung: Punkte müssen nacheinander besucht werden. Um ein Beispiel zu geben, wenn der Mann auf p3 ist, kann er auf p3 warten, bis der Hund einen Zug macht, er kann auf p4 gehen, aber er kann nie gehen zurück zu p2. Gleiches gilt für den Hund.

Wir definieren den Abstand von 2 Punkten als d (pi, qj). Wir nehmen an, dass d (pi, qj) bei O (1) berechnet wird. Alle Abstände d (pi, qj) sind bekannt.

Unsere Aufgabe ist es, die minimal mögliche maximale Distanz (minimale Leine) d zwischen dem Mann und dem Hund zu finden, während sie sich in Richtung pn und qm bewegen.

Um ein Beispiel zu geben, wenn d (p1, q1) = 1, d (p1, q2) = 2, d (p1, q3) = 3, d (q2, p1) = 2,5, d (p2, q2) = 2,2 und d (p2, q3) = 1,8, dann ist der minimale maximale Abstand 2.

schritt 1: mann und hund sind bei p1 und q1. Der aktuelle maximale Abstand ist 1.

Schritt 2: Mann bleibt auf p1, Hund bewegt sich nach q2. Aktuelle maximale Entfernung ist 2.

Schritt 3: Mensch und Hund simultaneuosly auf p2 und q3 respectively.Maximum Abstand 2.

bleibt bewegen, die die am besten geeigneten Algorithmus für diese Aufgabe ist es wie ein Frechet Abstand aussieht? Problem ...

Answer 1

Ich würde dynamische Programmierung vorschlagen. Es gibt höchstens drei mögliche vorherige Positionen für jeden Schritt. Lassen Sie f(i,j) die maximale minimale Leine Abstand von (p1,q1) bis (pi,pj) sein.

Dann:

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

Sie über den Aufbau einer Matrix denken konnte, einen Bottom-up-Berechnung (eigentlich ein Dreieck ausgehend von oben links) zu halten oder eine andere Alternative kann eine rekursive Funktion werden memoizing. Die Matrix kann in O(m*n) Zeit erstellt werden, und Platz wird eigentlich nur für zwei Zeilen benötigt. Um Ihr Beispiel zu nehmen, die wir haben:

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))) 

Klar f(1,2) wäre die niedrigste in der min Auswertung bis 2 als Lösung führt.

Der Auftrag für eine dp Konstruktion würde, da f(i-1,j-1) etwa so aussehen ist ein Elternteil von f(i-1,j) und f(i,j-1) aber alle drei für f(i,j) benötigt:

  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 

Anscheinend gibt es einige veröffentlichte Arbeit auf die Berechnung einer effizienteren Lösung. Zum Beispiel: Agarwal et al. Computing the discrete Fréchet distance in subquadratic time

Und hier ist ein Artikel, eine formale Behandlung des dp Algorithmus, der oben präsentiert: Eiter & Mannila. Computing Discrete Frechet Distance