Entwickler-Ecke :: Thema anzeigen - Travelling Salesman Problem

Showtime - So 03.10.04 20:25
Titel: Travelling Salesman Problem - Schule

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

BenBE - So 03.10.04 20:47
Titel: Re: Travelling Salesman Problem - Schule

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!

GSE - So 03.10.04 23:14

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? :wink:

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. :wink:

mfg
GSE

Udontknow - Mo 04.10.04 09:57

.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

Gausi - Mo 04.10.04 10:06

.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?

.Chef - Mo 04.10.04 10:30

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. :D

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?

BenBE - Mo 04.10.04 10:42

.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. :D

Naja, mach doch auch Spaß ... :lupe:

.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.

Gausi - Mo 04.10.04 11:00

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?

Gausi - Mo 04.10.04 11:07

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...

Tilo - Mo 04.10.04 14:09

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 [http://www.fh-augsburg.de/informatik/projekte/mebib/emiel/entw_inf/genetische_algorithmen.html] 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]

Showtime - Mo 04.10.04 17:36

hallo!

geht ja echt schnell mit euch...!! großes dankeschön schonmal...!!

erstma@Gausi:
hab ja nie gesagt,dass es ne hausaufgabe is...das hat BenBE (indirekt) gesagt!
es is mehr 'n projekt...haben da mehrere wochen für zeit
und ja,es ist das kürzeste-Wege-Problem!

ich weiß ja auch schon ne menge darüber,u.a. welche lösungsarten es gibt...
z.b. branch & cut,kleinster aufspannender baum
das prinzip dieser lösungswege habe ich ja verstanden,ich
weiß halt nur nich,wie man es in delphi programmiert...

und hierbei brauche ich eure hilfe ^^

ps: ich schau mir grad den link von tilo an...vllt is ja was dabei! =D

Gausi - Mo 04.10.04 19:19

ok, dann für ein Projekt.

Branch&cut sagt mir jetzt nix, aber kleinster spannender Baum hat AFAIK nichts mit dem kürzesten Wege-Problem zu tun. Beim MinimalenSpannBaum möchte man erreichen, dass alle Knoten zwar miteinander verbunden sind, aber es keine "Kreise" in dem verbleibenden Graphen gibt. Die Kantensumme in dem Baum soll dabei minimal sein.

Für kürzesteWege würde ich mal nach Dijkstras Algorithmus suchen. Der ist dafür genau das richtige.

Zur Implementierung in Delphi: Das Hauptproblem ist dabei die Verwaltung des Graphen. Du mußt dir eine Datenstruktur TGraph erstellen, in der Knoten und Kanten gespeichert sind. Dabei hat eine Kante einen Start- und einen End-Knoten, sowie eine gewisse Länge. Außerdem benötigst du an den Objekten Kante und Knoten diverse Flags/Markierungen. Stichworte für die Darstellung des Graphen sind dann Adjazenzliste oder Adjazenzmatrix, wobei man die Listenstruktur auch implementieren muss (oder man nimmt TList oder so)

Oder hast du schon die Datenstruktur Graph implementiert? Dann fällt ein Großteil der Arbeit nämlich weg...

Aber ein Kommentar noch: Finden die Lehrer es eigentlich cool, wenn man das einfache "kürzeste Wege Problem" mit Traveling Salesman bezeichnet? Kannst ja mal danach fragen...

Showtime - Mo 11.10.04 13:35

jo danke!!
ihr habt mir schon sehr weitergeholfen!!
das TSP und was damit zusammenhängt hab ich ja schon verstanden...
das blöde is nur...mit dem programmiern hab ichs nich so :?
wisst ihr vllt,wo es tutorials oder hilfen (vllt auch quelltexte...muss aber nicht sein)
gibt,wie man sich bei delphi zufällige punkte generieren lässt?

thx im vorraus!
bis dann
Showtime

Showtime - Mo 11.10.04 13:35

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!