Spela in på en matematisk turné

Ny algoritm förbättrar tillvägagångssättet för det resande säljaren problemet

Det resande säljaren problemet låter till en början trivialt, men är en överraskande hård matematisk mutter. © Barbara Frommann / Uni Bonn
läsa högt

High Mathematics City Tour: En ny algoritm ger den absolut bästa tillnärmningen till det matematiska resande säljaren problemet. Under mer än 60 år har matematiker letat efter en lösning för att optimera sin resplan - även superdatorer kan inte klara uppgiften. Rekordet för tillnärmning har nu minskat tyska och franska forskare till 1, 4 gånger det kortaste avståndet.

Hur planerar jag en rundtur genom flera städer så att hela resplanen blir så kort som möjligt? "Det här tur-returproblemet låter trivialt, men det är en tuff mutter att spricka, " säger Jens Vygen från Discrete Mathematics Research Institute vid University of Bonn. Med få städer på rutten är lösningen enkel: beräkna avståndet för alla möjliga anslutningar och välj den kortaste.

Men när antalet destinationer ökar, ökar också komplexiteten i den så kallade resande säljarens problem. Med 15 städer finns det redan mer än 43 miljarder olika rundresor, med 18 städer ökar antalet möjligheter till över 177 biljoner. Beräkningstiden som krävs för detta är för mycket för även de modernaste superdatorerna.

Central vikt för matematisk optimering

Problemet är inte bara intressant för turister, kommersiella resenärer eller pakettjänster: "Återreseproblemet betyder inte nödvändigtvis städer som ska korsas - mycket ofta söker man till exempel en optimal sekvens av arbetssteg, " förklarar András Sebő från universitetet i Grenoble, Astronomiska himmelundersökningar, till exempel, ber om den kortaste vägen från stjärna till stjärna. "Detta populära problem har varit centralt för matematisk optimering i årtionden."

Jens Vygen från Forskningsinstitutet för diskret matematik vid universitetet i Bonn hjälper resande säljare att hitta den kortaste vägen som möjligt. © Barbara Frommann / Uni Bonn

Matematiker har letat efter en enklare och framför allt allmän lösning i mer än 60 år - hittills utan framgång. Det finns emellertid några algoritmer som approximerar den optimala rutten. Men forskarna måste göra medgivanden: Ett något längre avstånd accepteras om beräkningstiden kan reduceras betydligt som ett resultat. Ruttens minsta längd kan beräknas väl, men en hög beräkningsinsats krävs för den nödvändiga sekvensen av städer. Den tidigare rekordhållaren tillhandahöll resplaner som var nästan halva avståndet längre än den teoretiska kortaste möjliga resplanen. display

Lökalgoritm med fina öron

Sebő och Vygen har nu tydligt underskränkt denna rekord: deras nya algoritm levererar 1, 4 gånger det optimala returresningsavståndet. Den nya posten är möjlig genom en matematisk procedur som heter "Sch ne-Ohren-Zerlegung". Här flyttar matematiker in från utsidan medan de ansluter platserna. Vygen jämför jämförelsen med lagren av en lök: "Detta fungerar bara om du har tagit tag i rätt lökstruktur och du inte ser kartan med gatorna och platserna till en början."

Märkligt nog bryde forskarna sig inte om tur-returproblemet till en början: "Som ofta är fallet var en slump på spel", säger Vygen. Egentligen ville matematiker optimera kraft- och telekommunikationsnätet på ett sådant sätt att hela systemet inte fylls i när en kabel går sönder. "Men hur många matematiker har vi alltid tur och returproblem", säger Vygen. Därför var det uppenbart att tillämpa tillvägagångssättet för nätverksproblemet också på liknande cirkulära frågor. (Combinatorica, 2014; doi: 10.1007 / s00493-011-2960-3)

(Rheinische Friedrich-Wilhelms-University Bonn, 04.11.2014 - AKR)