Velocity Reviews > complexity of Traveling Salesman Problem?

# complexity of Traveling Salesman Problem?

Guest
Posts: n/a

 09-03-2003
in the following code.

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

* 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[i][j]);

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

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

printf ("Minimum cost: %d.\nTour: ", cost);
for (i=0; i<n; i++)
printf ("%d ", tour[i]+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];

temp[start+1] = tour[i];
temp[i] = tour[start+1];

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

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

return mincost;
}

Derk Gwen
Guest
Posts: n/a

 09-03-2003
# 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.

--
Derk Gwen http://derkgwen.250free.com/html/index.html

Joona I Palaste
Guest
Posts: n/a

 09-03-2003
Derk Gwen <(E-Mail Removed)> scribbled the following:
> Vinay Adella <(E-Mail Removed)> wrote:
> # 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 ((E-Mail Removed)) ---------------------------\
| 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

August Derleth
Guest
Posts: n/a

 09-03-2003
Vinay Adella <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>.. .
> 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. */
>
> * 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 <stdlib.h> /* For EXIT_SUCCESS and EXIT_FAILURE */
> #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[i][j]);
>
> for (i=0; i<n; i++)
> tour[i] = i;
>
> cost = tsp_dp (c, tour, 0, n);
>
> printf ("Minimum cost: %d.\nTour: ", cost);
> for (i=0; i<n; i++)
> printf ("%d ", tour[i]+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.

Jack Klein
Guest
Posts: n/a

 09-04-2003
On 3 Sep 2003 15:28:02 -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) (August
Derleth) wrote in comp.lang.c:

> Vinay Adella <(E-Mail Removed)> wrote in message news:<(E-Mail Removed)>.. .
> > 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