Handelsreizigersprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het handelsreizigersprobleem (TSP, travelling salesman problem) is een van de bekendste problemen in de computerwetenschap en operationeel onderzoek. Het kan als volgt worden geformuleerd:

Als er n steden gegeven zijn die een handelsreiziger moet bezoeken, samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die kan worden gebruikt, waarbij iedere stad wordt bezocht.

Het probleem is een onderdeel van de grafentheorie.

Van het probleem is aangetoond dat het NP-moeilijk is en de formulering in beslisbaarheidsvorm ("Gegeven de afstanden en een totale afstand x, beslis of er een oplossing is die korter is dan x") is NP-volledig.

De rechtstreekse manier om dit op te lossen is alle mogelijke routes na te gaan en ze te vergelijken, maar aangezien het aantal combinaties n! bedraagt (n faculteit = n × (n-1) × (n-2) × ... × 2 × 1) wordt dit snel onmogelijk voor meer dan ca. 25 steden. Er bestaan wel efficiënte algoritmes die een goede oplossing geven, waarvan echter niet met zekerheid bekend is of deze de beste is.

In 1998 berekenden wiskundigen van de Universiteit van Princeton de exacte oplossing voor 15.112 steden in Duitsland. De oplossing kostte 22,6 jaar computertijd en de berekeningen werden op een netwerk van 110 processors uitgevoerd.[1] In mei 2004 is de oplossing voor het handelsreizigersprobleem gevonden voor alle plaatsen in Zweden, een totaal van 24.978. De afstand bedraagt ongeveer 72.500 kilometer.[2]

Het probleem is niet alleen academisch; het heeft talloze directe toepassingen in de praktijk, van het aanleggen van kabelnetten tot het bepalen van de route van de boorkop bij het boren van gaatjes in printplaten.

Zie ook[bewerken]

Externe link[bewerken]

Bronnen, noten en/of referenties