Traveling Salesman Problem Antwort



Richtig!

Sie haben richtig geschätzt!

Es gibt genau 10 461 394 944 000 Möglichkeiten, das sind rund 10 Billionen Möglichkeiten.
Selbst für einen Rechner der 1000 Möglichkeiten in der Sekunde berechnen und vergleichen könnte, würde das eine Aufgabe für rund 300 Jahre darstellen. Und das sind lediglich 17 Knoten. Wieviele Knoten hat ein Telefonnetzwerk oder ein integrierter Schaltkreis? Es ist wohl leicht einzusehen, daß der Aufwand, alle Lösungen zu finden und miteinander zu vergleichen unpraktikabel wird.


Einführung Homepage TSP und NPC

Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996