Einen Baum durchlaufen

[Minz]

@w3Seek
ja, den hatte ich ja schon erwähnt, nur muss ich dafür zunächst einen Baum haben, bevor ich den anwenden kann...deswegen

werde ich zunächst Alzaimers Tipp befolgen und versuchen einen rekursiven Algorithmus zu finden. So war eigentlich auch mein erster gedanklicher Ansatz, nur fehlten mir dazu die nötigen Voraussetzungen, z.B.

Zitat:

1: (2,10) , (3,10) , (4,14)
2: (1,10) , (4,10)
3: (1,10) , (4,10)
4: (1,10) , (2,10) , (3,10)

Wenn ich diese Struktur in Arrays oder Matrixen habe, kann ich mir darauf eine Rekursion vorstellen. In gewisser Weise ist der Baum damit repräsentiert. Wobei es 4: (1,14) ... sein müsste :zwinker:

Und wenn ichs nicht hinkriege, nehme ich Alzaimers Algo, den mir dizzy genannt hat. Den hab ich schon getestet und funktioniert wunderbar :mrgreen: da muss ich die Buchstaben nur noch in Zahlen verwandeln, was kein Prob sein dürfte.

Thx erstmal an alle!

[alzaimar]

@Minz: Der Fehler wurde von mir nur eingebaut, um zu testen, ob Du alles auch verstanden hast :oops:
Frage: Wieviele Knoten hast Du denn in deinem Graphen (AKA: Wie viele Städte muss der Reisende besuchen?')

[Minz]

also ich fange mit fünf Städten an 1 bis 5

wobei Stadt 1 der Startpunkt ist.

Habe bis jetzt die Matrix erzeugt und die Rekursion läuft zumindest soweit, das ich die erste Zahlenfolge bekomme: 1 2 3 4 5

Nur leider haperts noch bei den restlichen Kombinationen, ich hasse Rekursionen, das fühlt sich so an, als würde mein Kopf sich gleich mitdrehen :mrgreen:
Das Problem liegt noch daran, dass ich nach der ersten Kombination 1 2 3 4 5 bei der 3 landen müsste und an der Stelle muss der wissen, dass die 4 schon probiert wurde, so dass er mit der 5 weitermacht 1 2 3 5 4

Naja noch ein bissel drehen dann hoffe ich klappt das :wall:

Ansonsten dürfte Dein Algo mit den Permutationen auch von der Geschwindigkeit her schon fast optimal sein - im Vergleich zu Rekursionen

[Jelly]

Zitat:

Zitat von alzaimar

wenn a ein Nachbar von b ist , dann ist ja auch b ein nachbar von a...

Wenn du aber Einbahnstrassen berücksichtigt, führt aber kein Weg von B nach A, obwohl einer von A nach B führt. Also ich würde dann lieber alles doppelt speichern...

In Der Entwickler war mal vor Jahren ein Artikel drin, wo der A* Algorythmus erklärt war. Durchwühl mal in deren Ausgabenarchiv. Es lohnt sich die Ausgabe nachzubestellen.

[dizzy]

Wie oben schon mal beschrieben hilft A* hier nicht weiter, da er nicht die Bedingung erfüllt alle Knoten zu besuchen. A* ist nur geeignet wenn man die kürzeste (bzw. schnellste - A* berücksichtigt auch eine Kostenfunktion) finden will. Dieser Weg wird aber nicht über alle Knoten laufen (können).

[alzaimar]

@Jelly: Ich hatte das erstmal als ungerichteten Graphen betrachtet, weiter unten bin ich auf die Möglichkeit der unterschiedlichen Bewertung ("b liegt auf einem Berg") eingegangen. Trotzdem danke für den Hinweis...

@Minz: Eine Möglichkeit, bei Rekursion eine Gehirnverwurstung zu verhindern, ist, sich nur zu überlegen, wie ich von einem Knoten zum nächsten komme. Wenn dabei alle Sonderfälle (schon besucht etc.) berücksichtigt werden, hast Du es fast. Dann musst du nur noch die geeignete Anfangsbedingung schaffen und fertig. Wer die "Vollständige Induktion" beherrscht, kann auch rekursive Routinen implementieren. Du solltest Dur nochmal meinen Visit-Algorithmus anschauen. Ich markiere die Knoten, die ich besucht habe.

[omata]

Moin,

habe mich mal dran versucht...

MfG
Thorsten

Heinweis zum Programm: Steuerung erfolgt mit der Maus