Not Yet Answered # TSP - dynamic programming

kal_crazy 13 Discussion Starter DawnofanewEra Moschops 683 Hey, so I wanna ask how I need to create a method who will remove word if in that word is 2 same chars. Example: "Potato" in this word there is a 2 "o" chars so this word will need to be removed. "Forum" in this word there is no ...

0

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 3 Years Ago by DawnofanewEra*: change in question

0

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.

0

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.

0

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 3 Years Ago by Moschops*

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Help! I want to create a java program that finds the highest even integer among the values entered by the user. Stop asking values when a value less than 1 have been entered. If no even integer is entered, display "No Even Integer"

Here is the sample output that I ...

I am writing a java program that needs to execute shell commands, so I wrote a function that would take the command to execute as a string (ie: "mkdir ~/Folder1") and execute that command with the shell. Here is the function:

```
try
{
Runtime run = Runtime.getRuntime();
Process pr = ...
```