/ en / Traditional / help

Beats Biblionetz - Begriffe

Traveling Salesman Problem Traveling Salesman Problem

iconSynonyme

Traveling Salesman Problem, Rundreiseproblem

iconDefinitionen

AlgorithmenZu 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
Gleichzeitige UngleichzeitigkeitenHier 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
(co-word occurance)		Knapsack-ProblemKnapsack-Problem(0.1), NP(0.06), P (PTIME)(0.05), NP-completeNP-complete(0.04)

iconHäufig co-zitierte Personen

Frege Frege

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

iconZitationsgraph

Diese Grafik ist nur im SVG-Format verfügbar. Dieses Format wird vom verwendeteten Browser offenbar nicht unterstützt.

Diese SVG-Grafik fensterfüllend anzeigen

iconZeitleiste

icon22 Erwä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.

Suchen im Biblionetz mit Google
Google Scholar
Google
Amazon

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.