Beats Biblionetz - Begriffe: Traveling Salesman Problem

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

Ein 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

Bemerkungen zum Begriff "Traveling Salesman Problem"

Aufgrund 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

Das 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

Der Begriff "Traveling Salesman Problem" ist verwandt mit:

Personen, die diesen Begriff am meisten verwenden (beta)

Personen, die am häufigsten zusammen mit diesen Begriff erwähnt werden (beta)

Statistisches Begriffsnetz zum Begriff "Traveling Salesman Problem" (Cozitationen) Dies ist eine graphische Darstellung derjenigen Begriffe, die häufig gleichzeitig mit dem Hauptbegriff erwähnt werden (Cozitation).

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

Der Begriff "Traveling Salesman Problem" wird besprochen in (Zitationen): Dies ist eine graphische Darstellung aller im Biblionetz vorhandenen Werke und ihre Verknüpfungen untereinander, die das ausgewählte Thema behandeln.

Dies ist eine graphische Darstellung aller im Biblionetz vorhandenen Werke und ihre Verknüpfungen untereinander, die das ausgewählte Thema behandeln.

Der Begriff "Traveling Salesman Problem" wird besprochen in (Zitationen): Dies ist eine nach Erscheinungsjahr geordnete Liste aller im Biblionetz vorhandenen Werke, die das ausgewählte Thema behandeln.

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

Algorithmen (Robert Sedgewick) (1983)
Computerdenken (Roger Penrose) (1989)
- 4. Wahrheit, Beweis und Erkenntnis
Mathematische Optimierung - Das Sintflutprinzip (Gunter Dueck, Tobias Scheuer ) (1994)
Das Affenpuzzle (David Harel) (2000)
- 1. Worum geht es überhaupt?
- 4. Manchmal wissen wir es nicht
Wild Duck (Gunter Dueck) (2000)
- 9. Der nicht aufzuhaltende Aufstieg
Studium generale zur Komplexität (Hans Diebner) (2001)
- 8. Realität, Aktualität, Ästhetik und Interpretation (Hans Diebner, Peter Weibel )
A New Kind of Science (Stephen Wolfram) (2002)
Mapping Scientific Frontiers (Chaomei Chen) (2003)
- 3. Mapping the Mind
- 4. Enabling Techniques for Science Mapping
LOG IN 127/2004 (2004)
- Werkstatt: Genetische Algorithmen (Alfred Hermes) (2004)
LOG IN 128/129/2004 (2004)
- Werkstatt: Genetische Algorithmen Teil 4 (Alfred Hermes) (2004)
Das Sintflutprinzip (Gunter Dueck) (2004)
- 2. Das Beste oder Höchste, was ist das genau?
GraphBench - Exploring the Limits of Complexity with Educational Software (ETH Dissertation 16392) (Markus Brändle) (2006)

Kommentare von BesucherInnen zum Begriff "Traveling Salesman Problem" Hier können auch Sie Ihren Kommentar anbringen!

Externe Links zum Begriff "Traveling Salesman Problem" Verweise auf Informationen ausserhalb des Biblionetzes

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