What heuristic is the traveling salesman problem using?

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • rahulforfriends
    New Member
    • Mar 2007
    • 6

    What heuristic is the traveling salesman problem using?

    can any one plz help me and tell wat heuristic this program of travelling salesman problem is using???


    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[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];
    
    /* Adjust positions. */
    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;
    }
    Last edited by horace1; Mar 25 '07, 08:02 AM. Reason: added code tags
  • horace1
    Recognized Expert Top Contributor
    • Nov 2006
    • 1510

    #2
    can you run the program with sample data to determine the algorithm?

    Comment

    • rahulforfriends
      New Member
      • Mar 2007
      • 6

      #3
      Originally posted by horace1
      can you run the program with sample data to determine the algorithm?
      well yah i can run the program wid a sample data....
      wat i am not able to determine is the heuristic of this tsp programme

      i m not sure which heuristic it is following
      cud u plz help me out

      Comment

      • JosAH
        Recognized Expert MVP
        • Mar 2007
        • 11453

        #4
        This recursive TSP solving implementation is not a heuristic, it's an exhaustive
        search through the entire graph. Basically it runs like this:

        1) given a cheapest route so far, find the cheapest path from the current
        starting point (the endpoint of the route so far) to the starting point.

        Although this method always finds a cheapest TSP solution, it'll take a lot
        of time for substantial graphs/networks.

        kind regards,

        Jos

        Comment

        • r035198x
          MVP
          • Sep 2006
          • 13225

          #5
          Originally posted by rahulforfriends
          can any one plz help me and tell wat heuristic this program of travelling salesman problem is using???


          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[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];
          
          /* Adjust positions. */
          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;
          }
          I don't see any heuristic here. Isn't it that for the algorithm to be heuristic, it must be possible for it to run and follow two different paths given the same input parameters (follows a non-deterministic path)?

          Comment

          • JosAH
            Recognized Expert MVP
            • Mar 2007
            • 11453

            #6
            Originally posted by r035198x
            I don't see any heuristic here. Isn't it that for the algorithm to be heuristic, it must be possible for it to run and follow two different paths given the same input parameters (follows a non-deterministic path)?
            Not really: a heuristic can be (and most of the time is) deterministic. The
            characteristic of a heuristic is that it is fast and, more important, it finds
            a solution not worse than so many percent from an optimal solution.

            Some definitions are even weaker: the heuristic should just produce an
            'acceptable' solution. For a TSP a 2-opt or 3-opt are cheap heuristics.
            A better heuristic is the Lin-Kernighan opt method. All methods can fail
            miserably for some graphs (but that's why they're called a heuristic ;-)

            kind regards,

            Jos
            Last edited by JosAH; Mar 28 '07, 09:32 AM. Reason: typo ...

            Comment

            • r035198x
              MVP
              • Sep 2006
              • 13225

              #7
              Originally posted by JosAH
              Not really: a heuristic can be (and most of the time is) deterministic. The
              characteristic of a heuristic is that it is fast and, more important, it finds
              a solution not worse than so many percent from an optimal solution.

              Some definitions are even weaker: the heuristic should just produce an
              'acceptable' solution. For a TSP a 2-opt or 3-opt are cheap heuristics.
              A better heuristic is the Lin-Kernighan opt method. All methods can fail
              miserably for some graphs (but that's why they're called a heuristic ;-)

              kind regards,

              Jos
              Qoute=Wiki
              ..there is no proof the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will always be the case.


              So the non-determinism is in the frequency of getting a solution efficiently or am I still missing it?

              Comment

              • JosAH
                Recognized Expert MVP
                • Mar 2007
                • 11453

                #8
                Originally posted by r035198x
                Qoute=Wiki
                ..there is no proof the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will always be the case.


                So the non-determinism is in the frequency of getting a solution efficiently or am I still missing it?
                You wrote: for identical input different results might be obtained, which is not
                true per se; i.e. heuristics can be, and most of the time are deterministic
                processes.

                A heuristic simply applies a (slightly) incorrect rule and tries to find a "good"
                (mind the quotes) solution to a problem quickly. Of course it's beneficial
                of the heuristic itself could signal that it failed somehow. What wiki said:
                "no guarantee that a good solution was found" is true for most heuristics.

                kind regards,

                Jos

                Comment

                • r035198x
                  MVP
                  • Sep 2006
                  • 13225

                  #9
                  Originally posted by JosAH
                  You wrote: for identical input different results might be obtained, which is not
                  true per se; i.e. heuristics can be, and most of the time are deterministic
                  processes.

                  ...
                  Ah, now here is something.

                  I actually said a different path could be taken meaning path taken at arriving at the result. But in this case the path taken is actually the result! So I guess I could have clouded things a bit. I do get your explanation though its quite nice.

                  Here is another dfn


                  Quote = What is
                  As an adjective, heuristic (pronounced hyu-RIS-tik and from the Greek "heuriskein " meaning "to discover") pertains to the process of gaining knowledge or some desired result by intelligent guesswork rather than by following some preestablished formula. (Heuristic can be contrasted with algorithmic.)


                  Which is where I got the "different path at arriving at the solution" idea since I saw that guesswork can be used for determining the next step.

                  Comment

                  • JosAH
                    Recognized Expert MVP
                    • Mar 2007
                    • 11453

                    #10
                    Originally posted by r035198x
                    Which is where I got the "different path at arriving at the solution" idea since I saw that guesswork can be used for determining the next step.
                    Ah, yes; but most of the time that "guesswork" will be a deterministic process.
                    There *do* exist (pseudo) non-deterministic search algorithms though;
                    simulated annealing comes to mind where a current solution is just messed up
                    a bit in order to be able to continue the search for an optimum from another
                    "starting point". The worse (or more complicated) those search spaces are,
                    the more those non-deterministic heuristics come in and people find fairly
                    good solutions just by accident and a lot of brute force ;-)

                    kind regards,

                    Jos

                    Comment

                    • r035198x
                      MVP
                      • Sep 2006
                      • 13225

                      #11
                      Originally posted by JosAH
                      Ah, yes; but most of the time that "guesswork" will be a deterministic process.
                      There *do* exist (pseudo) non-deterministic search algorithms though;
                      simulated annealing comes to mind where a current solution is just messed up
                      a bit in order to be able to continue the search for an optimum from another
                      "starting point". The worse (or more complicated) those search spaces are,
                      the more those non-deterministic heuristics come in and people find fairly
                      good solutions just by accident and a lot of brute force ;-)

                      kind regards,

                      Jos
                      I see. I never really grasped the concept behind simulated annealing and its cooling metal analogy. Maybe one day I'll ask you about it.

                      Comment

                      • rahulforfriends
                        New Member
                        • Mar 2007
                        • 6

                        #12
                        so cud u plz give me a program i mean a c++ or c program on tsp tat uses 2-opt or 3-opt or ne other better heuristic to solve the tsp

                        Comment

                        • r035198x
                          MVP
                          • Sep 2006
                          • 13225

                          #13
                          Originally posted by rahulforfriends
                          so cud u plz give me a program i mean a c++ or c program on tsp tat uses 2-opt or 3-opt or ne other better heuristic to solve the tsp
                          We don't give out code. We assist you to write correct code.

                          Comment

                          • rahulforfriends
                            New Member
                            • Mar 2007
                            • 6

                            #14
                            ok thn plz help me out to write the code
                            i mean i m just not getting hoiw to start the code
                            i hv found the cost matrix now how shall i proceed further

                            Comment

                            • JosAH
                              Recognized Expert MVP
                              • Mar 2007
                              • 11453

                              #15
                              Originally posted by r035198x
                              I see. I never really grasped the concept behind simulated annealing and its cooling metal analogy. Maybe one day I'll ask you about it.
                              Wiki has a nice page about simulated annealing.

                              kind regards,

                              Jos

                              Comment

                              Working...