Welke technieken zijn er om de kortste route te vinden bij een handelsreizigersprobleem?

Het handelsreizigersprobleem is een bekend probleem uit de complexiteitstheorie. De formulering is eenvoudig: vind de kortste route om alle gegeven plaatsen één keer te bezoeken.
De oplossing is echter verre van eenvoudig. Het is een NP-moeilijk probleem, hetgeen (kort en misschien niet strikt genoeg geformuleerd) betekent dat er geen wezenlijk snellere oplossingsmethode bestaat dan alle mogelijkheden één voor één proberen.
Je kunt natuurlijk wel wat winst behalen door routes waar je echt van het ene eind naar het andere springt en weer terug uit te sluiten. Je vindt al snel routes die redelijk in de buurt van het ideaal liggen. Maar wat is echt de kortste? En hoe toon je dat aan?
Ik kan me voorstellen dat je voor een opdracht een voorbeeld verzint met 6 tot 8 steden en dan laat zien dat één route van alle mogelijke de kortste is. Dat kan nog net door alles uit te schrijven zonder computer. Maar bij grotere aantallen wordt het algauw onbegonnen werk. Zet er een opmerking bij dat er geen wezenlijk snellere methode bestaat om dit aan te pakken dan zul je vast goed scoren.