Auch ein Hobby: S-Bahn fahren

#1 von Socke , 21.02.2015 21:52

Auf was Mathematik-Studenten aber auch so alles kommen: Die kürzeste Route in einem S-Bahnnetz, um alle Stationen anzufahren.

http://www.morgenpost.de/berlin-aktuell/...Stunden-ab.html


 
Socke
Beiträge: 11.391
Registriert am: 08.06.2014

zuletzt bearbeitet 21.02.2015 | Top

RE: Auch ein Hobby: S-Bahn fahren

#2 von Jimbo , 22.02.2015 13:10

TSP - Travelling Salesman Problem. Eine altbekannte Aufgabe, die heutzutage am besten mit einem genetischen Algorithmus zu lösen ist. Genetische Algorithmen wurden erstmals in der Nachkriegszeit bekannt und haben erst seit den 70er und 80er Jahren Eingang in die Lösung praktischer Probleme erhalten. Genetische Algorithmen lösen Aufgaben, die zuvor als unlösbar oder nur mit riesigem Rechenaufwand als lösbar galten. Das Schöne an genetischen Algorithmen ist, dass sie schon sehr bald eine tatsächlich gangbare Lösung liefern, nicht unbedingt die optimale, aber ein Lösung, die zum Ziel führt. Um bessere Lösungen zu erhalten, muss man nur weiterrechnen lassen, irgendwann gibts keine besseren Lösungen mehr, dann hat man quasi optimiert. Optimierungslösungen auf Basis von Matrizen ('Lineare Optimierung') zielen nur auf das optimale Ergebnis (einen der Eckpunkte einer multidimensionalen Fläche) und können zuvor nicht abgebrochen werden, man lässt einenComputer daran oft tagelang rechnen, obwohl ein, wenn auch durchaus suboptiomales Ergebnis bereits nach wenigen Minuten nötig wäre, zB das übliche Fabriksteuerungsproblem.


All good deeds shall be punished

 
Jimbo
Beiträge: 5.153
Registriert am: 09.06.2014


RE: Auch ein Hobby: S-Bahn fahren

#3 von Arschministrator , 22.02.2015 22:45

schön. danke für die zusammenfaselung.

nein, spaß beiseite, hast du sehr anschaulich und einprägsam dargestellt.

es gibt jede menge software, die genau diese thematik für unternehmen mit großem außendienst bzw. werksverkehr löst.

in der praxis habe ich in stark abgeschwächter form bei ebay-abholfahrten ein ähnliches thema zu beantworten. da es aber meistens nur um maximal vier abholpunkte geht, ergibt sich die lösung bei einem blick auf die karte meist von alleine.


 
Arschministrator
Beiträge: 1.550
Registriert am: 07.06.2014


   

Karriere: Ein Ingenieur wird Hotelier
Als Jude nur nicht auffallen!

Xobor Einfach ein eigenes Xobor Forum erstellen