Het Traveling Salesman probleem betreft het vinden van de kortste rondrit (tour) langs een aantal plaatsen of punten, waarbij tussen elk tweetal plaatsen de onderlinge afstand gegeven is. Dit probleem komt veel voor, in verschillende gedaantes, en is niet alleen voor een handelsreiziger of pizzabezorger van belang: het is praktisch en zeer relevant. Helaas heeft dit probleem geen efficiënte oplossing; in veel praktische gevallen wordt volstaan met een benadering die op een redelijk efficiënte manier een oplossing bepaalt die niet te ver van de optimale oplossing afwijkt.
De eenvoudige "brute force" oplossing van dit probleem bestaat uit het proberen van alle mogelijke routes langs de genoemde punten; in het geval van N punten betreft dit N! mogelijkheden. Zoals we uit de onderstaande tabel voor N! zien, loopt dit aantal mogelijkheden snel uit de hand.
Er is zeer veel literatuur over dit probleem te vinden, ook op het web. Enkele verwijzingen:
Als opstapje voor een brute-kracht algoritme voor het Traveling Salesman problem behandelen we eerst een algoritme om alle permutaties van een rij te bepalen.
We maken gebruik van een recursieve benadering:
Door herhaald toepassen van de tweede stap komen we uiteindelijk bij een rij ter lengte 1, met een triviale oplossing.
In het uitwerken van dit principe in de programmeertaal Python maken we gebruik van een variabele seq: een rij (lijst) van getallen: seq[0], seq[1], ... ; de functie perm (i) bepaalt alle permutaties van seq[i, i+1, ...]. Als i gelijk is aan de positie van het laatste element van de rij (ofwel, i==len(seq)-1), dan hebben we te maken met een rij van lengte 1, met de triviale oplossing. De stap
seq[i], seq[j] = seq [j], seq[i]
wisselt de elementen seq[i] en seq[j] om, waardoor de oorspronkelijke seq[j] nu kop-element wordt. Dit moeten we na het bepalen van alle permutaties van de rest-rij nogmaals doen, om de rij seq weer in de oorspronkelijke volgorde terug te zetten.
def perm (i):
if i==len(seq)-1:
print "sec=", seq
else:
for j in range (i, len(seq)):
seq[i], seq[j] = seq [j], seq[i]
perm (i+1)
seq[i], seq[j] = seq [j], seq[i]
We proberen nu het Traveling Salesman problem op te lossen door alle mogelijke routes te proberen. Uitgangspunt voor deze oplossing is het algoritme voor het bepalen van alle permutaties, zoals hierboven beschreven. Als we een permutatie bepaald hebben, moeten we de kosten van de bijbehorende tour bepalen. De basis daarvoor is de kostenfunctie, cost (i,j), die de kosten van de reis van punt i naar punt j weergeeft. In het voorbeeld maakt deze kostenfunctie gebruik van een afstandentabel, scost, die de afstand van i naar j weergeeft; in dit voorbeeld zijn de afstanden symmetrisch, wat betekent dat we maar de helft van de tabel hoeven op te slaan. In de kostenfunctie cost zorgen we ervoor dat we altijd de juiste elementen van deze tabel gebruiken.
De kosten van een tour gegeven door een rij punten s bepalen we door de kosten van alle samenstellende paden (s[i-1], s[i]) op te tellen; hiervoor gebruiken we de functie tourcost. We moeten de kosten van de totale rondrit bepalen, inclusief de afstand van eindpunt terug naar het begin; voor dit laatste maken we gebruik van een handigheid in Python: s[-1] is het laatste element van een rij, en s[0] het eerste element. cost([s-1],s[0]) geeft dan de kosten van de verbinding van het laatste naar het eerste element.
Het algoritme is in principe ontworpen voor asymmetrische afstanden, hoewel we in dit voorbeeld te maken hebben met een symmetrische kostenfunctie.
Opgave: hoeveel rekenwerk kunnen we mogelijk besparen als we er van uitgaan dat de kostenfunctie symmetrisch is?
Opgave: als we bij het oorspronkelijke Traveling Salesman probleem willen blijven, hoeven we alleen maar de routes te beschouwen die met punt 0 beginnen. Hoeveel rekenwerk kunnen we daarmee besparen? Hoeveel groter kan het probleem daarmee worden, met dezelfde hoerveelheid rekenwerk als oorspronkelijk?
Over "complexiteit". Wat opvalt aan dit algoritme is dat het algoritme zelf eenvoudig is - maar dat de hoeveelheid rekenwerk enorm snel toeneemt. Dit illustreert heel duidelijk dat er geen relatie is tussen de conceptuele eenvoud van een algoritme, en de hoeveelheid rekenwerk. Een algoritme waarvan de hoeveelheid rekenwerk snel toeneemt met de omvang van het probleem (bij het Traveling Salesman problem, het aantal plaatsen), heet een algoritme met een grote rekenkundige complexiteit. Dit zegt dus niets over de eenvoud van het algoritme!