Hallo liebe Pythongemeinde,
ich hätte da folgendes Problem und weiß leider nicht wie ich es lösen kann:
Ich habe eine Art Startpunkt, mehrere Zwischenpunkte und einen Endpunkt (Die Punkte an sich sind Objekte)
Nun habe ich eine Funktion die zu jedem Punkt seine Nachbarpunkte bestimmt
Es entsteht praktisch ein Baum, deren Äste immer dann aufhören, wenn er auf den Endpunkt stößt.
Jetzt bräuchte ich eine Funktion, die mir alle die Punkte, von Start zu Ende, bei allen Möglichkeiten den Baum zu "durchwandern "in einer Liste zurückgibt,
allerdings weiß ich nicht, wie tief der Baum ist und es darf auch kein Punkt doppelt passiert werden.
Die Punkte sind in einer globalen Liste gespeichert, das erste Element ist der Startpunkt, das letzte der Endpunkt
Danke im voraus!
Baum durchsuchen
-
BlackJack
@Tobs: Das klingt nach ganz normaler Tiefensuche auf einem Graphen. Vielleicht hilft Dir ja das `networkx`-Paket bei der Aufgabe.
Danke für die schnelle Antwort! 
Jemand hat mal gemeint, dass man eine Funktion in einer Funktion usw. aufrufen könnte, die dann
ihr Ergebnis immer an die höhere Funktion weitergibt, so dass die höchste Funktion dann die Lösung
zurückgibt. Ist so etwas überhaupt möglich, und wenn ja, wie?
Also:
def Funktion():
...
gesamtloesung = Funktion()
Wäre echt toll, wenn ihr mir das erklären könntet
Jemand hat mal gemeint, dass man eine Funktion in einer Funktion usw. aufrufen könnte, die dann
ihr Ergebnis immer an die höhere Funktion weitergibt, so dass die höchste Funktion dann die Lösung
zurückgibt. Ist so etwas überhaupt möglich, und wenn ja, wie?
Also:
def Funktion():
...
gesamtloesung = Funktion()
Wäre echt toll, wenn ihr mir das erklären könntet
Okay, unter dem Stichwort Rekursive Funktionen hab ich in Google eine ganze Menge gefunden, danke für den Begriff
Beim ausprobieren, habe ich allerdings festgestellt, dass Python 3 nur eine Schachtelung bis 977 unterstützt.
Wie stelle ich es an, wenn ich tiefer Schachteln will?
Beim ausprobieren, habe ich allerdings festgestellt, dass Python 3 nur eine Schachtelung bis 977 unterstützt.
Wie stelle ich es an, wenn ich tiefer Schachteln will?
Man kann das Rekursionslimit erhöhen, aber irgendwie sieht das so aus, als sollte man erst gar keine Rekursion verwenden.Tobs hat geschrieben:Wie stelle ich es an, wenn ich tiefer Schachteln will?
-
BlackJack
@Tobs: Vergiss die Funktion zum setzen des Limits, die ist gefährlich, und schreibe eine iterative Lösung die den impliziten Stapelspeicher bei rekursiven Aufrufen explizit selbst verwaltet.
Jede Rekursion kann in eine Schleife umgewandelt werden. Manchmal ist das trivial, manchmal erfordert das etwas Nachdenken. Bei der Tiefensuche bietet sich ein Stack mit den noch zu besuchenden Knoten an. Darüber gibt es aber auch genügend Literatur.
Die Frage in deinem Fall: Interessiert dich das Rekursionslimit überhaupt? Wenn dein Baum nicht besonders tief ist, dann wirst du nie an das Rekurionslimit von Python stoßen. Und ein Baum mit einer Tiefe von etwa 1000 wäre schon sehr ungewöhnlich. Wenn der auch nur halbwegs balanciert ist, dann könntest du diesen niemals vollständig durchsuchen.
Die Frage in deinem Fall: Interessiert dich das Rekursionslimit überhaupt? Wenn dein Baum nicht besonders tief ist, dann wirst du nie an das Rekurionslimit von Python stoßen. Und ein Baum mit einer Tiefe von etwa 1000 wäre schon sehr ungewöhnlich. Wenn der auch nur halbwegs balanciert ist, dann könntest du diesen niemals vollständig durchsuchen.
Das Leben ist wie ein Tennisball.
Ich hab jetzt mal darauf gesetzt, dass der Fragesteller die Dokumentation liest: "This should be done with care, because a too-high limit can lead to a crash."BlackJack hat geschrieben:@Tobs: Vergiss die Funktion zum setzen des Limits, die ist gefährlich, [..]
Der rekursive Ansatz ist hier meiner Meinung nach ohnehin falsch.
-
BlackJack
@/me: Ja aber was ist denn ein zu hoher Wert? Ohne das auch nur ansatzweise zu wissen, und zwar nicht nur für die Python-Version/-Implementierung die man gerade selber auf dem Rechner hat, ist diese Funktion IMHO nutzlos weil potentiell jeder Wert der höher als die Voreinstellung ist zu einem Absturz führen kann.
Edit: Und ein rekursiver Ansatz bei einer Tiefensuche ist *der* naheliegende Ansatz.
Edit: Und ein rekursiver Ansatz bei einer Tiefensuche ist *der* naheliegende Ansatz.
Okay, ich muss euch jetzt leider nochmal was fragen
Ich hab meine Liste mit den Objekten. [O1,O2,O3]
Und eine Funktion mit der ich die Nachbarn("im Sinne des Programmes zusammenhängende Objekte") feststellen kann: Ox.get_neighbours() #Gibt Liste mit Nachbarobjekten zurück.
Ich habe einen Startpunkt: O1
Und einen Endpunkt: O3
Nun brauche ich alle Wege vom Startpunkt bis zum Endpunkt, in dem vereinfachten Beispiel dann nur O1,O2,O3.
Dabei darf kein Objekt doppelt vorkommen, allerdings müssen alle Wege erfasst werden.
Ich weiß nicht wie viele Objekte die Liste enthält.
Wenn ihr versteht was ich meine, freue ich mich über eure Antwort
(Ich hab mir sowas ungefähr wie eine for-Schleife in einer geschachtelten Funktion vorgestellt)
Ich hab meine Liste mit den Objekten. [O1,O2,O3]
Und eine Funktion mit der ich die Nachbarn("im Sinne des Programmes zusammenhängende Objekte") feststellen kann: Ox.get_neighbours() #Gibt Liste mit Nachbarobjekten zurück.
Ich habe einen Startpunkt: O1
Und einen Endpunkt: O3
Nun brauche ich alle Wege vom Startpunkt bis zum Endpunkt, in dem vereinfachten Beispiel dann nur O1,O2,O3.
Dabei darf kein Objekt doppelt vorkommen, allerdings müssen alle Wege erfasst werden.
Ich weiß nicht wie viele Objekte die Liste enthält.
Wenn ihr versteht was ich meine, freue ich mich über eure Antwort
(Ich hab mir sowas ungefähr wie eine for-Schleife in einer geschachtelten Funktion vorgestellt)