Traveling salesman problem
Traveling Salesman-problemet (ofte kaldet TSP) er et klassisk algoritmisk problem inden for datalogi og operationsforskning. Det er fokuseret på optimering. I denne sammenhæng betyder en bedre løsning ofte en løsning, der er billigere, kortere eller hurtigere. TSP er et matematisk problem. Det udtrykkes lettest som en graf, der beskriver placeringen af et sæt knudepunkter.
Det rejsende sælgerproblem blev defineret i 1800-tallet af den irske matematiker W. R. Hamilton og den britiske matematiker Thomas Kirkman. Hamiltons Icosian Game var et fritidspuslespil, der var baseret på at finde en Hamilton-cyklus. Den generelle form af TSP synes først at være blevet undersøgt af matematikere i 1930'erne i Wien og på Harvard, især af Karl Menger. Menger definerer problemet, overvejer den indlysende brute-force-algoritme og konstaterer, at den nærmeste nabo heuristik ikke er optimal:
Vi betegner som messenger-problem (da dette spørgsmål i praksis skal løses af hvert enkelt postbud, men også af mange rejsende) opgaven med at finde den korteste rute, der forbinder punkterne, for fintligt mange punkter, hvis parvise afstande er kendt. Selvfølgelig kan dette problem løses ved endeligt mange forsøg. Regler, som ville presse antallet af forsøg ned under antallet af permutationer af de givne punkter, er ikke kendt. Reglen om, at man først skal gå fra startpunktet til det nærmeste punkt, derefter til det punkt, der ligger tættest på dette punkt osv. giver i almindelighed ikke den korteste rute.
Hassler Whitney fra Princeton University introducerede kort efter navnet traveling salesman problem.
En sælger ønsker at besøge alle byerne A, B, C og D. Hvad er den bedste måde at gøre dette på (billigste flybilletter og minimal rejsetid)?
Optimal rute for en sælger, der besøger de 15 største byer i Tyskland. Den viste rute er den korteste af de 43.589.145.600 mulige ruter.
William Rowan Hamilton
Angivelse af problemet
Problemet med den rejsende sælger beskriver en sælger, der skal rejse mellem N byer. I hvilken rækkefølge han gør det, er han ligeglad med, så længe han besøger hver by én gang i løbet af sin rejse og slutter der, hvor han var først. Hver by er forbundet med andre nærliggende byer, eller knudepunkter, med fly, vej eller jernbane. Hver af disse forbindelser mellem byerne har en eller flere vægte (eller omkostninger) tilknyttet. Omkostningerne beskriver, hvor "vanskeligt" det er at krydse denne kant i grafen, og kan f.eks. angives ved prisen på en flybillet eller en togbillet, eller måske ved længden af kanten eller den tid, der kræves for at gennemføre gennemkørslen. Sælgeren ønsker at holde både rejseomkostningerne og den tilbagelagte afstand så lav som muligt.
Traveling Salesman-problemet er typisk for en stor klasse af "svære" optimeringsproblemer, som har fascineret matematikere og dataloger i årevis. Det vigtigste er, at det har anvendelser inden for videnskab og teknik. Ved fremstillingen af et printkort er det f.eks. vigtigt at bestemme den bedste rækkefølge, i hvilken en laser skal bore tusindvis af huller. En effektiv løsning på dette problem reducerer produktionsomkostningerne for producenten.
Sværhedsgrad
Generelt er problemet med den omrejsende sælger svært at løse. Hvis der findes en måde at opdele problemet i mindre delproblemer, vil disse delproblemer være mindst lige så komplekse som det oprindelige problem. Det er det, som dataloger kalder NP-hårde problemer.
Mange mennesker har undersøgt dette problem. Den nemmeste (og dyreste løsning) er at prøve alle muligheder. Problemet med dette er, at man for N byer har (N-1) faktorielle muligheder. Det betyder, at der for kun 10 byer er over 180.000 kombinationer at prøve (da startbyen er defineret, kan der være permutationer på de resterende ni). Vi tæller kun halvdelen, da hver rute har en tilsvarende rute i omvendt retning med samme længde eller omkostninger. 9! / 2 = 181 440
- Der kan findes nøjagtige løsninger på problemet ved hjælp af branch and bound-algoritmer. Dette er i øjeblikket muligt for op til 85 900 byer.
- Heuristiske metoder anvender et sæt vejledende regler for valg af det næste knudepunkt. Men da heuristikker resulterer i tilnærmelser, vil de ikke altid give den optimale løsning, selv om tilladelige heuristikker af høj kvalitet kan finde en brugbar løsning på en brøkdel af den tid, der kræves til en fuldstændig brute force-analyse af problemet. Et eksempel på en heuristik for et knudepunkt kunne være en summering af, hvor mange ubesøgte knudepunkter der er "tæt på" et forbundet knudepunkt. Dette kunne tilskynde sælgeren til at besøge en gruppe af knuder i nærheden af hinanden, inden han går videre til en anden naturlig klynge i grafen. Se Monte Carlo-algoritmer og Las Vegas-algoritmer
Spørgsmål og svar
Spørgsmål: Hvad er det rejsende sælgerproblem?
A: Traveling Salesman Problem (TSP) er et klassisk algoritmisk problem inden for datalogi og operationsforskning. Det fokuserer på optimering, hvor bedre løsninger ofte betyder billigere, kortere eller hurtigere løsninger.
Spørgsmål: Hvordan udtrykkes TSP?
Svar: TSP udtrykkes lettest som en graf, der beskriver placeringen af et sæt knudepunkter.
Spørgsmål: Hvem definerede først TSP?
Svar: Traveling Salesman-problemet blev defineret i 1800-tallet af den irske matematiker W. R. Hamilton og af den britiske matematiker Thomas Kirkman.
Spørgsmål: Hvem undersøgte det yderligere i 1930'erne?
Svar: I 1930'erne studerede matematikerne Karl Menger i Wien og Harvard det yderligere.
Spørgsmål: Hvad introducerede Hassler Whitney kort efter?
Svar: Hassler Whitney på Princeton University introducerede navnet "traveling salesman problem" kort efter definitionen af det.
Spørgsmål: Hvad betyder "bedre løsning" i denne sammenhæng?
A: I denne sammenhæng betyder bedre løsning ofte en løsning, der er billigere, kortere eller hurtigere.
Spørgsmål: Hvilken algoritme blev af Menger betragtet som indlysende, da han studerede TSP?
Svar: Menger betragtede en indlysende brute-force-algoritme som indlysende, da han studerede TSP, og bemærkede, at brugen af nærmeste nabo heuristik ikke altid giver optimale resultater.
