Handelsresandeproblemet
Traveling Salesman Problem (ofta kallat TSP) är ett klassiskt algoritmiskt problem inom datavetenskap och operationsforskning. Det är inriktat på optimering. I det här sammanhanget betyder bättre lösning ofta en lösning som är billigare, kortare eller snabbare. TSP är ett matematiskt problem. Det uttrycks lättast som en graf som beskriver platserna för en uppsättning noder.
Problemet med den resande säljaren definierades på 1800-talet av den irländska matematikern W. R. Hamilton och den brittiska matematikern Thomas Kirkman. Hamiltons Icosian Game var ett fritidspussel som byggde på att hitta en Hamiltons cykel. Den allmänna formen av TSP verkar ha studerats för första gången av matematiker under 1930-talet i Wien och på Harvard, särskilt av Karl Menger. Menger definierar problemet, överväger den uppenbara brutala algoritmen och observerar att den närmaste granne-heuristiken inte är optimal:
Vi betecknar budbärarproblemet (eftersom denna fråga i praktiken bör lösas av varje brevbärare, men också av många resenärer) som en uppgift att för finantilt många punkter vars parvisa avstånd är kända, hitta den kortaste vägen som förbinder dessa punkter. Naturligtvis kan detta problem lösas genom ändligt många försök. Regler som skulle få antalet försök att understiga antalet permutationer av de givna punkterna är inte kända. Regeln att man först ska gå från startpunkten till den närmaste punkten, sedan till den punkt som ligger närmast denna punkt osv. ger i allmänhet inte den kortaste vägen.
Hassler Whitney vid Princeton University introducerade kort därefter namnet "traveling salesman problem".
En försäljare vill besöka alla städerna A, B, C och D. Vilket är det bästa sättet att göra detta (billigaste flygbiljetter och minsta möjliga restid)?
Optimal rutt för en försäljare som besöker de 15 största städerna i Tyskland. Den visade rutten är den kortaste av de 43 589 145 600 möjliga rutterna.
William Rowan Hamilton
Problemet är tydligt formulerat.
Problemet med den resande försäljaren beskriver en försäljare som måste resa mellan N städer. Han bryr sig inte om i vilken ordning han gör det, så länge han besöker varje stad en gång under resan och slutar där han var i början. Varje stad är förbunden med andra närliggande städer, eller noder, med flyg, väg eller järnväg. Varje länk mellan städerna har en eller flera vikter (eller kostnader). Kostnaden beskriver hur "svårt" det är att korsa denna kant i grafen, och kan till exempel anges genom kostnaden för en flygbiljett eller tågbiljett, eller kanske genom längden på kanten, eller den tid som krävs för att genomföra korsningen. Försäljaren vill hålla både resekostnaderna och den sträcka han reser så låg som möjligt.
Traveling Salesman-problemet är typiskt för en stor klass av "svåra" optimeringsproblem som har fascinerat matematiker och datavetare i åratal. Det viktigaste är att det har tillämpningar inom vetenskap och teknik. Vid tillverkningen av ett kretskort är det till exempel viktigt att bestämma den bästa ordningen i vilken en laser ska borra tusentals hål. En effektiv lösning på detta problem minskar tillverkarens produktionskostnader.
Svårighetsgrad
Generellt sett är problemet med den resande säljaren svårt att lösa. Om det finns ett sätt att dela upp problemet i mindre problemkomponenter, kommer dessa komponenter att vara minst lika komplexa som det ursprungliga problemet. Detta är vad datavetare kallar NP-hårda problem.
Många har studerat detta problem. Den enklaste (och dyraste) lösningen är att helt enkelt prova alla möjligheter. Problemet med detta är att man för N städer har (N-1) faktoriella möjligheter. Detta innebär att det för endast 10 städer finns över 180 000 kombinationer att prova (eftersom startstaden är definierad kan det finnas permutationer för de återstående nio). Vi räknar bara hälften eftersom varje rutt har en likvärdig rutt i motsatt riktning med samma längd eller kostnad. 9! / 2 = 181 440
- Exakta lösningar på problemet kan hittas med hjälp av algoritmer för grenar och gränser. Detta är för närvarande möjligt för upp till 85 900 städer.
- Heuristiska metoder använder en uppsättning vägledande regler för att välja nästa nod. Men eftersom heuristiker ger approximationer ger de inte alltid den optimala lösningen, även om godtagbara heuristiker av hög kvalitet kan hitta en användbar lösning på en bråkdel av den tid som krävs för en fullständig brute force-analys av problemet. Ett exempel på en heuristik för en nod skulle vara en summering av hur många obesökta noder som ligger "nära" en ansluten nod. Detta skulle kunna uppmuntra försäljaren att besöka en grupp av nära knutar som är grupperade tillsammans innan han går vidare till ett annat naturligt kluster i grafen. Se Monte Carlo-algoritmer och Las Vegas-algoritmer.
Frågor och svar
Fråga: Vad är problemet med den resande säljaren?
S: Traveling Salesman Problem (TSP) är ett klassiskt algoritmiskt problem inom datavetenskap och operationsforskning. Det fokuserar på optimering, där bättre lösningar ofta innebär billigare, kortare eller snabbare lösningar.
F: Hur uttrycks TSP?
S: TSP uttrycks lättast som en graf som beskriver var en uppsättning noder befinner sig.
F: Vem definierade först TSP?
Svar: Problemet med den resande säljaren definierades på 1800-talet av den irländske matematikern W. R. Hamilton och den brittiske matematikern Thomas Kirkman.
F: Vem studerade det vidare under 1930-talet?
Svar: Under 1930-talet studerade matematikerna Karl Menger i Wien och på Harvard det vidare.
F: Vad introducerade Hassler Whitney kort därefter?
S: Hassler Whitney vid Princeton University införde namnet "traveling salesman problem" strax efter att det definierats.
F: Vad betyder "bättre lösning" i detta sammanhang?
S: I detta sammanhang betyder bättre lösning ofta en lösning som är billigare, kortare eller snabbare.
F: Vilken algoritm ansåg Menger vara självklar när han studerade TSP?
S: Menger ansåg att en självklar brute-force-algoritm var en självklar algoritm när han studerade TSP och konstaterade att användningen av heuristiken för närmaste granne inte alltid ger optimala resultat.
