Handelsreizigersprobleem
Uit Wikipedia, de vrije encyclopedia
Het handelsreizigersprobleem is een van de bekendste problemen in de informatica en het operationele onderzoek. Het wordt vaak TSP genoemd, een afkorting van de Engelse benaming travelling salesman problem. Het kan als volgt worden geformuleerd:
Gegeven steden samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die een keer langs iedere stad komt en eindigt bij de eerste stad.[1]
Het probleem is een onderdeel van de grafentheorie.
Formeel is de invoer van het probleem een volledige, gewogen graaf. De oplossing van het probleem is een pad door de graaf dat iedere knoop precies één keer aandoet, begint en eindigt in dezelfde knoop, en een minimale totale lengte heeft. De eis dat elke knoop precies één keer doorlopen wordt, zorgt ervoor dat elke rondreis hetzelfde aantal stappen bevat, wat mogelijk is omdat de invoer een volledige graaf is, waarin elke knoop in één stap vanuit elke andere knoop bereikt kan worden. Elke samenhangende graaf kan volledig worden gemaakt door een (gewogen) transitieve afsluiting uit te voeren.