Software & Finance





Viual C++ - Travelling Salesman Problem Solved





 

Travelling salesman problem can be solved easily if there are only 4 or 5 cities in our input.

But if there are more than 20 or 50 cities, the perfect solution would take couple of years to compute.

 

I have discussed here about the solution which is faster and obviously not the best solution using dynamic programming.

 

TSP

 

 

The idea that I have used here is to split the problem into small pieces and find the solution and then join them.

 


Source Code


#include "TSP.h"

#include <algorithm>

#include <math.h>

#include <string>

#include <vector>

#include <map>

#include <set>

 

 

using namespace std;

 

typedef struct _CITY_INFO

{

    std::string cityname;

    int x;

    int y;

 

} CITY_INFO;

 

static CITY_INFO polypoints[] = {

    { "A", 5,   10 },

    { "B", 10,    20 },

    { "C", 15,    5 },

    { "D", 20,    15 },

    { "E", 25,    20 },

    { "F", 30,    30 },

    { "G", 20,    18 },

    { "H", 30,    5 },

    { "I", 30,    15 },

    { "J", 20,    25 },

    { "K", 6,     10 },

    { "L", 15,    10 },

    { "M", 40,    10 },

    { "N", 45,    25 },

    { "O", 40,    35 },

    { "P", 45,    45 },

    { "Q", 40,    20 },

    { "R", 52,    35 },

    { "S", 55,    40 },

    { "T", 50,    25 },

    { "U", 50,    20 },

    { "V", 55,    25 },

    { "W", 60,    30 },

    { "X", 50,    50 },

    { "Y", 60,    45 },

    { "Z", 60,    60 },

};

 

 

double CalculateDistance(CITY_INFO x, CITY_INFO y)

{

    double result = sqrt( (double)(x.x - y.x)*(x.x - y.x) + (x.y - y.y)*(x.y - y.y));

    return result;

}

 

int TSP_Helper(std::vector<CITY_INFO> &arr, double *dist, std::string &path, CITY_INFO &firstpoint, CITY_INFO &lastpoint)

{

    int len = arr.size();

    if(len > 5)

        return -1; // Not Supported

 

    double mindist = INT_MAX;

    std::string str = "01234";

    str = str.substr(0, len);

    do

    {

        double distance = 0;

        for(int i = 0; i < str.size() - 1; i++)

        {

            distance += CalculateDistance(arr[str[i]-'0'], arr[str[i+1] - '0']);

        }

        if( mindist > distance)

        {

            mindist = distance;

            *dist = mindist;

           

            path = "";

            for(int i = 0; i < str.size(); i++)

            {

                path += arr[str[i]-'0'].cityname;

            }

 

            firstpoint = arr[str[0]-'0'];

            lastpoint = arr[str[str.size() - 1]-'0'];           

        }

        //std::cout << *dist << "\t" << str.c_str() << "\n";

 

    } while(std::next_permutation(str.begin(), str.end()) != false);

}

 

bool SplitSet(const std::vector<CITY_INFO> &myset, std::vector<std::vector<CITY_INFO> > &mysplitset)

