Was ist der beste Weg, um Pfade in einem großen Raster zu routen?
Ich arbeite an einem Algorithmus, um eine Menge von nicht durchschnittenen Pfaden in einem Gitter für a zu finden
gegebene Paare von Punkten ..
So für diese Paare:
(9,4) und (12,13)
Die Ausgabe sollte in etwa so aussehen:
%Vor%und drucken Sie "Blocked", wenn es nicht alle Pfade routen kann
Zuerst habe ich nach einem bereits erstellten Algorithmus gesucht, um alle einfachen Pfade zwischen 2 zu finden Punkte in einem Diagramm oder einem Raster. und ich fand dieses von @Casey Watson und @svick hier Es funktioniert wirklich gut, aber nur für kleine Graphen.
Ich habe es in C # .NET umgewandelt und es ein wenig verbessert, um Pfade von finden zu können maximale Länge X. und bauen Sie darauf meinen Gesamtalgorithmus auf.
Der, den ich gebaut habe, funktioniert in kleinen Graphen.
Hier sind Routen 9 Paare in einem 8x8 Raster.
aber es dauert eine große Zeit in größeren wie die 16x16 oder sogar die letzte, die ich vorhatte, das ist ein 3D-Modell von 16x16x2 So,
Der Algorithmus wurde entwickelt, um ein Tiefensuch-Algorithmus RECURSIVE zu sein, aber es hat viel Zeit gebraucht, um dem Benutzer einen Wert zurückzugeben. Deshalb habe ich beschlossen, es in Schleifen anstelle der rekursiven Aufrufe zu konvertieren, so dass ich von der Funktion yield return in .NET profitieren kann aber es half trotzdem nicht besser.
Die Schleifenversion des Algorithmus findet eine Route für ein Punktepaar in weniger als einer Sekunde, aber die rekursive Methode benötigte mehr als 90 Sekunden.
Wenn ich mit zwei Paaren versuchte, dauerte die Loop-Version ungefähr 342 Sekunden, aber die rekursive dauerte ungefähr 200 ..
So kann ich nicht wissen, was schneller ist ..!? das rekursive oder die Schleifen eins ..
Ich möchte wirklich den besten Weg wissen, dies zu tun.
Hinweis: Die erste Ziffer in der Nummer des Knotens bestimmt den Layer (Beginnt bei 1) ..
Hier ist der Code
%Vor%1 Antwort
Ich denke, die Antwort liegt darin, wie Sie die Knoten in Ihrem Gitter nummeriert haben. Für ein einfaches 2-dimensionales Gitter, 4 Knoten mal 4, würden Sie sie nummerieren: 00, 01, 02, 03, 10, 11, 12 ... 30, 31, 32, 33. Betrachten Sie sie als zusammengesetzte Zahlenstrings ( keine Dezimalwerte), die als dimensionsbasierte Knotenadressen fungieren.
In einem 3-dimensionalen Gitter würden sie 000, 001, 002 usw. bis 330, 331, 332, 333 nummeriert sein.
Wenn Sie alle Routen zwischen zwei Punkten 10 und 22 finden möchten, können Sie schnell ihre Entfernung berechnen, indem Sie die Abmessungsunterschiede hinzufügen: 1y ist eine weg von 2y und x0 ist zwei weg von x2. Daher ist der Knotenabstand 3, Sie müssen über 3 Kanten (insgesamt 4 Knoten) reisen, um das Ziel zu erreichen.
Der Lösungsraum (die einzigen Knoten, die jemals an einer Lösungsroute beteiligt sein könnten) kann durch Erstellen eines Satzes von eingebetteten FOR / NEXT-Schleifen, eine für jede Dimension, aufgelistet werden. In diesem Fall würden die Anfangs- und Endwerte von 10 und 22 10, 11, 12, 20, 21 und 22 ergeben.
Jetzt kommt der schlaue Teil. Sie können eine Tabelle mit Weiterleitungsverbindungen zwischen den Knoten in Ihrem Array vorberechnen (vorbereiten). Knoten 10 verbindet sich mit 20 und 11 (beide 1-dimensionale Differenz entfernt). Daraus können Sie eine Sequenz gültiger Pfade von 10 bis 22 generieren, indem Sie einen zu einer Dimensionsdifferenz hinzufügen, in welche Richtung Sie auch immer bewegen möchten (in einem 2D-Array können Sie nur eine von zwei Möglichkeiten wählen. In 3D Sie erhalten drei Möglichkeiten).
Jede Antwort sollte die kürzest mögliche Entfernung sein. Die Berechnungszeit für diesen Ansatz sollte Millisekunden sein. Auf einem dampfbetriebenen ZX81! ; o)
Ich würde gerne Diagramme geben, aber es scheint keine Möglichkeit zu geben, sie in stackoverflow hochzuladen.
Ich hoffe, das ist hilfreich für Sie.
Tags und Links .net c# performance