11
Travelling Salesman Problem
Problem des Handlungsreisenden
TSP
n-Städte
-kürzeste Strecke
-jede Stadt genau einmal
-anschließend wieder an Ausgangstadt
-> Kombinatorische Optimierungsproblem
TSP
1: A-B-C-D-A
2: A-C-B-D-A
3: A-B-D-C-A
4: A-D-C-B-A
5: A-D-B-C-A
6: A-C-D-B-A
S(n) = (n-1)!/2
(n-1)!
Problematik
Problematik
d.h. das Lösen kann nicht polynomial sondern höchstens exponential erfolgen
(z. B. Simulated Annealing, Tabu Search)
Klassifizierung
Klassifikation
P
-effizienter (in Polynomialzeit lösbarer) Lösungsweg existiert
-"praktisch lösbar"
P
NP
-Lösungsweg unbekannt
-Komplexe Probleme
-konkrete Lösungen können sehr effizient und schnell überprüft werden
- die sich nichtdeterministisch (nicht in der Polynomialzeit) lösen lassen
NP
TSP
Schaltkreis Design(SAT)
Mitarbeiter Zeitpläne
Alltagsbeispiele
-Genetischer Algorithmus (TSP)
-logistische Probleme
Alltagsbsp.
Quellen
https://www.youtube.com/watch?v=3GAfjE_ChR
https://stackoverflow.com/questions/10371317/what-are-real-world-industry-applications-of-tspI
http://www.wirtschaftslexikon24.com/d/traveling-salesman-problem/traveling-salesman-problem.htm
https://brilliant.org/wiki/sorting-algorithms/
https://de.wikipedia.org/wiki/NP-Vollst%C3%A4ndigkeit
https://de.wikipedia.org/wiki/P-NP-Problem#NP