{

    // Construct a grid

 

    std::vector<CITY_INFO>::const_iterator it = myset.begin();

 

    int minx = it->x;

    int maxx = it->x;

    int miny = it->y;

    int maxy = it->y;

 

    for(; it != myset.end(); ++it)

    {

        if(minx >= it->x)

            minx = it->x;

        if(maxx < it->x)

            maxx = it->x;

 

        if(miny >= it->y)

            miny = it->y;

        if(maxy < it->y)

            maxy = it->y;

    }

    int width = maxx - minx;

    int height = maxy - miny;

    int midx = width / 2 + minx;

    int midy = height / 2 + miny;

 

   

    std::vector<CITY_INFO> s1, s2, s3, s4;

    std::vector<CITY_INFO> *pset[] = { &s1, &s2, &s3, &s4 };

 

    it = myset.begin();

    for(; it != myset.end(); ++it)

    {

        // First Grid

        if(it->x < midx && it->y < midy)

            s1.push_back(*it);       

    

        // Second Grid

        if(it->x >= midx && it->y < midy)

            s2.push_back(*it);

   

        // Third Grid

        if(it->x < midx && it->y >= midy)

            s3.push_back(*it);

       

        // Fourth Grid

        if(it->x >= midx && it->y >= midy)

            s4.push_back(*it);

    }

 

    for(int i = 0; i < 4; i++)

    {

        if(pset[i]->size() <= 5)

        {

            if(pset[i]->size() > 0)

                mysplitset.push_back(*pset[i]);

        }

        else

        {

            std::vector<std::vector<CITY_INFO> > tempset;

            SplitSet(*pset[i], tempset);

            for(std::vector<std::vector<CITY_INFO> >::iterator tit = tempset.begin();

                tit != tempset.end(); ++tit)

            {

                if(tit->size() > 0)

                    mysplitset.push_back(*tit);

            }

        }

    }

    return true;

}

 

int TSP_Start(CITY_INFO *parr, int len, double *dist, std::string &finalpath)

{

    int NumCities = len;

    if(NumCities <= 5)

    {

        std::vector<CITY_INFO> myset;

        for(int i = 0; i < len; i++)

        {

            myset.push_back(parr[i]);

        }

        CITY_INFO firstpoint, lastpoint;

        TSP_Helper(myset, dist, finalpath, firstpoint, lastpoint);

    }

    else

    {

        std::vector<CITY_INFO> myset;

        for(int i = 0; i < len; i++)

        {

            myset.push_back(parr[i]);

        }

 

        std::vector<std::vector<CITY_INFO> > mysplitset;

        SplitSet(myset, mysplitset);

 

        double distance = 0;

        std::string result = "";

       

 

        finalpath = "";

        CITY_INFO firstpoint, lastpoint;

        for(int i = 0; i < mysplitset.size(); i++)

        {

            std::vector<CITY_INFO> current = mysplitset[i];

           

            if(i == 0)

            {

                double distSP = 0;

                std::string path;

                TSP_Helper(current, &distSP, path, firstpoint, lastpoint);

 

                std::cout << "Path: "<< distSP << "\t" << path.c_str() << "\n";

                distance = distSP;

                finalpath = path;

            }

            else

            {

                double distSP = 0;

                std::string path;

                CITY_INFO fp, lp;

                TSP_Helper(current, &distSP, path, fp, lp);

 

                distance += distSP;

                finalpath += path;

 

                // Previous iteration last and current first point distance

                std::vector<CITY_INFO> prev = mysplitset[i - 1];

                // optimization required on this line!!!

                // Distance between the last point and the closet point the current circuit would be taken here instead of first point

                distance += CalculateDistance(lastpoint, fp);

                lastpoint = lp;

                firstpoint = fp;

 

                std::cout << "Path: " << distance << "\t" << finalpath.c_str() << "\n";

                *dist = distance;

            }

        }

    }

    return 0;

}

 

 

void main()

{   

 

    int NumCities = sizeof(polypoints) / sizeof(polypoints[0]);

    double dist = 0;

    std::string path;

    TSP_Start(polypoints, 26, &dist, path);

 

    std::cout << "\nPath: " << dist << "\t" << path.c_str() << "\n\n";

}

 

Output


Path: 15        AKLC

Path: 46.1803   AKLCDIH

Path: 71.1803   AKLCDIHB

Path: 109.746   AKLCDIHBEGJF

Path: 132.107   AKLCDIHBEGJFM

Path: 154.989   AKLCDIHBEGJFMNQ

Path: 182.06    AKLCDIHBEGJFMNQUTVW

Path: 213.856   AKLCDIHBEGJFMNQUTVWOP

Path: 238.964   AKLCDIHBEGJFMNQUTVWOPRSY

Path: 264.287   AKLCDIHBEGJFMNQUTVWOPRSYXZ

 

Path: 264.287   AKLCDIHBEGJFMNQUTVWOPRSYXZ

 

Press any key to continue . . .