Algorithmus zwei Punkte zu finden, am weitesten voneinander entfernt

StackOverflow https://stackoverflow.com/questions/477591

Frage

Im für einen Algorithmus sucht in einem Rennspiel Im Herstellung verwendet werden. Die Karte / Level / Spur zufällig so erzeugt wird, ich brauche zwei Orte zu finden, Start- und Ziel, dass die Verwendung des meisten der Karte macht.

  • Der Algorithmus ist in einem zweidimensionalen Raum
    • arbeiten
  • Von jedem Punkt kann man nur in vier Richtungen zum nächsten Punkt durchqueren; oben, unten, links, rechts
  • Die Punkte können nur entweder gesperrt oder nicht blockierte, nur unblockierte Punkte
    • verfahren werden

Im Hinblick auf die Berechnung der Entfernung, sollte es nicht sein, der „Vogel Weg“ für einen Mangel eines besseren Wortes. Der Weg zwischen A und B sollte länger sein, wenn es eine Wand (oder eine anderer Sperrbereich) zwischen ihnen ist.

Im nicht sicher, wo man anfangen, Kommentare sind sehr willkommen und vorgeschlagenen Lösungen sind in Pseudo-Code bevorzugt.

Edit: Richtig. Nach einem Blick durch den Code gs I gab es einen weiteren Schuss. Statt Python, schrieb ich dieses Mal ist es in C ++. Aber nach wie vor, auch nach Lesen auf Dijkstras Algorithmus , die Floodfill und Hosam Alys Lösung , scheitere ich jeden entscheidenden Unterschied zu erkennen. Mein Code funktioniert immer noch, aber nicht so schnell, wie Sie zu sein scheinen immer Sie zu laufen. Full Source ist auf pastie . Die einzigen interessanten Linien (ich glaube) ist die Dijkstra-Variante selbst auf den Leitungen 78-118.

Aber Geschwindigkeit ist nicht das Hauptproblem hier. Ich würde wirklich die Hilfe schätzen, wenn jemand nett genug sei, um die Unterschiede in den Algorithmen zu zeigen.

  • In Hosam Alys Algorithmus, der einzige Unterschied ist, dass er von den Grenzen durchsucht statt jeden Knoten?
  • In Dijkstras behalten Sie den Überblick und überschreiben die Strecke ging, aber nicht in Floodfill, aber das ist über es?
War es hilfreich?

Lösung

Unter der Annahme, die Karte rechteckig ist, können Sie eine Schleife über alle Grenzpunkte und eine Flutfüllung starten Sie den am weitesten entfernten Punkt vom Startpunkt zu finden: 

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

Ich denke, das in O(n^2) wäre. Wenn ich mich nicht irre, ist es (L+W) * 2 * (L*W) * 4, wo L die Länge und W ist die Breite der Karte, (L+W) * 2 die Anzahl der Grenzpunkte über den Umfang darstellt, (L*W) ist die Anzahl der Punkte, und 4 ist die Annahme, dass Hochwasser-fill einem Punkt a maximal 4mal würde den Zugang (aus allen Richtungen). Da n auf die Anzahl der Punkte entspricht, ist dies (L + W) * 8 * n gleichwertig, die besser sein sollte als O(n 2 ). (Wenn die Karte quadratisch ist, würde der Auftrag O(16n wird 1.5 ).)

Update: nach den Kommentaren, da die Karte eher ein Labyrinth ist (als ein mit einfachen Hindernissen, wie ich anfangs dachte), können Sie die gleiche Logik oben machen könnten, aber die Überprüfung alle Punkte in der Karte (wie an der Grenze zu den Punkten gegen nur). Dies sollte in der Reihenfolge des O(4n sein 2 ), die als beide noch besser ist F-W und Dijkstra.

Hinweis: Flood Füllung ist besser geeignet für dieses Problem da alle Vertices direkt über nur 4 Grenzen verbunden. Eine Breite erster Durchlauf der Karte kann relativ schnell Ergebnisse liefern (in nur O(n)). Ich gehe davon aus, dass jeder Punkt kann von jedem seiner vier Nachbarn, so dass die Koeffizienten in den Formeln oben in der Flutfüllung überprüft werden.

Update 2: Ich bin für all das positive Feedback dankbar Ich habe zu diesem Algorithmus erhalten. Besonderer Dank geht an @Georg für seine Bewertung .

P. S. Alle Kommentare oder Korrekturen sind willkommen.

