Inledning

Vi ska i denna artikel ta upp det klassiska handelsresandeproblemet. På engelska kort kallat TSP (travelling salesman problem). Problemet har sina rötter så tidigt som 1832 men behandlades först seriöst på 1930-talet.

Problemet var en gång formulerat som "hur reser man snabbast från New York till alla delstatshuvudstäder i USA och sedan tillbaka till New York?". Eftersom det finns runt 50 hållplatser på resan så blir antalet kombinationer väldigt stort! Grundproblemet är alltså att ett antal platser skall besökas och den mest optimala (kortaste) vägen ska hittas som tar dig från punkt A, via alla andra punkter, tillbaka till punkt A.

Det visar sig att grundproblemet dyker upp i många olika sammanhang och tillämpningar t.ex. inom grafteori, nätverkskommunikation, etc. Problemet blir extra intressant då det visar sig att det inte finns någon algoritm som hittar den bästa vägen utan att testa ALLA kombinationer, även kallat Brute force. Att testa alla kombinationer är inte möjligt då det skulle ta för lång tid helt enkelt.

Kring TSP kan vi alltså skapa olika algoritmer för att försöka att antingen a) hitta en snabb lösning eller b) hitta en bra lösning. En bra algoritm hade helst både varit snabb och ge ett bra resultat.

Komplexitet

Innan vi presenterar en algoritm så kan vi diskutera komplexiteten i själva problemet. Säg att vi har 4 platser att besöka: A, B, C och D. Hur många kombinationer kan jag skapa?

Rätt svar är 24. Som första punkt kan jag välja 4, som andra 3, som tredje punkt 2 och som fjärde 1. Alltså 4 x 3 x 2 x 1 = 24. Exempel: ABCDA, BACDB, etc. Men om vi tänker efter lite så behöver vi inte så många kombinationer.

Eftersom varje väg innehåller alla punkter och ska avslutas i den punkt vi började så kan vi alltid välja vilken punkt vi vill börja med. I vårt exempel kan vi utgå från A och undersöka alla möjligheter nu. Svaret blir då 3 x 2 x 1 = 6 kombinationer. Detta då t.ex. ABCDA är samma väg som BCDAB, CDABC, DABCD.

Den komplexitet som beskrivs i första exemplet är O(n!). I andra exemplet är det egentligen (n-1)! men fortfarande i jämförbarhet med mängden data O(n!). Testa en gång att beräkna 50! (om du kan). Du inser då att det är ett VÄLDIGT stort tal.

Slumpa lösning

I ett första försök att hitta och rita ut en väg så tar vi en slumpvis lösning. Vi tar helt enkelt den väg som blir när vi slumpar ut platserna som ska besökas. Platserna lagrar vi i en List som Vector2 så att varje plats har en X- och en Y-koordinat.

För att visualisera resultatet hav vi valt att använda MonoGame samt grunderna från artikeln Cirklar o linjer .

Platserna ritas som mörkblå punkter där röd symboliserar startpunkten på resan. Linjer dras sedan från punkt till punkt i den ordning som de råkat slumpas fram. Resultatet blir sådär...

Koden får att slumpa är inte så mycket att fokusera på men koden för att beräkna avståndet är lite mer intressant. Här har vi valt modulo i loop'en för att kunna hantera sista beräkningen då avståndet från sista punkt till första också ska beräknas. Samma teknik använder vi när vi ritar ut alla linjer.

    // Random 
    for (int i = 0; i < 50; i++)
        routeRandom.Add(new Vector2(rnd.Next(20, 1260), rnd.Next(40, 700)));

    for (int i = 0; i < routeRandom.Count; i++)
        routeRandomLength += (routeRandom[i] - routeRandom[(i + 1) % routeRandom.Count]).Length();

    for (int i = 0; i < routeRandom.Count; i++)
        DrawLine(routeRandom[i], routeRandom[(i + 1)%routeRandom.Count], Color.GreenYellow, 3);

Närmsta granne

Nästa steg är att implementera någon strategi för att hitta en bättre väg. En enkel algoritm är att utgå från en startpunkt och sedan hela tiden välja den närmsta punkt som nästa mål. Denna strategi kallas "närmsta granne" eller nearest neighbour på engelska. Ibland kallas den även för "greedy" på engelska.

    //Nearest neighbour
    List<Vector2> tmp = new List<Vector2>(routeRandom);
    routeNearest.Add(tmp[0]);
    tmp.RemoveAt(0);

    while (tmp.Count > 0)
    {
        //Find closest
        var start = routeNearest[routeNearest.Count - 1];
        var pick = tmp[0];
        var length = (start - pick).LengthSquared();

        for (int i = 1; i < tmp.Count; i++)
        {
            if ((start - tmp[i]).LengthSquared() < length)
            {
                length = (start - tmp[i]).LengthSquared();
                pick = tmp[i];
            }
        }
        routeNearest.Add(pick);
        tmp.Remove(pick);
    }
    

Tanken med koden är att först skapa en kopia av alla platser. Sedan välja ut en startpunkt. Därefter leta bland de platser som finns kvar och hitta den som ligger inom närmast räckhåll. När vi hittat den närmsta (pick) så lägger vi till den i vår lista och tar samtidigt bort den från listan över återstående platser.

Resultatet blir genast betydligt bättre!

2-opt

2-opt är en "enkel" sökalgoritm för TSP som föreslogs 1958. Algoritmen jobbar fram nya förslag genom att ta en begränsad bit av vägen, klippa ut, vända, sätta tillbaka och se om resultatet blev bättre. Genom att systematiskt göra detta blir resultatet att alla vägar som korsar varandra istället "rätas ut".

Som pseudokod kan algoritmen beskrivas såhär:

        
2optSwap(route, i, k) {
    //1. take route[1] to route[i-1] and add them in order to new_route
    //2. take route[i] to route[k] and add them in reverse order to new_route
    //3. take route[k+1] to end and add them in order to new_route
    return new_route;
}
        
repeat until no improvement is made {
   start_again:
   best_distance = calculateTotalDistance(existing_route)
   for (i = 0; i < number of nodes eligible to be swapped - 1; i++) {
       for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
           new_route = 2optSwap(existing_route, i, k)
           new_distance = calculateTotalDistance(new_route)
           if (new_distance < best_distance) {
               existing_route = new_route
               goto start_again
           }
       }
   }
}
    

Källa Wikipedia

Video

Avslutning

TSP erbjuder stora utmaningar. Du som läsare kan själv experimentera med egna algoritmer för att hitta lösningar. En nog så svår uppgift kan vara att implementera en brute force algoritm som testar ALLA kombinationer.

Andra mer avancerade algoritmer finns givetvis, t.ex. 3-opt och Lin–Kernighan heuristic.

Vi har inte lagt någon djupare matematisk fokus på problemet. Vill man det så rekommenderar vi vidare läsning på området, t.ex. Hamilton cykler.

Koden finns för nedladdning.