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.
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 . . .
|
|