Algorithmus zum Finden von zwei am weitesten voneinander entfernten Punkten

Question

Ich suche einen Algorithmus, der in einem Rennspiel verwendet werden soll, an dem ich arbeite. Die Karte/Level/Strecke wird zufällig generiert, also muss ich zwei Orte finden, Start und Ziel, die den größten Teil der Karte ausnutzen.

• Der Algorithmus soll in einem zweidimensionalen Raum arbeiten
• Von jedem Punkt aus kann man sich nur in vier Richtungen zum nächsten Punkt bewegen: nach oben, unten, links, rechts
• Punkte können nur entweder blockiert oder nicht blockiert sein, nur nicht blockierte Punkte können durchfahren werden

Was die Berechnung der Entfernung betrifft, so sollte es sich nicht um den "Vogelpfad" handeln, um ein besseres Wort zu finden. Der Weg zwischen A und B sollte länger sein, wenn sich eine Wand (oder ein anderes Hindernis) zwischen ihnen befindet.

Ich weiß nicht, wo ich anfangen soll, Kommentare sind sehr willkommen und Lösungsvorschläge werden in Pseudocode bevorzugt.

Edit : Richtig. Nach der Durchsicht von gs' Code Ich habe es noch einmal probiert. Anstelle von Python habe ich es diesmal in C++ geschrieben. Aber selbst nach der Lektüre von Dijkstras Algorithmus die Hochwasserdeponie y Hosam Alys Lösung kann ich keinen entscheidenden Unterschied erkennen. Mein Code funktioniert immer noch, aber nicht so schnell, wie Sie Ihren zum Laufen zu bringen scheinen. Der vollständige Quelltext ist auf Nudeln . Die einzige interessante Zeile ist (so vermute ich) die Dijkstra-Variante selbst in den Zeilen 78-118.

Aber Geschwindigkeit ist hier nicht das Hauptthema. Ich wäre wirklich dankbar, wenn jemand so freundlich wäre, mich auf die Unterschiede in den Algorithmen hinzuweisen.

• Besteht bei Hosam Alys Algorithmus der einzige Unterschied darin, dass er von den Rändern aus scannt und nicht von jedem Knoten aus?
• In Dijkstras kann man die zurückgelegte Strecke verfolgen und überschreiben, in floodfill nicht, aber das war's dann auch schon?

Answer 1

Unter der Annahme, dass die Karte rechteckig ist, können Sie eine Schleife über alle Randpunkte ziehen und eine Flutung starten, um den am weitesten vom Startpunkt entfernten Punkt 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 schätze, das wäre in O(n^2) . Wenn ich mich nicht irre, ist es (L+W) * 2 * (L*W) * 4 , donde L ist die Länge und W ist die Breite der Karte, (L+W) * 2 steht für die Anzahl der Grenzpunkte innerhalb des Umkreises, (L*W) ist die Anzahl der Punkte, und 4 ist die Annahme, dass die Hochwasserschüttung maximal 4 Mal (aus allen Richtungen) auf einen Punkt treffen würde. Da n der Anzahl der Punkte entspricht, ist dies gleichbedeutend mit (L + W) * 8 * n was besser sein sollte als O(n 2 ) . (Wenn die Karte quadratisch ist, wäre die Reihenfolge O(16n 1.5 ) .)

更新しました。 Da es sich bei der Karte eher um ein Labyrinth handelt (und nicht um ein Labyrinth mit einfachen Hindernissen, wie ich anfangs dachte), könnte man dieselbe Logik wie oben anwenden, aber alle Punkte auf der Karte überprüfen (und nicht nur die Punkte am Rand). Dies sollte in folgender Reihenfolge geschehen O(4n 2 ) was immer noch besser ist als die von F-W und Dijkstra.

Nota: Auffüllen mit Hochwasser ist für dieses Problem besser geeignet, da alle Scheitelpunkte über nur 4 Grenzen direkt verbunden sind. Eine erste Durchquerung der Karte in der Breite kann relativ schnell Ergebnisse liefern (in nur O(n) ). Ich gehe davon aus, dass jeder Punkt in der Flutfüllung von jedem seiner 4 Nachbarn geprüft werden kann, daher der Koeffizient in den obigen Formeln.

Update 2: Ich bin dankbar für die vielen positiven Rückmeldungen, die ich zu diesem Algorithmus erhalten habe. Besonderen Dank an @Georg für seine Überprüfung .

P.S. Alle Kommentare oder Korrekturen sind willkommen.

Answer 2

Fortsetzung der Frage nach Floyd-Warshall oder dem einfachen Algorithmus von Hosam Aly :

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

