Handelsreizigersprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Kortste route die de 15 grootste steden van Duitsland aandoet

Het handelsreizigersprobleem is een van de bekendste problemen in de informatica en het operationele onderzoek. Het wordt vaak van het Engelse travelling salesperson problem afgekort tot TSP. Het kan als volgt worden geformuleerd:

Aanhalingsteken openen

Gegeven steden samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die precies één keer langs iedere stad komt.

Aanhalingsteken sluiten

Het probleem is een onderdeel van de grafentheorie. Het algoritme dat de berekening uitvoert om deze weg te vinden wordt bijvoorbeeld bij het etsen van printplaten gebruikt. De rechtstreekse manier om dit op te lossen is alle mogelijke routes na te gaan en ze te vergelijken, maar aangezien het aantal combinaties bedraagt wordt dit snel onmogelijk voor meer dan ca. 25 steden. Er bestaan wel efficiënte algoritmes die een goede oplossing geven, maar waarvan 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 computertijdequivalent op een enkele Alpha-processor van 500 MHz. Maar de berekeningen werden op een netwerk van 110 processors uitgevoerd.[1] In mei 2004 is de oplossing voor het handelsreizigersprobleem met een afstand van ongeveer 72.500 km[2] gevonden voor de 24.978 plaatsen in Zweden.

Het handelsreizigersprobleem is NP-moeilijk. De beslissingsvariant van het probleem (gegeven de onderlinge afstanden tussen de steden, bestaat er een oplossing die korter is dan een gegeven maximum afstand?) is NP-volledig.

Het probleem lijkt op het Chinese postbodeprobleem. Bij het handelsreizigersprobleem moeten echter alle plaatsen één keer worden aangedaan, terwijl bij het Chinese postbodeprobleem alle wegen tussen de verschillende plaatsen moeten zijn gebruikt. Het Chinese postbodeprobleem is niet NP-moeilijk.