Rechenaufwand beim Problem des Travelling Salesman

Wenn einfach nur alle Permutationen durchprobiert werden, liegt der Aufwand bei O(n!) (bzw. O((n-1)!) wenn berücksichtigt wird, daß es unerheblich ist, wo die Rundreise begonnen wird und somit der 1. Ort als Startort fest angenommen werden kann).

Das Branch-And-Bound-Verfahren hilft in der Praxis, den Aufwand zu reduzieren, kann dies jedoch nicht in jedem Fall garantieren.

Leider ist kein Algorithmus mit einer Komplexität von O(n^k) (mit festem k) für dieses Problem bekannt. Allerdings gibt es auch bislang keinen Nachweis, daß es einen solchen Algorithmus nicht geben könnte.

Somit ist dieses Problem heute z.B. für n = 100 nicht lösbar. Stattdessen gibt man sich dann mit relativ guten (aber nicht immer optimalen) Routen zufrieden.

Dieses Problem gehört zu einer Klasse von Problemen (sogenannte NP-vollständige Probleme), die diese Ungewißheit teilen und für die gilt, daß wenn eines davon in polynomialer Zeit lösbar ist, dann sind auch alle anderen davon in polynomialer Zeit lösbar.

	Wenn einfach nur alle Permutationen durchprobiert werden, liegt der Aufwand bei O(n!) (bzw. O((n-1)!) wenn berücksichtigt wird, daß es unerheblich ist, wo die Rundreise begonnen wird und somit der 1. Ort als Startort fest angenommen werden kann).
	Das Branch-And-Bound-Verfahren hilft in der Praxis, den Aufwand zu reduzieren, kann dies jedoch nicht in jedem Fall garantieren.
	Leider ist kein Algorithmus mit einer Komplexität von O(n^k) (mit festem k) für dieses Problem bekannt. Allerdings gibt es auch bislang keinen Nachweis, daß es einen solchen Algorithmus nicht geben könnte.
	Somit ist dieses Problem heute z.B. für n = 100 nicht lösbar. Stattdessen gibt man sich dann mit relativ guten (aber nicht immer optimalen) Routen zufrieden.
	Dieses Problem gehört zu einer Klasse von Problemen (sogenannte NP-vollständige Probleme), die diese Ungewißheit teilen und für die gilt, daß wenn eines davon in polynomialer Zeit lösbar ist, dann sind auch alle anderen davon in polynomialer Zeit lösbar.