TSP (Travelling Salesman problem)


#include <iostream>
using namespace std;
#define MAX 100
#define INF 354754546

int n = 5;
int step = 0;
int path[MAX];
int visited[MAX];
int array[MAX][MAX] = {
{INF, 3, 4, 2, 7},
{3, INF, 4, 6, 3},
{4, 4, INF, 5, 8},
{2, 6, 5, INF, 6},
{7, 3, 8, 6, INF}
};

void TSP(int start)
{
int min = 0;
while(step < n)
{
for(int i=0; i<step; i++) // find minimum cost.
{
if(visited[i] == 0 && array[start][i] < array[start][min])
{
min = i;
}
}
array[start][min] = array[min][start] = INF;
start = min; // set the next start point.
path[step++] = start; // next step.
visited[start] = 1; // set this point visited.
}
}

void PrintPath()
{
for(int i=0; i<n; i++){
cout << path[i] << " ";
}
}
int main()
{
TSP(0); // start from the first point
PrintPath();
return 0;
}

Advertisements

2 thoughts on “TSP (Travelling Salesman problem)

  1. Pingback: Artificial intelligence | David Ng

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s