Einen Baum durchlaufen

[Minz]

Hallo,

es gibt da ja das Travelling Salesman Problem -

angenommen ich habe 5 Städte und ich starte von Stadt 1 und will alle anderen 4 Städte anfahren und das auf der kürzesten Strecke.

Wie kann ich jetzt möglichst einfach alle möglichen Gesamtstrecken ausrechnen.

Mir ist klar, dass ich irgendwann auf Geschwindigkeits-/Zeitprobleme stoße, wenn es mehrere Städte werden, aber bei 5! (5 Städte) hält sich das ganze mit 120 Kombinationen oder so in Grenzen. Ich möchte da blos die Methode erfahren, mit der ich alle Kombinationen ausrechnen kann, ohne evtl. viele Prüfungen oder so zu machen.

Das Verfahren kann auch gerne langsamer sein, hauptsache es ist gut nachvollziehbar :mrgreen:

Danke schonmal Minz

[Hansa]

Das nennt sich Fakultät. => suchen

[dizzy]

Zitat:

Zitat von Hansa

Das nennt sich Fakultät. => suchen

:roll: Das ist aber kaum auf sein Problem bezogen. Die 5! hat er mit 120 schon sehr richtig als Anzahl der möglichen Permutationen angegeben (von denen aber viele wegfallen, da der Startpunkt - so wie ich das verstanden habe - fest sein soll. Es kommt also auf nur 4! Möglichkeiten raus.)

Was hier wirklich gefragt ist, ist ein Algo zur Traversierung von einem Graphen. Und Graphenprobleme sind ein wohldefinierter und bekannter Umstand in der EDV, und es gibt reichlich Möglichkeiten einen Graphen zu durchlaufen. Eine Methode die nun wirklich alle Knoten besucht kenne ich leider nicht aus dem Kopf, aber mit den hier genannten Begriffen lässt sich weit aus problemorientierter googeln als mit "Fakultät" ;). Soll z.B. nur der schnellste Weg zwischen zwei Knoten gefunden werden, so ist A* ein sehr guter Algo. Nur leider (oder zum Glück :D) besucht er nicht alle Knoten, sondern nur die nötigsten.


Gruss,
Fabian

[MrSpock]

@Hansa: Solche Postings kannst du dir wirklich schenken. Das ist nicht nur am Thema vorbei, sondern hilft Minz überhaupt nicht. Er hat doch kein Problem mit dem Begriff oder der Definition der Fakultät. Lies doch erst einmal um was es geht und wenn du dann einen sinnvollen Beitrag hast, kannst du den gerne posten. Sonst unterlasse einfach sinnlose Kommentare. :warn:

[alzaimar]

Graphen durchlaufen, z.B. so:

Delphi-Quellcode:

Procedure Visit (aNode : TNode);
Var
  Neighbor: TNode;

Begin
  if aNode.Visited Then Exit;
  aNode.Visited := True;
  Foreach Neighbor in aNode.Neighbors do
    Visit (Child);
End;

Vorher natürlich im gesamten Graphen die 'Visited' Eigenschaft auf False setzen.
Beim Travelling Salesman Problem merkst Du dir den Startknoten und die Anzahl bereits besuchter Knoten. Wenn Du einen Knoten besuchst, dan prüfst Du einfach, ob das der Startknoten ist und ob Du alle Knoten besucht hast. Fertig.

[edit]
Ach ja, und die Gesamtentfernung berechnest Du aus der Summe der Einzelentfernungen. Man hat dafür eine 'Kosten' Funktion, hier die Entfernungen. Die Funktion Cost (a,b) liefert Dir die Entfernung zwischen a und b. Das ist einfacher, als für jeden Neighbor-Knoten die Entfernung im Node zu speichern, weil dann die Entfernungen doppelt gespeichert sind:
wenn a ein Nachbar von b ist , dann ist ja auch b ein nachbar von a...
[/edit]

[Minz]

Danke schonmal für die Antworten.

@alzaimer
Nicht dass ich jetzt davon viel verstanden hätte :gruebel: deswegen nochmal langsam für mich bitte :zwinker:

Du setzt vorraus, dass ich den Baum schon habe oder? Ähm wahrscheinlich hätte ich das Thema "Einen Baum erstellen" nennen sollen :mrgreen:

Theoretisch würde mir ja schon reichen eine Liste zu erstellen die sämtliche Zahlenkombinationen enthält:

(Zahlen entsprechen den Städten)
1 2 3 4 5
1 2 3 5 4
1 3 2 5 4
1 3 2 4 5
1 4 3 2 5
1 4 3 5 2
etc.

