Wir werden uns zwei allgemeine Techniken ansehen, die auf das Problem des Handlungsreisenden angewendet werden. Die erste, Branch and Bound, ist ein klassischer Ansatz in der kombinatorischen Optimierung, der für verschiedene Probleme verwendet wird. Sie kann als eine Verbesserung der Brute-Force-Suche angesehen werden: Wir versuchen, eine Permutation Stück für Stück zu konstruieren, aber bei jedem Schritt prüfen wir, ob es noch sinnvoll ist, die Permutation weiter zu konstruieren (wenn nicht, schneiden wir den aktuellen Zweig einfach ab). Die zweite Methode, die dynamische Programmierung, ist wohl die beliebteste algorithmische Technik. Sie löst ein Problem, indem sie eine Sammlung kleinerer Teilprobleme durchläuft.

Wie wir in den vorangegangenen Modulen gesehen haben, ist es schwierig, das Problem des Handelsreisenden genau zu lösen. Tatsächlich erwarten wir nicht einmal in naher Zukunft eine effiziente Lösung. Aus diesem Grund ist es sinnvoll zu fragen: Ist es möglich, effizient eine Lösung zu finden, die wahrscheinlich suboptimal ist, aber gleichzeitig nahe am Optimum liegt? Es stellt sich heraus, dass die Antwort ja lautet! Wir werden zwei Algorithmen kennenlernen. Der erste garantiert, dass er schnell eine Lösung findet, die höchstens doppelt so lang ist wie die optimale Lösung. Der zweite Algorithmus hat keine solche Garantie, aber es ist bekannt, dass er in der Praxis recht gut funktioniert.