How do you convert Travel Salesman problem from Recursive to Iterative?

Answer 1

//Here is my copy of recursive, any suggestion on converting to Iterative? Please help!

#include <iostream>

#include <stdio.h>

#define INFINITY 9999

using namespace std;

int cost=0;

int n,a[10][10],visited[10];

int initial;

void read()

{

cout << "Please enter number of vertices: ";

cin >> n;

while (n <= 0)

{

cout << "Number of vertices has to be greater than 0. Please enter number of vertices again: ";

cin >> n;

}

};

void get(int a[10][10],int n,int visited[10])

{

int i,j,max,src,dest,wt;

for(i=0;i<n;i++)

{

visited[i]=0;

for(j=0;j<n;j++)

{

a[i][j]=999;

}

}

//display our input data

max=n*(n-1);

cout << "n = " << n << ", lines: " << max << endl;

for(i=0;i<max;i++)

{

cin >> src >> dest >>wt;

//a[src][dest]=wt;

a[dest][src]=wt;

}

//print-out matrix table

cout<<"\nCost Matrix";

cout<<"\n~\n";

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

if(a[i][j]!=999)

cout<<a[i][j]<<"\t";

else

cout<<"0\t";

}

cout<<endl;

}

//get initial destination

cout << "Please enter your initial destination: ";

cin >> initial;

};

int least(int c,int n,int a[10][10],int visited[10])

{

int nc=999,min=999,kmin;

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

if((a[c][i]!=0)&&(visited[i]==0))

{

if(a[c][i]<min)

{

min=a[i][initial]+a[c][i];

kmin=a[c][i];

nc=i;

}

}

if(min!=999)

cost+=kmin;

return nc;

};

//void mincost(int city,int n,int a[10][10],int visited[])

//{

// //==========================

// int counter;

// //cout<<"This is counter count: "<<counter;

// //==========================

// int i,ncity;

// visited[city]=1;

// cout<<city<<"<-";

// ncity=least(city,n,a,visited);

// if(ncity==999)

// {

// ncity=initial;

// printf("%d",ncity);

// cost+=a[city][ncity];

// return;

// }

// mincost(ncity,n,a,visited);

//};

void mincost(int city,int n,int a[10][10],int visited[])

{

int counter=0;

//cost = 0 variable

//cout<<"Mincost is running!"<<endl;

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

{

int a[10][10];

int i,ncity;

visited[city]=1;

cout<<city<<"<-";

ncity=least(city,n,a,visited);

if(ncity==999)

{

ncity=initial;

printf("%d",ncity);

cost+=a[city][ncity];

return;

}

}

};

void put()

{

printf("\nMinimun cost for visiting all cities:%d\n",cost);

};

main()

{

read();

get(a,n,visited);

mincost(initial,n,a,visited);

cout<<endl;

put();

}