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

Fertigstellung eines Python-Mockups der Dijkstra-Lösung für das Problem. Der Code wurde ein bisschen lang, also habe ich ihn woanders gepostet: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

Bei der von mir eingestellten Größe dauert es etwa 1,5 Sekunden, den Algorithmus für einen Knoten auszuführen. Die Ausführung für jeden Knoten dauert ein paar Minuten.

Scheint aber nicht zu funktionieren, es wird immer die obere linke und untere rechte Ecke als der längste Weg angezeigt; 58 Kacheln. Was natürlich richtig ist, wenn man keine Hindernisse hat. Aber selbst wenn man ein paar zufällig platzierte Hindernisse hinzufügt, findet das Programm diesen Weg immer noch am längsten. Vielleicht ist es immer noch wahr, schwer zu testen ohne fortgeschrittene Formen.

Aber vielleicht kann es zumindest meinen Ehrgeiz zeigen.

Answer 2

Ok, der "Hosam-Algorithmus" ist eine Breitensuche mit einer Vorauswahl an Knotenpunkten. Der Dijkstra-Algorithmus sollte hier NICHT angewendet werden, da Ihre Kanten keine Gewichte haben.

Der Unterschied ist entscheidend, denn wenn die Gewichte der Kanten variieren, muss man sich viele Optionen (alternative Routen) offen halten und diese bei jedem Schritt überprüfen. Dadurch wird der Algorithmus komplexer. Bei der Breitensuche werden einfach alle Kanten einmal in einer Weise untersucht, die gewährleistet, dass der kürzeste Weg zu jedem Knoten gefunden wird, d. h. die Kanten werden in der Reihenfolge untersucht, in der sie gefunden werden.

Der Unterschied besteht also darin, dass Dijkstra "zurückgehen" und sich die bereits erkundeten Kanten ansehen muss, um sicherzustellen, dass er dem kürzesten Weg folgt, während die Suche nach der Breite immer weiß, dass sie dem kürzesten Weg folgt.

Außerdem ist in einem Labyrinth nicht garantiert, dass die Punkte am äußeren Rand Teil der längsten Route sind. Wenn man zum Beispiel ein Labyrinth in Form einer riesigen Spirale hat, deren äußeres Ende in die Mitte zurückführt, könnte man zwei Punkte haben, einen in der Mitte der Spirale und den anderen am Ende der Spirale, beide in der Mitte!

Ein guter Weg, dies zu tun, besteht darin, von jedem Punkt aus eine Breitensuche durchzuführen, aber den Ausgangspunkt nach einer Suche zu entfernen (Sie kennen bereits alle Routen zu und von ihm). Die Komplexität von breadth first ist O(n), wobei n = |V|+|E|. Wir machen dies einmal für jeden Knoten in V, also wird es O(n^2).

Answer 3

Ihre Beschreibung klingt für mich wie ein Irrgartenführung Problem. Überprüfen Sie die Lee-Algorithmus . Bücher über Place-and-Route-Probleme im VLSI-Design können Ihnen helfen - Sherwanis "Algorithmen für die Automatisierung des physikalischen VLSI-Designs" ist gut, und Sie finden vielleicht VLSI-Automatisierung des physikalischen Entwurfs von Sait und Youssef nützlich (und billiger in der Google-Version...)

Answer 4

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

Es genügt, den Raum in große Raster aufzuteilen und den Abstand zwischen den Rastern im Voraus zu berechnen. Die Auswahl der Punktpaare, die die am weitesten voneinander entfernten Raster belegen, ist dann eine Frage des einfachen Nachschlagens in einer Tabelle. Im Normalfall müssen Sie nur eine kleine Anzahl von Objekten paarweise überprüfen.

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