Hallo erstmal!!

bin neu hier im Forum und wusste leider nicht genau,wo ich hinposten sollte!
naja...erstmal zu meinem Problem:

ich muss in der schule (gymnasium,stufe 13) in informatik mit delphi
ein programm schreiben,mit dem sich das travelling salesman problem lösen lässt!
leider habe ich keine ahnung,wie...

es wäre echt nett,wenn mir hier jemand helfen könnte,sei es mit
algorythmus,quelltext,seiten im netz,bücher usw usf

was ich leider nicht gebrauchen kann,sind lösungsansätze,die nur theoretisch sind...
ich brauch schon was mathematisches!!

es ist sehr dringend!!

mfG
Showtime

Hi,

ich weiß nicht, ob ich eine Bildungslücke hab, aber weiß irgendjemand hier, was das Traveling Salesman Problem eigentlich ist?

AXMD

Showtime hat folgendes geschrieben:

Hallo erstmal!! bin neu hier im Forum und wusste leider nicht genau,wo ich hinposten sollte! naja...erstmal zu meinem Problem:

Offtopic wäre angebrachter ...

Showtime hat folgendes geschrieben:

ich muss in der schule (gymnasium,stufe 13) in informatik mit delphi ein programm schreiben,mit dem sich das travelling salesman problem lösen lässt! leider habe ich keine ahnung,wie...

@TUFKAPL: Können wir mal eine Sparte "Hausaufgaben" anlegen???

Showtime hat folgendes geschrieben:

es wäre echt nett,wenn mir hier jemand helfen könnte,sei es mit algorythmus,quelltext,seiten im netz,bücher usw usf

Dieses Problem lässt sich durch die Kontaktierung unser aller Freund "GOOGLE" lösen!!!

Showtime hat folgendes geschrieben:

was ich leider nicht gebrauchen kann,sind lösungsansätze,die nur theoretisch sind... ich brauch schon was mathematisches!!

Gibt's genug im Netz ... man müsste nur mal den Vorschlag etwas weiter oben im Post berücksichtigen.

Showtime hat folgendes geschrieben:

es ist sehr dringend!!

Aber nicht so dringend, dass ich dir darauf eine Antwort geben muss!

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Das Travelling Salesman Problem ist auf der Suche nach dem kürzesten Weg durch eine Reihe von Punkten (für die Mathematiker: im zweidimensionalen Raum).

@Showtime
such doch mal nach
GENETISCHE PROGRAMMIERUNG TRAVEL SALESMAN

Zitat:

was ich leider nicht gebrauchen kann,sind lösungsansätze,die nur theoretisch sind... ich brauch schon was mathematisches!!

und mathematik ist wohl nicht theoretisch?

Zitat:

@TUFKAPL: Können wir mal eine Sparte "Hausaufgaben" anlegen???

ja, aber wenn, dann nicht kostenlos. soll ja auch irgendwas bringen. und von dem geld könnte man den server mit bezahlen.

mfg
GSE

Zitat:

und von dem geld könnte man den server mit bezahlen.

Die Idee klingt - ganz im Ernst - gut.

AXMD

.Chef hat folgendes geschrieben:

Das Travelling Salesman Problem ist auf der Suche nach dem kürzesten Weg durch eine Reihe von Punkten (für die Mathematiker: im zweidimensionalen Raum).

Spielt die Art des Raumes eine Rolle für den Algorithmus? Entscheidend sind eben die Abstände der Punkte zueinander, ob 2,3 oder 4D ist doch letztendlich egal.

Cu,
Udontknow

Natürlich kann der Raum auch n-dimensional sein. Das ursprüngliche TSP bezog sich aber auf die Ebene.

Ahso, ich war verwirrt, weil du "für Mathematiker:" geschrieben hattest...

.Chef hat folgendes geschrieben:

as Travelling Salesman Problem ist auf der Suche nach dem kürzesten Weg durch eine Reihe von Punkten (für die Mathematiker: im zweidimensionalen Raum)

Das ist nicht ganz richtig. Gegeben ist eine Menge von Punkten (Knoten) und eine Menge von Verbindungen zwischen diesen Knoten (Kanten), die eine gewisse Gewichtung (Länge) haben. Das müssen keine Puntkte in einem 2D-Raum sein. (Auch nicht in einem vernünftigen n-D-Raum. Dort hat man ja in der Regel eine Norm oder so. Bei TSP kann es sein, dass die Kanten A-B und B-C jeweils die Entfernung 5 haben, aber A-C hat die Entfernung 20) Dieses Gebilde aus Knoten und gewichteten Kanten nenn man gewichteter Graph. Das TSP Problem liegt darin, eine Rundreise über alle Knoten zu finden, so dass jeder Knoten genau einmal besucht wird, und man am Ende wieder am Ausgangsknoten ankommt.
TSP daher, weil Handlungsreisende gerne mal durch die Gegend reisen, umm ihre Priodukte anzupreisen. Dabei wollen sie natürlich jede Stadt nur einmal besuchen, und das möglichst kostengünstig (Länge der Kanten zwischen den Städten könnte sein: benötigte Fahrtzeit, Entfernung in km, Kosten für die Fahrt etc.)

Lösungsansatz im wesentlichen:
Da das TSP-Problem zu den NP-vollständigen Problemen gehört, ist es "nur schwer lösbar". Im wesentlichen muss man alle möglichen Rundreisen durchprobieren. Mit Hochleistungsrechnern ist das zur Zeit exakt mit ungefähr 125 Städten in vernünftiger Zeit lösbar. Alles andere sind Näherungsverfahren, aber das ist nicht Stoff für die Schule.

