complexity of Traveling Salesman Problem?

Discussion in 'C Programming' started by Vinay Adella, Sep 3, 2003.

  1. Vinay Adella

    Vinay Adella Guest

    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;
    }
     
    Vinay Adella, Sep 3, 2003
    #1
    1. Advertising

  2. Vinay Adella

    Derk Gwen Guest

    Vinay Adella <> 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.

    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
    She broke your heart and inadvertendently drove men to deviant lifestyles.
     
    Derk Gwen, Sep 3, 2003
    #2
    1. Advertising

  3. Derk Gwen <> scribbled the following:
    > Vinay Adella <> 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 () ---------------------------\
    | 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
     
    Joona I Palaste, Sep 3, 2003
    #3
  4. Vinay Adella <> wrote in message news:<>...
    > 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 <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[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.
     
    August Derleth, Sep 3, 2003
    #4
  5. Vinay Adella

    Jack Klein Guest

    On 3 Sep 2003 15:28:02 -0700, (August
    Derleth) wrote in comp.lang.c:

    > Vinay Adella <> wrote in message news:<>...
    > > 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
     
    Jack Klein, Sep 4, 2003
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. KantKwitDansin1

    Traveling Salesman Problem

    KantKwitDansin1, Dec 11, 2004, in forum: C++
    Replies:
    9
    Views:
    5,575
    Surendra Singhi
    Dec 12, 2004
  2. Replies:
    5
    Views:
    1,006
    Jim Langston
    Sep 11, 2006
  3. Replies:
    0
    Views:
    668
  4. JSH
    Replies:
    61
    Views:
    1,545
    Michael Press
    Aug 21, 2008
  5. Ruby Quiz
    Replies:
    17
    Views:
    322
    Rick DeNatale
    Apr 29, 2009
Loading...

Share This Page