• Labyrinth-Ersteller
• längste Strecke finden

In allen Testfällen war Floyd-Warshall um ein Vielfaches langsamer, was wahrscheinlich auf die sehr begrenzte Anzahl von Kanten zurückzuführen ist, die diesem Algorithmus dabei helfen, dies zu erreichen.

Das waren die Zeiten, in denen das Feld jeweils vierfach war und 3 von 10 Feldern ein Hindernis darstellten.

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 von Hosam Aly scheint quadratisch zu sein, daher würde ich empfehlen, diesen Algorithmus zu verwenden. Auch der Speicherverbrauch von Floyd-Warshall ist n 2 eindeutig mehr als nötig. Wenn Sie eine Idee haben, warum Floyd-Warshall so langsam ist, hinterlassen Sie bitte einen Kommentar oder bearbeiten Sie diesen Beitrag.

PS: Ich habe schon lange nicht mehr in C oder C++ geschrieben, ich hoffe, ich habe nicht zu viele Fehler gemacht.

Answer 3

Es klingt so, als ob Sie die Endpunkte durch das Grafikdurchmesser . Eine recht gute und leicht zu berechnende Annäherung besteht darin, einen zufälligen Punkt zu wählen, den am weitesten entfernten Punkt davon zu finden und dann den am weitesten entfernten Punkt von diesem Punkt zu finden. Diese beiden letzten Punkte sollten nahezu maximal voneinander getrennt sein.

Für ein rechteckiges Labyrinth bedeutet dies, dass man mit zwei Flutungen ein ziemlich gutes Paar von Start- und Endpunkten erhalten sollte.

Answer 4

Ich habe meinen ursprünglichen Beitrag, in dem ich den Floyd-Warshall-Algorithmus empfahl, gelöscht :(

gs hat einen realistischen Benchmark durchgeführt und raten Sie mal, F-W ist wesentlich langsamer als Hosam Alys "flood fill"-Algorithmus für typische Kartengrößen! Obwohl F-W also ein cooler Algorithmus ist und viel schneller als der von Dijkstra für dichte Graphen, kann ich ihn nicht mehr für das Problem des Auftraggebers empfehlen, bei dem es um sehr dünne Graphen geht (jeder Vertex hat nur 4 Kanten).

Für das Protokoll:

• Eine effiziente Umsetzung von Dijkstra-Algorithmus benötigt O(Elog V) Zeit für einen Graphen mit E Kanten und V Scheitelpunkten.
• Hosam Alys "Flutfüllung" ist eine Suche in der Breite zuerst was O(V) ist. Man kann sich dies als einen Spezialfall des Dijkstra-Algorithmus vorstellen, bei dem kein Knoten seine Entfernungsschätzung revidieren kann.
• El Floyd-Warshall-Algorithmus benötigt O(V^3)-Zeit, ist sehr einfach zu programmieren und ist immer noch die schnellste Lösung für dichte Graphen (Graphen, bei denen die Eckpunkte typischerweise mit vielen anderen Eckpunkten verbunden sind). Aber es ist nicht die richtige Wahl für die Aufgabe des Auftraggebers, die sehr spärliche Graphen umfasst.

Answer 5

Raimund Seidel gibt im ersten Abschnitt seiner Arbeit eine einfache Methode zur Berechnung der Abstandsmatrix für alle Paare auf einem ungewichteten, ungerichteten Graphen (was genau das ist, was Sie wollen) an, indem er die Matrixmultiplikation verwendet Zum All-Pairs-Shortest-Path Problem in ungewichteten, ungerichteten Graphen [pdf] .

Die Eingabe ist die Adjazenzmatrix und die Ausgabe ist die Matrix der kürzesten Wege für alle Paare. Die Laufzeit ist O(M(n)*log(n)) für n Punkte, wobei M(n) die Laufzeit Ihres Matrixmultiplikationsalgorithmus ist.

Das Papier gibt auch die Methode zur Berechnung der tatsächlichen Pfade (in der gleichen Laufzeit), wenn Sie dies auch benötigen.

Seidels Algorithmus ist cool, weil die Laufzeit unabhängig von der Anzahl der Kanten ist, aber das ist hier eigentlich egal, weil unser Graph spärlich ist. Allerdings kann dies immer noch eine gute Wahl sein (trotz der etwas schlechteren als n^2 Laufzeit), wenn man die Abstandsmatrix aller Paare haben möchte, und dies könnte auch einfacher zu implementieren und zu debuggen sein als floodfill auf einem Labyrinth.

Hier ist der Pseudocode:

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 Punktpaar mit dem größten Abstand zu ermitteln, geben wir einfach argmax_ij(d_ij) zurück