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.