complexity of Traveling Salesman Problem?

V

Vinay Adella

Please let me know about the searches and computational complexity involved
in the following code.


/* C program to demonstrate travelling salesperson problem. */

/* About this algorithm:
* Here we use dynamic programming to find a solution to the
* travelling salesperson problem. The problem consists of finding
* the least-cost cycle in a given set of nodes. */

#include <stdio.h>
#define MAX 100
#define INFINITY 999

int tsp_dp (int c[][MAX], int tour[], int start, int n);

int main()
{
int n; /* Number of cities. */
int i, j; /* Loop counters. */
int c[MAX][MAX]; /* Cost matrix. */
int tour[MAX]; /* Tour matrix. */
int cost; /* Least cost. */

printf ("This program demonstrates the TSP problem.");
printf ("\nHow many cities to traverse? ");
scanf ("%d", &n);
printf ("Enter the cost matrix: (999: no connection)\n");
for (i=0; i<n; i++)
for (j=0; j<n; j++)
scanf ("%d", &c[j]);

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

cost = tsp_dp (c, tour, 0, n);

printf ("Minimum cost: %d.\nTour: ", cost);
for (i=0; i<n; i++)
printf ("%d ", tour+1);
printf ("1\n");
}

int tsp_dp (int c[][MAX], int tour[], int start, int n)
{
int i, j, k; /* Loop counters. */
int temp[MAX]; /* Temporary during calculations. */
int mintour[MAX]; /* Minimal tour array. */
int mincost; /* Minimal cost. */
int ccost; /* Current cost. */

/* End of recursion condition. */
if (start == n - 2)
return c[tour[n-2]][tour[n-1]] + c[tour[n-1]][0];

/* Compute the tour starting from the current city. */
mincost = INFINITY;
for (i = start+1; i<n; i++)
{ for (j=0; j<n; j++)
temp[j] = tour[j];

/* Adjust positions. */
temp[start+1] = tour;
temp = tour[start+1];

/* Found a better cycle? (Recurrence derivable.) */
if (c[tour[start]][tour] +
(ccost = tsp_dp (c, temp, start+1, n)) < mincost) {
mincost = c[tour[start]][tour] + ccost;
for (k=0; k<n; k++)
mintour[k] = temp[k];
}
}

/* Set the minimum-tour array. */
for (i=0; i<n; i++)
tour = mintour;

return mincost;
}
 
D

Derk Gwen

# Please let me know about the searches and computational complexity involved
# in the following code.

Unless you've discoverred something worthy of a Noble Prize, the complexity is
going to be no better any other TSP solution. You're potentiallly evaluating
all possible cycles, which gives you O(N!). However since you've limitted
the input to an a priori limit of MAX, it is actually O(1) for large values of 1.

As far as I know the most efficient known probablisitic solutions are based on
simulated annealing: find one cycle and then perturb it randomly and see if the
new cycle is more efficient. The perturbation are initially large and then
reduced as the cycle converges. This can give an exact solution in extrapolynomial
time, and an approximate solution in polynomial time. The acceptable degree of
approximation determines the order of the polynomial.
 
J

Joona I Palaste

Derk Gwen said:
# Please let me know about the searches and computational complexity involved
# in the following code.
Unless you've discoverred something worthy of a Noble Prize, the complexity is
going to be no better any other TSP solution. You're potentiallly evaluating
all possible cycles, which gives you O(N!). However since you've limitted
the input to an a priori limit of MAX, it is actually O(1) for large values of 1.

I didn't know prizes were also admitted into nobility. Alfred Nobel
should be proud.

--
/-- Joona Palaste ([email protected]) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"War! Huh! Good God, y'all! What is it good for? We asked Mayor Quimby."
- Kent Brockman
 
A

August Derleth

Vinay Adella said:
Please let me know about the searches and computational complexity involved
in the following code.

Derek Gwen has answered this problem, so let me give you a few
pointers on how to make this program more functional.
/* C program to demonstrate travelling salesperson problem. */

/* About this algorithm:
* Here we use dynamic programming to find a solution to the
* travelling salesperson problem. The problem consists of finding
* the least-cost cycle in a given set of nodes. */

#include <stdio.h>
#include said:
#define MAX 100
#define INFINITY 999

int tsp_dp (int c[][MAX], int tour[], int start, int n);

int main() int main(void)
{
int n; /* Number of cities. */
int i, j; /* Loop counters. */
int c[MAX][MAX]; /* Cost matrix. */
int tour[MAX]; /* Tour matrix. */
int cost; /* Least cost. */

printf ("This program demonstrates the TSP problem.");
printf ("\nHow many cities to traverse? ");
scanf ("%d", &n);
printf ("Enter the cost matrix: (999: no connection)\n");
for (i=0; i<n; i++)
for (j=0; j<n; j++)
scanf ("%d", &c[j]);

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

cost = tsp_dp (c, tour, 0, n);

printf ("Minimum cost: %d.\nTour: ", cost);
for (i=0; i<n; i++)
printf ("%d ", tour+1);
printf ("1\n");

exit(EXIT_SUCCESS); /* If a function returns an int, it better
actually return an int. And void main(void); is /not/ correct code. */

<snip subroutine>

Other than those few things, your code is better than a lot of the
code we get around here.
 
J

Jack Klein

Vinay Adella said:
Please let me know about the searches and computational complexity involved
in the following code.

Derek Gwen has answered this problem, so let me give you a few
pointers on how to make this program more functional.
[snip]

exit(EXIT_SUCCESS); /* If a function returns an int, it better

There is no possible benefit at all here for calling exit() over
returning the value from main().

And there is no real benefit, except to the pedantic, for using
EXIT_SUCCESS over just plain old 0.
actually return an int. And void main(void); is /not/ correct code. */

<snip subroutine>

Other than those few things, your code is better than a lot of the
code we get around here.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top