Lineare Optimierung beim TSP

[3_of_8]

Es ist noch nicht bewiesen, aber es wird vermutet, dass TSP NP-schwer ist und dass es deshalb eine exponentielle Laufzeitkomplexität hat. Du hast n! Möglichkeiten, deine Route zu wählen, und du musst alle durchprobieren und n! verhält sich asymptotisch wie sqrt(n)*n^n.

Also ich denke mal, deine untere und obere Schranke dafür, wie das ganze skaliert, ist sqrt(n)*n^n. Außer vielleicht in Sonderfällen, du könntest zum Beispiel erstmal schauen, wie die Kostenverteilung (also die Entfernung) ist und wenn sie überall gleich ist, sind alle Lösungen gleichwertig, wodurch du einen Algorithmus hast, der für n skaliert - aber Sonderfälle bei einer Laufzeitbetrachtung heranzuziehen ist eher ungewöhnlich. Bei einer Sortierung hat man sonst auch eine untere Grenze von O(n), wenn die Folge schon sortiert ist.