Algorithmus: Distanz-Transformation - ein schnellerer Algorithmus?

Question

Ich versuche das Entfernungstransformationsproblem zu lösen (mit Manhattans Entfernung). Grundsätzlich gibt Matrix mit 0 und 1 ist, Programm muss zuweisen Entfernungen von jeder Position am nächsten 1. Zum Beispiel für diese eine

0000 
0100 
0000 
0000 

Entfernung Transformationsmatrix ist

2123 
1012 
2123 
3234 

Mögliche Lösungen aus meinem Kopf :

langsamsten (langsamste, weil ich sie umzusetzen haben versucht - sie hinken auf sehr großen Matrizen):

1. Brute-Force - für jede 1, die das Programm liest, ändern Sie die Abstände entsprechend vom Anfang bis zum Ende.

2. Breite-zuerst Suche von Nullen - für jede 0, Programm sucht nach nächsten 1 von innen nach außen.

3. Wie 2, aber beginnend mit der 1-Marke jeden Abstand von innen nach außen.

4. Viel schneller (Lesen von Code anderen Leute)

   Breitensuche von 1en

   1. Assign all values in the distance matrix to -1 or very big value. 
   2. While reading matrix, put all positions of 1's into queue. 
   3. While queue is not empty 
       a. Dequeue position - let it be x 
       b. For each position around x (that has distance 1 from it) 
        if position is valid (does not exceed matrix dimensions) then 
         if distance is not initialized or is greater than (distance of x) + 1 then 
          I. distance = (distance of x) + 1 
          II. enqueue position into queue 
   

Ich wollte fragen, ob es schnelle Lösung für dieses Problem ist. Ich habe versucht, Algorithmen für die Entfernung zu suchen, aber die meisten von ihnen beschäftigen sich mit euklidischen Entfernungen.

Vielen Dank im Voraus.

Answer 1

Die Breite erste Suche würde Θ(n*m) Operationen ausführen, wobei n und m die Breite und Höhe Ihrer Matrix sind.

Sie müssen Θ(n*m) Zahlen ausgeben, so dass Sie aus theoretischer Sicht nicht schneller als das bekommen können.

Ich nehme an, Sie sind nicht daran interessiert, in Diskussionen mit Cache und solchen Optimierungen zu gehen.

---

Beachten Sie, dass diese Lösung in interessanteren Fällen funktioniert. Zum Beispiel vorstellen, die gleiche Frage, aber es könnte anders „Quellen“ sein:

00000 
01000 
00000 
00000 
00010 

Mit BFS, erhalten Sie die folgende Entfernung zu engster Quelle in der gleichen Zeitkomplexität:

21234 
1
21223 
32212 
1 

Mit einer einzigen Quelle gibt es jedoch eine andere Lösung, könnte eine etwas bessere Leistung in der Praxis haben (obwohl die Komplexität immer noch die gleiche ist).

Bevor, beobachten wir die folgende Eigenschaft.

Property: Wenn die Quelle auf (a, b), dann ein Punkt (x, y) die folgende manhattan Entfernung:

d(x, y) = abs(x - a) + abs(y - b) 

Dies sollte ganz einfach sein, zu beweisen. Also ein anderer Algorithmus wäre:

for r in rows 
    for c in cols 
    d(r, c) = abc(r - a) + abs(c - b) 

was sehr kurz und einfach ist.

---

Wenn Sie nicht schreiben und testen, gibt es keine einfache Möglichkeit, die beiden Algorithmen zu vergleichen. Unter der Annahme, eine effiziente Implementierung begrenzt Warteschlange (mit einem Array), Sie haben die folgenden Hauptoperationen pro Zelle:

• BFS: Warteschlange Einfügen/Löschen, Besuchs jedes Knotens 5mal (viermal von Nachbarn und eine Auszeit die Warteschlange)
• Direkt Formel: zwei Subtraktion und zwei if s

Es würde davon abhängen wirklich auf dem Compiler und seine Optimierungen sowie die spezifische CPU und Speicherarchitektur zu sagen, welche besser durchführen würde.

Das sagte, würde ich raten, mit zu gehen, was Ihnen einfacher scheint. Beachten Sie jedoch, dass bei mehreren Quellen in der zweiten Lösung mehrere Durchläufe für das Array (oder mehrere Entfernungsberechnungen in einem Durchgang) erforderlich wären und bei einer ausreichend großen Anzahl von Quellen definitiv eine schlechtere Leistung als BFS hätte.

Answer 2

Sie brauchen keine Warteschlange oder so etwas überhaupt. Beachten Sie, dass, wenn (i, j) in der Entfernung d von (k, l) ist, eine Möglichkeit besteht, zu erkennen, dass die Entfernung nach links oder rechts gehen soll | i-k | mal und dann hoch oder runter | j-l | mal.

Also initialisieren Sie Ihre Matrix mit großen Zahlen und stecken Sie eine Null überall, wo Sie eine 1 in Ihrem Eingang haben. Jetzt tun Sie etwas wie folgt:

for (i = 0; i < sx-1; i++) { 
    for (j = 0; j < sy-1; j++) { 
    dist[i+1][j] = min(dist[i+1][j], dist[i][j]+1); 
    dist[i][j+1] = min(dist[i][j+1], dist[i][j]+1); 
    } 
    dist[i][sy-1] = min(dist[i][sy-1], dist[i][sy-2]+1); 
} 
for (j = 0; j < sy-1; j++) { 
    dist[sx-1][j] = min(dist[sx-1][j], dist[sx-2][j]+1); 
} 

An diesem Punkt haben Sie alle der kürzesten Wege gefunden, die nur nach unten oder rechts gehen. Wenn Sie eine ähnliche Funktion zum Hochgehen und Verlassen ausführen, gibt Ihnen dist[i][j] den Abstand von (i, j) zum nächsten 1 in Ihrer Eingabematrix.