TSP - dynamic programming

[DawnofanewEra]

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

[kal_crazy]

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.

[DawnofanewEra]

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.

[Moschops]

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.

[tinstaafl]

Also you have a constant NUM_CITIES set to 5