Wobei die 1 auch gespart werden kann, was Dizzy in seinem Post schon erwähnte, weil die Startstadt feststeht.

Ansonsten habe ich bei Google nur Uni-Seiten entdeckt, die mich als Nicht-Student zu knapp mit nachvollziehbaren Material versorgen :?: - Dijkstar-Algorithmus oder so zum Berechnen der kürzesten Strecke bei einem gegebenen Startpunkt, erfordert zunächst die Generierung eines kürzesten-Weg-Baums.
Viel zu kompliziert :mrgreen:

Wie gesagt, ein Zahlenfolgegenerator, der alle möglichen Zahlenfolgen enthält, wäre für mich genau das Richtige...weiß da jemand was?

[dizzy]

Dann brauchst du tatsächlich alle Permutationen deiner Zahlenmenge. (Das wären bei z.B. 15 Städten mit fester Startstadt aber schon 1.307.674.368.000 Kombinationen... Da wird's RAM knapp ;))

alzaimar hat im DF dieses hier gepostet. Das dürfte sich leicht auf Arrays umwandeln lassen. Die Funktion gibt die n-te Permutation einer Folge zurück. Du müsstest diese Funktion für die Folge [2, 3, 4, 5] also mit "aCount" von 1 bis 4! 4!-mal aufrufen um alle Varianten herauszubekommen. (Getestet hab ich diese Funktion nicht, aber alzaimar ist imho weit weniger hirnschwach als sein Name vermuten lässt :D.)

Nur scheitert dein gesamtes Vorhaben bei schon wenig mehr Städten, da sich das ganze fakultätisch verhält, und je auch noch eine Stadt mehr gespeichert werden muss (was bei der Menge an Sätzen die dazu kommen durchaus zu bedenken ist...). Ganz zu schweigen von der nötigen Zeit alle Kombinationen durchzutesten. Bis dahin hat dein Salesman sicherlich alles 10 Mal abgelatscht - egal mit welcher Route :zwinker:.


Gruss,
Fabian

[alzaimar]

Ein Graph ist definiert durch eine Menge von Knoten (Nodes) N, eine Menge von Kanten (Edges) E und eine Funktion Cost (n1,n2) (n1 und n2 sind Knoten) die angibt, wieviel ein Gang von n1 nach n2 kostet, wobei n1 und n2 durch eine Kante aus E verbunden sind...
Als Knoten kannst Du die Zahlen 1...N annehmen. Die Kanten und die Kosten sind als Entfernungsmatrix (1..N, 1..N) definiert.
Ein Weg der Länge X von a nach b wird dann einfach so abgebildet, das die Matrix [a,b] und [b,a] den Wert X enthält. Wenn man nicht von a nach b laufen kann, ist in der Entfernungsmatrix der Wert -1 (oder maxint) eingetragen.
Auf diese Weise kann man auch unterschiedliche Kosten a->b und b->a implementieren. Wenn b auf einem Berg liegt, ist a->b bestimmt teurer als b->a...

Stell Dir Ein Quadrat vor.

Code:

1---2
|\  |
| \ |
|  \|
3---4

Die Matrix sieht dann so aus:

Code:

----1  2  3  4
1|  - 10 10 14
2| 10  -  - 10 
3| 10  -  - 10
4| 14 10 10  -

10 ist die Entfernung (oder die Kosten), um von 1 nach 2, 2->4, 1->3 und 3->4 zu gelangen. 1-->4 ist hier etwas länger.

Bei Graphen mit vielen Knoten aber verhältnismäßig wenig Kanten ist diese Abbildung nicht optimal, genauergesagt Schrott.
Dann musst du Dir explizit für jeden Knoten die Kanten und die Kosten speichern, z.B. als Array [1..N] Of Array Of int:

Code:

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

Der Aufwand ist etwas größer, aber wesentlich schneller in der Verarbeitung.

Mein Tipp: Mal Dir mal einen kleinen Graphen mit so 5-7 Knoten auf und unterschiedlichen Entfernungen. Dann trommelst du das per 'Const' in ein Test-Programm und spielst damit rum...

Jetzt kannst Du mit einem rekursiven Algorithmus alle Kombinationen durchrechnen und die optimale Route ausgeben.

[w3seek]

Die Loesung fuer das Problem ist der weltbekannte Dijkstra Algorithmus, dieser wird sowohl bei Routenberechnungen als auch z.B. bei der Wegfindung durch Netzwerke (Internet) verwendet.

[alzaimar]

Nein, nicht ganz, weil Djikstra den "Single Pair Shortest Path" findet, wir aber das TSP implementieren wollen. Aber, in der Richtung sollte man weiter forschen, da hat du schon recht.

[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