Ich vermute aber mal (im Hinblick auf eine ältere "Hausaufgabe"), dass mit TSP hier was anderes gemeint ist: Nämlich das kürzeste Wege Problem.
Gegeben hat man dabei einen Graphen, und zwei markierte Knoten (Städte). Gesucht ist der kürzeste Weg zwischen diesen beiden Städten. Das geht einfacher. Vielleciht beschreibst du mal das Problem, was der Lehrer euch gegeben hat. Oder hat der nur TSP gesagt?

Udontknow hat folgendes geschrieben:

Ahso, ich war verwirrt, weil du "für Mathematiker:" geschrieben hattest...

Ich wollte diese "Spezies" nur von vornherein direkt ansprechen, da derartige Aussagen im Gespräch mit Mathematikern sofort allgemein bewiesen werden müssen.

Ich kenne das TSP ursprünglich so, dass du einfach die Koordinaten x und y zu jedem Punkt hast, und dann die kürzeste Rundreise ausrechnest (ooookaaay, hätte ich oben anders ausdrücken können, aber ich bin nunmal nicht ao der große Redner).

Zur Gewichtung: Wie will man denn bitte für einzelne Verbindungen eine seperate Gewichtung speichern (für jede Verbindung!), wenn es bei 125 Punkten bereits rund 10^209 Verbindungen gibt?

.Chef hat folgendes geschrieben:

Udontknow hat folgendes geschrieben: Ahso, ich war verwirrt, weil du "für Mathematiker:" geschrieben hattest... Ich wollte diese "Spezies" nur von vornherein direkt ansprechen, da derartige Aussagen im Gespräch mit Mathematikern sofort allgemein bewiesen werden müssen.

Naja, mach doch auch Spaß ...

.Chef hat folgendes geschrieben:

Zur Gewichtung: Wie will man denn bitte für einzelne Verbindungen eine seperate Gewichtung speichern (für jede Verbindung!), wenn es bei 125 Punkten bereits rund 10^209 Verbindungen gibt?

Wieso??? Du musst nicht für jede Verbindung auch ein Gewicht haben. Wenn du an einer Kreuzung stehst, 7 verschiedene andere Kreuzungen in der Stadt kennst, kannst du von deiner jetzigen Ampel doch auch nicht jeden Punkt sofort erreichen ... d.h.: Der Speicheraufwand reduziert sich durch das Fehlen zahlreicher Verbindungsmöglichkeiten.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Seit wann gibts beim TSP Kreuzungen? Jeder Punkt ist direkt mit jedem anderen verbunden.

.Chef hat folgendes geschrieben:

Seit wann gibts beim TSP Kreuzungen? Jeder Punkt ist direkt mit jedem anderen verbunden.

War als Beispiel gedacht:
Jede Kreuzung ist ein Knoten, jede Straße zwischen den Kreuzungen eine Kante.
Und wenn du das so siehst, kommt das hin.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Wenn du zusätzlich zu den Direktverbindungen noch mit Knoten rechnest, wirds nur noch mehr Aufwand, von daher ist das egal.

Zitat:

Zur Gewichtung: Wie will man denn bitte für einzelne Verbindungen eine seperate Gewichtung speichern (für jede Verbindung!), wenn es bei 125 Punkten bereits rund 10^209 Verbindungen gibt?

Autsch. Autsch. Autsch.

Man hat 125 Punkte. Der erste ist mit 124 Punkten verbunden. Macht 124 Kanten.
Der zweite ist auch mit 124 Punkten verbunden. Eine Kante haben wir schon. macht also 123 Kanten. Für den dritten Knoten braucht man dann nur noch 122 Kanten usw. usf.

Um die Gesamtzahl der maximal möglichen Verbindungen bei n+1 Knoten auszurechnen, muss man also rechnen tun: n + n-1 + n-2 + n-3 + ... + 2 + 1.

Der kluge Gauß (nicht der Gausi) hat da mal ne Formel getan: n* (n+1)/2. Bei 125 wären das also 124*125/2 = 7750. Wenn man da jeweils einen Integer (4Byte) dran speichert, wären das 31000 Byte, das sind etwas weniger als 31KB. Das passt noch, oder?

Schei... stimmt! Ich bin noch voll bei Fakultät. Ich mach hier grad 'ne Berechnung für e, da kommt man schonmal durcheinander.

Aber mit dem Problem der Lösung der Hausaufgabe sind wir dadurch auch nicht weitergekommen. Mal gucken, wann showtime sagen kann, was der Lehrer mit dem TSP meint. Wenn er nämlich das kürzeste-Wege-Problem meint, dann kann ihm geholfen werden.
TSP mal eben als Hausaufgabe zu lösen, finde ich ein bissel happig. Und genetische Programmierung (Vorschlag Tilo) in der Schule...ich weiss nicht. Das ist AFAIK ein recht neues Forschungsgebiet. Wäre vielleicht eher was für ne Seminar-, Bachelor- oder Diplomarbeit...

Das mit genetischer Programmierung, habe ich nur anpesprochen, weil über das Thema viel mit TSP zu tun hat. Daher bin ich der Auffassung, das es dort Lösungsvorschläge und -verfahren gibt. Die Verwendung von genetischen Algorithmen ist grob jesagt gesteuerter Zufall.

Hier ein Link zu einer Seite zu gentischen Algorithmen, in der auch das TSP als Beispielprogramm in einem Download vorhanden ist. [edit] sein soll, hab die Seite nur Überfolgen, hatte aber das Ding schon mal Downgeloded und ausprobiert, sehr interessant und empfehlenswert[/edit]