Why are some algorithm to solve TSP using dynamic programming can solve up to 10 cities while some can go beyond that...i.e. 10, 100 or more..!!

What is the factor that determines the capability of the algortihm to solve more than 10 or less..??

Edited by DawnofanewEra: change in question

4
Contributors
4
Replies
28
Views
4 Years
Discussion Span
Last Post by tinstaafl

For dynamic programming we are breaking down the problem into sub-problems hence there are too many computations. However, you can optimize by using Kruskal's algorithm.

In my opinion the best way to solve TSP is by Simulated Annealing. This works by comparing the current solution with the new solution. If the new solution is worse then we keep the current solution and store into temporary storage lets call it best solution. And this keeps happening in a loop. We gave initially a temperature = 10000 and a cooling rate=0.003. So while temperature is greater than 1 we continue to find the best or optimal solution. Once the temperature is less than 1 we output the "optimal solution" or the best one. Simulated Annealing can find 1024 cities or more.

I was wondering why my program (dynamic programming) cannot compute more than 5 cities.

``````#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <iomanip>
#include <sys/time.h>

#define NUM_CITIES 5

using namespace std;

class dynamic
{
private:
int c[5][5],d[24],p[24][6],list[5],r;
public:
dynamic();
void getdata();
void display();
int fact(int num);
int min(int list[]);
void perm(int list[], int k, int m);
void sol();
};

dynamic::dynamic()
{
r=0;
}

void dynamic::getdata()
{
//cout<<"Enter no. of cities:";
//cin>>n;
//cout<<endl;
int j, i;
for (int i=0;i<NUM_CITIES;i++)
for (int j=0;j<NUM_CITIES;j++)
c[i][j]=0;

for (i=0;i<NUM_CITIES;i++)
{
for (j=0;j<NUM_CITIES;j++)
{
if (i!=j)                       //only calculates distances for cities which don't map onto themselves
{
int tempRand = rand()%40;
while (tempRand == 0){
tempRand = rand()%40;
}
c[i][j] = tempRand;
c[j][i] = tempRand;
}
else
{
c[i][j] = 0;
}
}
list[i] = i+1;
}
/*if (c[i][j]==0)
{
cout<<"Enter cost from "<<i<<" to "<<j<<" :";
cin>>c[i][j];
c[j][i]=c[i][j];
}*/

//for (i=0;i<n-1;i++)
//  list[i]=i+1;
}

int dynamic::fact(int num)
{
int f=1;
if (num!=0)
for (int i=1;i<=num;i++)
f=f*i;
return f;
}

void dynamic::perm(int list[], int k, int m)
{
int i,temp;
if (k==m)
{
for (i=0;i<=m;i++)
{
p[r][i+1]=list[i];
}
r++;
}
else
for (i=k;i<=m;i++)
{
temp=list[k]; list[k]=list[i]; list[i]=temp;
perm(list,k+1,m);
temp=list[k]; list[k]=list[i]; list[i]=temp;
}
}

void dynamic::sol()
{
int i;
perm(list,0,NUM_CITIES-2);
for (int i=0;i<fact(NUM_CITIES-1);i++)
{
p[i][0]=0;
p[i][NUM_CITIES]=0;
}
for (i=0;i<fact(NUM_CITIES-1);i++)
{
d[i]=0;
for (int j=0;j<NUM_CITIES;j++)
{
d[i]=d[i]+c[p[i][j]][p[i][j+1]];
}
}
}

int dynamic::min(int list[])
{
int minimum=list[0];
for (int i=0;i<fact(NUM_CITIES-1);i++)
{
if (list[i]<minimum)
minimum=list[i];
}
return minimum;
}

void dynamic::display()
{
int i,j;
cout<<endl<<"The cost Matrix:"<<endl;
for (i=0;i<NUM_CITIES;i++)
{
for (j=0;j<NUM_CITIES;j++)
cout<<c[i][j]<<"\t";
cout<<endl;
}
cout<<endl<<"The Possible paths and their corresponding cost:"<<endl;
for (i=0;i<fact(NUM_CITIES-1);i++)
{
for (j=0;j<NUM_CITIES+1;j++)
cout<<p[i][j]<<"\t";
cout<<"--> "<<d[i]<<endl;
}
cout<<endl<<"The shortest path :"<<endl;
for (i=0;i<fact(NUM_CITIES-1);i++)
{
if (d[i]==min(d))
break;
}
for (j=0;j<=NUM_CITIES;j++)
{
cout<<p[i][j]<<" ";
}
cout<<endl<<"\nThe cost of this path is "<<d[i]<<endl;
}

int main()
{
//clrscr();
char cont;
srand (time(NULL));             //seeds random numbers
do{

struct timeval start, end;
gettimeofday(&start, NULL);
double time;
//CTimer *Itimer = new CTimer;
//Itimer->Start();

dynamic ts;
ts.getdata();

//Itimer->End();

//cout <<"Time: " << setprecision(5) << Itimer->GetTimeInMilliseconds() << '\n';

ts.sol();
ts.display();

gettimeofday(&end, NULL);
time = ((end.tv_sec * 1000000 + end.tv_usec) - (start.tv_sec * 1000000 + start.tv_usec)) / 1000000.0;
cout <<"Time: " << time << '\n';

cout << "\n\nDo you want to run again? [Y or N]: ";
cin >> cont;

while (cont != 'Y' && cont != 'y' && cont != 'N' && cont != 'n')
{
cout << "\n\nInvalid response! Please re-enter: ";
cin >> cont;
}
} while (cont == 'Y' || cont == 'y');

system("PAUSE");
return 0;

//getch();
}
``````

Is there anything I should change so that it can compute like 10 cities and more.

You have hard-coded the size of your arrays:
`int c[5][5],d[24],p[24][6],list[5],r;`

If you need arrays that can have their size set at runtime, don't use arrays. Use C++ std::vector (or the shiny new std::array if your compiler supports it) to get arrays that you can set the size of at runtime.

Edited by Moschops

Also you have a constant `NUM_CITIES` set to 5

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.