|
Seite 13 von 77 |
Wenn nicht der günstigste Weg zwischen zwei Knoten gesucht wird, wie beim eigentlichen TSP, sondern der günstigste Weg, der durch N Knoten geht, wird die benötigte Rechenzeit sogar proportional zu 2N.
Das bedeutet, dass nur bei einem kleinen Wert für N das Problem noch eindeutig in adäquater Zeit lösbar ist. Bei hohem N steigt die Rechenzeit sehr schnell an. Dieser extreme Anstieg lässt kaum darauf hoffen, dass zukünftige Verbesserungen der Computer-Rechenleistung ausreichen, um wesentlich höhere Werte für N bei vertretbarem Rechenaufwand bearbeiten zu können.
