Suche eine Eulersche Tour
Ich versuche ein problem zu lösen, auf Udacity wie folgt beschrieben:
# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]
Kam ich auf die folgende Lösung, die zwar nicht so elegant, wie einige der rekursive algorithmen, scheint zu funktionieren in meinem test-Fall.
def find_eulerian_tour(graph):
tour = []
start_vertex = graph[0][0]
tour.append(start_vertex)
while len(graph) > 0:
current_vertex = tour[len(tour) - 1]
for edge in graph:
if current_vertex in edge:
if edge[0] == current_vertex:
current_vertex = edge[1]
elif edge[1] == current_vertex:
current_vertex = edge[0]
else:
# Edit to account for case no tour is possible
return False
graph.remove(edge)
tour.append(current_vertex)
break
return tour
graph = [(1, 2), (2, 3), (3, 1)]
print find_eulerian_tour(graph)
>> [1, 2, 3, 1]
Jedoch beim Absenden, bekomme ich auch abgelehnt, durch die Schüler. Mache ich etwas falsch? Ich sehe keinen Fehler.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hier ist ein Gültiger Fall, bei dem Ihr Algorithmus versagt:
Nutzen Sie die Kraft der
print
um herauszufinden, was passiertgraph
undcurrent_vertex
.Noch ein Tipp: Bewegen Sie den
else
nach unten, so dass es gehört zu denfor
und wird ausgeführt, wenn diefor
Schleife wird nicht unterbrochen. So wie es jetzt ist, kann es auch niemals ausgeführt werden. Nach, dass die Korrektur, die der Algorithmus dann noch immer nicht selbstverständlich.Der Algorithmus dann noch immer nicht selbstverständlich.
Der Algorithmus dann noch immer nicht selbstverständlich.
Bitte nicht kommentieren, die besagt, dass der code nicht funktioniert. Tut es das nicht. Der Algorithmus dann noch immer nicht, selbst wenn der code unten tut, was der OP im Sinn hatte. Der Punkt war, zu zeigen, dass die OP ' s Algorithmus ist falsch, was der OP nicht ermitteln konnte. Für eine korrekte Umsetzung des OP ' s Algorithmus benötigt wird (siehe unten). Eine korrekte Umsetzung eines falschen Algorithmus ist noch nicht die richtige Lösung.
Tut mir Leid, um diese Antwort noch schlimmer, indem alle diese langen Erklärungen, aber die Menschen weiterhin zu beschweren, dass der code nicht funktioniert (natürlich, der Punkt war, zu zeigen, dass es falsch ist). Sie auch downvote diese Antwort, wahrscheinlich, weil Sie erwarten, dass Sie in der Lage sein, den code kopieren, als eine Lösung. Aber das ist nicht der Punkt, der Punkt ist, zu zeigen, in der OP, dass es einen Fehler in seinem Algorithmus.
Der code unten nicht finden Eulersche Touren. Schauen Sie anderswo zu kopieren code für die Weitergabe Ihrer assingments!
Ausgabe:
Ich bin auch in der gleichen Vorlesung, WolframH die Antwort nicht für mich arbeiten. Hier ist meine Lösung (angenommen der Schüler):
Schieben alle möglichen
next node
in einen heap (search
), dann Suche nach jeder einer von Ihnen, während der Aufnahme.Hier ist ein Fall, die Ihr Algorithmus nicht umgehen kann: die vollständigen Graphen auf 4 Knoten. Kleben ein
print tour
dort erhalten Sie:Lasse ich Sie zu finden, um das problem mit Ihrem Ansatz-man könnte einfach google für eine vollständige Implementierung, da Sie nicht, ich nehme an, Sie wollen den Spaß es herauszufinden für sich selbst. :^)
Edit:
Hmmph. Ich gebe zu, ich dachte, es war einfach eine verpasste Fehlerfall an den start. Eh, @WolframH schlagen mir ein aktualisiertes Beispiel, aber man könnte auch einen Blick auf die komplette Grafik auf 5 Eckpunkte, in denen der code gibt
kann leicht die Kanten (2,3), (2,4) und (3,4).
Kann die Frage leicht gelöst werden, als die oben genannten Lösungen mit einfachen Rekursion.
Dieser code funktioniert für alle Eingaben Liste der Tupel und gibt eine Liste von der tour.
Pls senden Sie Vorschläge und änderungen.
Dank
@WolframH:Dein code funktioniert nicht, wenn keine Schleife existiert in dem Graphen und der Tupel eingegeben werden, nur um fail code.
Ging ich durch den gleichen Kurs auf Udacity. Und ich umgesetzt Hierholzer-Algorithmus nach dem Lesen von Wikipedia. Hier ist der link zum Algorithmus https://en.wikipedia.org/wiki/Eulerian_path
Und unten ist mein code. Kein Zweifel, es wurde akzeptiert, indem Sie den Schüler(nach einigen Python ist3, um Python2-änderungen). 🙂
Hoffe, das hilft.
Obwohl der code nicht für Ungerichtete Graphen aber läuft perfekt auch mit gerichteten lieben. Wie auch immer, es immer noch nicht das problem löst, an hand von Udacity ' s Seite, kann aber behandelt werden wie eine niedrigere version des gleichen. Bitte nicht dagegen, die schlecht verwendet Python als ich bin noch neu in der Sprache.
Beiden test-Szenarien eine relativ gute Komplexität am unteren Rand Hinzugefügt.
Hier ist der original-code im Gregor Ulmer-Webseite auf, und es funktioniert.
Diese Lösung ist optimiert für O(V+E) Komplexität, d.h. linear in der Anzahl der Kanten und Ecken in dem Graphen
Für diejenigen, die direkt wünschend zu sehen Sie den code: https://github.com/cubohan/py-algos/blob/master/eulerian_tour.py
Beachten Sie, dass der code Verstöße gegen die Lesbarkeit und TROCKEN design-hauptsächlich aber nach dem Lesen der Erklärung, Sie kann leicht produzieren Sie Ihre eigene version.
**Zuerst das problem kann unterteilt werden diese Teilaufgaben: **
Bauen Sie die Grafik in eine freundlichere Struktur als eine Liste von Kanten für eine leichtere Verarbeitung ich.e (Angrenzens Listen)
Finden, der Grad jedes Knotens, um zunächst prüfen, ob eine Eulersche Tour möglich ist (gibt es nur noch Grad? Auch, SPEICHERN Sie diese Werte in einem dict mit Knoten als key => später verwendet zu werden)
Bauen die Eulersche tour
Die Idee hinter meiner Lösung ist einfach.
Wählen Sie den Knoten mit dem höchsten Grad, als Ausgangspunkt, und legen Sie es als der aktuelle Knoten. (Hinweis: dies erreichen Sie in der gleichen Zeit, während die Berechnung der Grad jeder Ecke. Speichern Sie alle diese Stufen in einem Wörterbuch.)
Fügen Sie aktuelle Knoten in der route-Liste was ist Ihre Antwort (Hinweis: auch ein Wörterbuch der Eckpunkte und die zugehörigen Indizes in der route-Liste. Dies wird später verwendet werden.)
Besuchen Sie die erste Kante der aktuellen vertex-wenn es nicht bereits besucht. (Hinweis: Ein Wörterbuch der besuchten Kanten beibehalten wird, der Schlüssel zu diesem dict ist eine sortierte Tupel der paar Eckpunkte bilden den Rand. Nach dem Besuch einer Kante, markieren Sie Sie besucht, indem Sie Sie in das dict.)
Pflegen Sie eine Anzahl von Grad restlichen des aktuellen vertex-und der besuchten Knoten (Dies wird sich als nützlich erweisen später) (Hinweis: Sie müssen subtrahieren Sie 1 von der dict-Grad, die Sie generieren, bevor Sie jedes mal, wählen Sie eine Kante)
Wechseln Sie aktuelle vertex zu vertex, die am anderen Ende der Kante, die Sie beschlossen, zu besuchen.
Wiederholen Sie die Schritte 2-5, bis Sie nicht finden können, eine unbesuchte Kante in der aktuellen vertex. (Hinweis: dies bedeutet, dass Sie zurückgekehrt sind, um Ihre Start-vertex)
Nun betrachten Sie dieses: Beachten Sie, dass alle nicht besuchten Kanten/vertices bilden Teilgraphen in der Haupt-Grafik, die die gleichen Eigenschaften haben wie das main Diagramm also eine Eulersche tour ist möglich von jeder der Ecken des Teilgraphen beginnend und endend an der gleichen vertex.
Alle unvisted Kanten können so besucht unter Eulersche Touren in diesen Teilgraphen müssen Sie nur verschmelzen diese sub-Touren mit der ersten tour.
Weiter:
Du eine Schleife durch alle Knoten des Graphen und bauen eine subtour in der gleiche Prozess, wie aufgeführt, für die main tour, wenn und nur wenn der reduzierte Grad von diesem Knoten nicht null ist,
Die Möglichkeit, diese Touren verschmelzen mit der route-Liste berechnete vorher, ist, dass Sie ersetzen die position des vertex, die Sie erwägen, zu beginnen, eine subtour aus in der route-Liste mit der subtour-output-Liste und später Abflachung dieser route-Liste
Wir sind noch nicht fertig! Was ist falsch oben?
Was passiert, wenn man einen nicht-null-Grad-vertex, die bisher NICHT BESUCHT und nicht in der route-Liste?!
Eine Einschränkung:
Dies ist ein außergewöhnlicher Fall.
Auftreten können Scheitelpunkte nicht besucht, bevor und damit Sie nicht in die main route-Liste.
IGNORIEREN Sie DIESE beim looping! Einer der Eckpunkte, die Sie bereits besucht haben, die mit nicht-null Grad reduziert wird GARANTIERT dazu führen, diese Eckpunkte in die subtour erstellen Sie ausgehend von diesen.
Wie ist das möglich??!!
Zeichnen Sie einen Graphen aus der test-Fall gegeben in dem link auf den code, und Sie werden verstehen. Trace heraus, was Ihr algo tut jeden Schritt des Prozesses. Zeichnen Sie es! Ein Bild ist log(N) Komplexität für das Verständnis und die Worte O(n2).
Ah, und beachten Sie, dass diese Garantie hält nur, wenn alle Kanten in der Liste der Eingänge in form einer einzigen Grafik und nicht zwei getrennte, unzusammenhängende Graphen.
Können Sie imitieren das Verhalten der BFS-Algorithmus und Huckepack auf Sie.
Hinweis: ich habe nicht versucht, schreiben Sie die Antwort, die die Verwendung von verknüpften Listen, weil verketteten Listen erfordert die Festlegung 2 Klassen (Definition von Knoten und deren Verhalten und definiert die gesamte verkettete Liste und seiner Verhaltensweisen). Doch für mehr Effizienz in der (append) und (entfernen) Verhaltensweisen, die Sie verwenden sollten, verknüpfte Listen anstelle von arrays :
Was ist, wenn wir dies tun? ( gerade überprüft und es ging udacity-test!!)