What heuristic is the traveling salesman problem using?

[rahulforfriends]

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

 
/* 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;
}

[horace1]

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

[rahulforfriends]

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

[JosAH]

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

[r035198x]

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

 
/* 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)?

[JosAH]

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

[r035198x]

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?

[JosAH]

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

[r035198x]

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.

[JosAH]

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

[r035198x]

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.

[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

[r035198x]

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.

[rahulforfriends]

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

[JosAH]

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

[JosAH]

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

Start off easy, build a 2Opt heuristic. Given a route, make two cuts in it and
reconnect the two pieces the other way around. This can only be done if for
an edge e_ij == v_i ---> v_j the edge v_j ---> v_i is also a possibility.

Conceptually you can get around this restriction by giving an (impossible)
edge v_j ---> v_i an absurdly high cost factor in your cost matrix.

Only take 'downhill' steps, i.e. the new route must be cheaper than the previous
one. If no cheaper route can be found, stop.

There are O(n^2) different possibilities per iteration where n is the number of
vertexes in the route . Good luck and

kind regards,

Jos

[rahulforfriends]

oh its a little complicated..i wish u cud give me the code....
i mean the heuristic is the initial step for my program..plz help me to get obver it...or else just tel me wat exactly is happeneing in the program tat i wrote...the one using dynamic algortihm
atleast u can help me tat way plzzz

[JosAH]

oh its a little complicated..i wish u cud give me the code....
i mean the heuristic is the initial step for my program..plz help me to get obver it...or else just tel me wat exactly is happeneing in the program tat i wrote...the one using dynamic algortihm
atleast u can help me tat way plzzz

Your program isn't a heuristic method; it's a full search through the entire
graph/network. The search is implemented recursively. Basically the recurrence
relation is as follows:

c_0i + cost_of_route(v_i, v_0)

where c_0i is the cost for traveling from node 0 (the start node) to node i
in one step. The cost_of_route() method finds the minimum cost to travel
to all nodes, starting at node i and ending at node 0 again.

Try it by hand on a small (say four vertexes) graph and you'll see how the
recursive mechanism works. (hint: it takes six steps in total so its doable
to find the best route by hand).

Let the nodes/vertexes be named 0, 1, 2 and 3. Starting at 0 you can travel
to 1, 2 or 3. So the first step is either:

01
02
03

given the first step you have to find the minimum routes for all the possibilites

for 01:

1230
1320

for 02:

2130
2310

for 03:

3120
3210

kind regards,

Jos

[rahulforfriends]

hi,
my guide is not accepting this program he want me to use 3-opt or 2-opt to write this program plz send me the program i dn't hv time or else i wud had tried to write the program on my own
help me out plz

[r035198x]

hi,
my guide is not accepting this program he want me to use 3-opt or 2-opt to write this program plz send me the program i dn't hv time or else i wud had tried to write the program on my own
help me out plz

We don't do student's assignments.

See the guidelines