/ en / Traditional / mobile

Beats Biblionetz - Begriffe

Traveling Salesman ProblemTraveling Salesman Problem

Diese Seite wurde seit mehr als 7 Monaten inhaltlich nicht mehr aktualisiert. Unter Umständen ist sie nicht mehr aktuell.

iconSynonyme

Traveling Salesman Problem, Rundreiseproblem

iconDefinitionen

Zu einer gegebenen Menge von Städten und Entfernungen zwischen allen Paaren von Städten ist eine Tour durch alle Städte zu finden, deren Länge kleiner als M ist.
Von Robert Sedgewick im Buch Algorithmen (1983) auf Seite 721
Roger PenroseEin weiteres NP-vollständiges Problem ist das "Problem des Handlungsreisenden"; es ähnelt dem Problem des Hamiltonschen Kreises, nur weist man den verschiedenen Kanten Zahlenwerte zu und sucht denjenigen Hamiltonschen Kreis, für den die Summe der Zahlen (die vom Handlungsreisenden zurückgelegte "Entfernung") ein Minimum ist. (Genaugenommen benötigen wir hier eine Ja/Nein-Version wie: Gibt es für das Problem des Handlungsreisenden einen Weg, dessen Länge kleiner ist als ein bestimmter Wert?)
Von Roger Penrose im Buch Computerdenken (1989) im Text Wahrheit, Beweis und Erkenntnis
Hier besteht die Schwierigkeit darin, die kürzeste Route durch eine Anzahl von Städten zu finden, bei der keine Stadt zweimal besucht und also kein Wegabschnitt wiederholt werden soll. Aufgrund der vielfältigen Kombinierbarkeit der Wegabschnitte generieren bereits relativ wenige Städte einen enormen Möglichkeitsraum. Während 5 Städte nur 12 unterschiedliche Routen erlauben, ermöglichen 10 Städte bereits 181 440 und 15 Städte schon über 43.5 Milliarden. Bei Größenordnungen von 200 Städten und mehr wird das Problem auf direktem Weg praktisch unlösbar, obwohl auch hier sämtliche beteiligten Größen nach wie vor nur endlicher Natur sind. Aktuell verfügbare Rechner würden Jahrtausende mit dem stupiden Durchprobieren sämtlicher Reiserouten beschäftigt sein.
Von Manfred Füllsack im Buch Gleichzeitige Ungleichzeitigkeiten (2011) im Text Entwicklungen

iconBemerkungen

David HarelAufgrund der NP-Vollständigkeit ist das Problem des Handlungsreisenden also in der Praxis nicht lösbar - zumindest bei unserem derzeitigen Wissensstand nicht.
Von David Harel im Buch Das Affenpuzzle (2000) im Text Manchmal wissen wir es nicht auf Seite 95
David HarelDas Problem des Handlungsreisenden ist zwar lösbar, doch die bekannten Algorithmen dafür sind nutzlos langsam (der naheliegendste durchläuft einfach sämtliche Routen; bei N Städten sind dies ungefähr N\ viele). Selbst die besten Algorithmen für das Problem des Handlungsreisenden sind so schlecht, daß sie im ungünstigsten Fall bereits bei Karten mit 150 oder 200 Städten hoffnungslos langsam sind. Und während 150 Städte für einen wirklichen Handlungsreisenden (oder eine Handlungsreisende) mit einem Koffer voller Kleinteile zwar nach einer großen Zahl klingen mag, ist sie für einige Anwendungen des Problems äußerst bescheiden.
Von David Harel im Buch Das Affenpuzzle (2000) im Text Manchmal wissen wir es nicht auf Seite 95

iconVerwandte Objeke

icon
Verwandte Begriffe
(Cozitation)
Knapsack-ProblemKnapsack-Problem, NP, P (PTIME), Optimierung, NP-completeNP-complete

iconHäufig co-zitierte Personen

Frege Frege
David Hilbert David
Hilbert

iconStatistisches Begriffsnetz Dies ist eine graphische Darstellung derjenigen Begriffe, die häufig gleichzeitig mit dem Hauptbegriff erwähnt werden (Cozitation).

Diese Grafik fensterfüllend anzeigen als Pixelgrafik (PNG) Vektorgrafik (SVG)

iconZitationsgraph

Diese Grafik fensterfüllend anzeigen als Pixelgrafik (PNG) Vektorgrafik (SVG)

iconErwähnungen Dies ist eine nach Erscheinungsjahr geordnete Liste aller im Biblionetz vorhandenen Werke, die das ausgewählte Thema behandeln.

iconAnderswo suchen Auch im Biblionetz finden Sie nicht alles. Aus diesem Grund bietet das Biblionetz bereits ausgefüllte Suchformulare für verschiedene Suchdienste an. Biblionetztreffer werden dabei ausgeschlossen.

iconBiblionetz-History Dies ist eine graphische Darstellung, wann wie viele Verweise von und zu diesem Objekt ins Biblionetz eingetragen wurden und wie oft die Seite abgerufen wurde.

Verweise auf Traveling Salesman Problem 203334236114533
Webzugriffe auf Traveling Salesman Problem 
20042005200620072008200920102011201220132014201520162017