Andere Tipps

Folgen auf die Frage nach Floyd-Warshall oder dem einfachen Algorithmus von Hosam Aly :

Ich habe ein Testprogramm, das beiden Methoden verwenden kann. Das sind die Dateien:

In allen Testfällen Floyd-Warshall durch eine große Größenordnung langsamer war, wahrscheinlich ist dies wegen der sehr begrenzten Menge an Kanten, die dieser Algorithmus helfen, dies zu erreichen.

Diese

waren die Zeiten, jedes Mal war das Feld quadruplet und 3 aus 10 Feldern waren ein Hindernis. 

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

Die Zeit des Hosam Aly scheint quadratisch zu sein, daher würde ich empfehlen, dass Algorithmus.  Auch der Speicherverbrauch von Floyd-Warshall ist n 2 , deutlich mehr als nötig. Wenn Sie eine Idee haben, warum Floyd-Warshall so langsam ist, lassen Sie einen Kommentar oder Beitrag bearbeiten.

PS: Ich habe nicht geschrieben C oder C ++ in einer langen Zeit, ich hoffe, ich habe zu viele Fehler nicht gemacht

.

Ich löschte meinen Original-Beitrag den Floyd-Warshall-Algorithmus zu empfehlen. : (

gs einen realistischen Benchmark tat und erraten, was FW ist wesentlich langsamer als Hosam Alys „flood fill“ Algorithmus für typische Kartengrößen! Also auch wenn F-W ein kühler Algorithmus und viel schneller als Dijkstra für dichte Graphen ist, kann ich es nicht mehr empfehlen für das Problem des OP, die sehr spärliche Graphen beinhalten (jeder Knoten hat nur 4 Kanten).

Für das Protokoll:

  • Eine effiziente Implementierung von Dijkstra-Algorithmus O (Elog V) Zeit für eine nimmt graph mit E Kanten und V Eckpunkten.
  • Hosam Alys "flood fill" ist eine Breitensuche , die O (V). Dies kann als ein Spezialfall des Dijkstra-Algorithmus gedacht werden, in denen kein Vertex seine Entfernung Schätzung revidiert hat.
  • Der Algorithmus von Floyd und Warshall O nimmt (V ^ 3 ) Zeit ist, um Code sehr einfach, und ist immer noch die schnellste für dichte Graphen (die Graphen, in denen Ecken zu vielen anderen Ecken der Regel verbunden sind). Aber es ist nicht die richtige Wahl für die Aufgabe des OP, die sehr spärliche Graphen handelt.

Es klingt wie das, was Sie wollen, ist die Endpunkte der Graph Durchmesser . Eine ziemlich gute und leicht zu berechnen Annäherung ist es, einen beliebigen Punkt zu holen, die am weitesten entfernten Punkt aus, dass finden, und dann von dort aus dem entferntesten Punkt zu finden. Die letzten beiden Punkte sollten in der Nähe sein, um maximal getrennt sind.

Für ein rechteckiges Labyrinth, das bedeutet, dass zwei Flutfüllungen sollten Sie ein ziemlich gutes Paar Start- und Endpunkte erhalten.

Raimund Seidel gibt eine einfache Methode Matrixmultiplikation mit der All-Paaren Distanzmatrix auf einer ungewichteten, ungerichteten Graphen zu berechnen (das ist genau das, was Sie wollen) im ersten Abschnitt seines Aufsatzes auf dem All-Pairs-Shortest-Path Problem in Ungewichtete ungerichtete Graphen  [Pdf] .

Die Eingabe ist die Adjazenzmatrix und die Ausgabe ist die all-Paare mit kürzestem Pfad Abstandsmatrix. Die Laufzeit ist O (M (n) * log (n)) für n Punkte, bei denen M (n) die Laufzeit Ihres Matrix-Multiplikation Algorithmus ist.

Das Papier gibt auch das Verfahren für die tatsächlichen Pfade der Berechnung (in der gleichen Laufzeit), wenn Sie diese auch benötigen.

Seidel-Algorithmus ist cool, weil die Laufzeit der Anzahl der Kanten unabhängig ist, aber wir kümmern uns eigentlich nicht hier, weil unser Graph spärlich ist. Jedoch kann dies immer noch eine gute Wahl sein (trotz der leicht-schlechter als n ^ 2 Laufzeit), wenn Sie die alle Paare Distanzmatrix wollen, und dies könnte auch einfacher zu implementieren und zu debuggen, als auf einem Labyrinth FloodFill.

Hier ist der Pseudo-Code: 

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

Um das Punktepaar mit dem größten Abstand bekommen wir wieder argmax_ij nur (d_ij)

einen Python-Mockup der dijkstra Lösung für das Problem Fertig. Code wurde ein bisschen lang, so gab ich es woanders: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

In der Größe I gesetzt, dauert es etwa 1,5 Sekunden, um den Algorithmus für einen Knoten auszuführen. Laufen sie für jeden Knoten ein paar Minuten dauert.

Dont scheinen allerdings zu arbeiten, es zeigt immer die linke obere und bottom Ecke als die längste Weg; 58 Fliesen. Was natürlich wahr ist, wenn Sie Hindernisse nicht haben. Aber auch ein paar zufällig platzierten hinzukommen, findet das Programm nach wie vor, dass man am längsten. Vielleicht ist es immer noch wahr, schwer zu testen, ohne fortgeschritteneren Formen.

Aber vielleicht kann es zumindest meinen Ehrgeiz zeigen.

Ok, „Hosam-Algorithmus“ ist eine Breite zunächst mit einer Vorselektion auf dem Knoten suchen. Dijkstra-Algorithmus sollte nicht hier angewendet werden, da die Kanten Gewichte nicht haben.

Der Unterschied ist von entscheidender Bedeutung, denn wenn die Gewichte der Kanten variieren, müssen Sie eine Menge von Optionen zu halten (alternative Routen) öffnen und überprüfen Sie sie bei jedem Schritt. Dies macht den Algorithmus komplexer. Mit der Breitensuche, erkunden Sie einfach alle Kanten einmal in einer Weise, die garantuees, dass Sie den kürzesten Weg zu jedem Knoten zu finden. das heißt, durch die Kanten in der Reihenfolge zu erkunden finden Sie sie.

Also im Grunde der Unterschied ist Dijkstra hat zu ‚Backtrack‘ und sieht an den Rand es vor, um sicherzustellen, erkundet hat, wird es den kürzesten Weg folgt, während die Breitensuche immer weiß, dass es auf den kürzesten Weg folgt.

Auch in einem Labyrinth, werden die Punkte auf der Außengrenze nicht garantiert Teil der längsten Strecke sein. Zum Beispiel, wenn Sie ein Labyrinth in Form einer riesigen Spirale haben, aber mit dem äußeren Ende in die Mitte zurück, könnte man zwei Punkte, die man im Herzen der Spirale und die andere am Ende der Spirale hat, die beide in der Mitte!

Also, ein guter Weg, dies zu tun, ist eine Breite zuerst von jedem Punkt Suche zu verwenden, aber den Ausgangspunkt nach einer Suche entfernen (Sie bereits alle Routen zu und von ihnen wissen). Komplexität der erste Breite ist O (n), wobei n = | V | + | E |. Wir tun dies, einmal für jeden Knoten in V, so wird es O (n ^ 2).

Ihre Beschreibung klingt für mich wie ein Labyrinth Routing Problem. Schauen Sie sich die Lee Algorithmus . Bücher über Place-and-Route Probleme in VLSI-Design helfen Sie können - Sherwani des „Algorithmen für VLSI Physical Design Automation " ist gut, und Sie können eine href finden <=" http://books.google.com/books?id=9XUY_zLiVVAC&dq=sait+youssef+design+automation&printsec=frontcover&source=bn&hl=en&sa= X & oi = book_result & resnum = 4 & ct = Ergebnis # PPA233, M1" rel = "nofollow noreferrer"> VLSI Physical Design Automation von Sait und Youssef nützlich (und billiger in der Google-Version ...)

Wenn Sie Ihre Objekte (Punkte) nicht bewegen, häufig können Sie solche führen eine Berechnung in einer viel kürzer als O (n ^ 3) Zeit.

Alles, was Sie brauchen, ist der Raum in große Netze und vorge berechnen die Zwischengitterabstand zu brechen. Dann Auswahl Punktpaare, die belegen fernsten Gitter eine Frage der einfachen Nachschlagen in einer Tabelle ist. Im Durchschnitt Fall müssen Sie weise paaren nur eine kleine Menge von Objekten überprüfen.

Diese Lösung funktioniert, wenn die Abstandsmetriken kontinuierlich sind. Wenn also zum Beispiel gibt es viele Hindernisse in der Karte ist (wie in Labyrinthen), könnte diese Methode fehl.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top