Understanding the traveling sales algorithm

[Axel]

I'm having trouble understanding the traveling sales algorithm. Each link node represents a city with an x and y coordinate in a circular linked list. I've managed to get the each city in the linked list through a file that is passed as an argument, and print it out. What i don't understand is the distance for sales trip:

/* code tags used to keep table alignment */

City                 | x coord | y coord
---------------------+---------+---------
city1                     4.40      7.70
city2                     3.30      8.80

/* code tags used to keep table alignment */

Starting distance for sales trip = 3.11

City                 | x coord | y coord
---------------------+---------+---------
city1                     4.40      7.70
city2                     3.30      8.80


Reduced distance for sales trip  = 3.11

the formula for determining the distance between two cities is:

   double x1 = 4.40;
   double x2 = 3.30;
   double y1 = 7.70;
   double y2 = 8.80;

->> printf("%.2f", sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))* 2);

which gives: 3.11, sounds easy right? but it gets more confusing:


the original text file, before the algorithm is run:

Nowhere 28.8 17.6
Somewhere 5.6 79.12
Whoknows 55.3 49.9
Elsewhere 22.22 11.11

after:

/* code tags used to keep table alignment */
City                 | x coord | y coord
---------------------+---------+---------
Elsewhere                22.22     11.11
Nowhere                  28.80     17.60
Somewhere                 5.60     79.12
Whoknows                 55.30     49.90


Starting distance for sales trip = 183.62


City                 | x coord | y coord
---------------------+---------+---------
Elsewhere                22.22     11.11
Nowhere                  28.80     17.60
Whoknows                 55.30     49.90
Somewhere                 5.60     79.12

Reduced distance for sales trip  = 178.69

i just don't get how the 'Starting distance for sales trip' and 'Reduced distance for sales trip' are determined. Can anyone give me any hints?

[Axel]

and just an addition, the formula should be used to calculate the shortest path. For example if going from A to C to B to D is shorter than ABCD then C and B should be swapped in the link list. I'm still trying to figure out how to swap an element first before i get to that.

Another question, if i have 4 cities (A, B, C, D) how can i compare their distances? because i only have 2 pointers to the list, start and next. How do i keep track of the 3rd element etc so i can compare it to the others.

I'm still confused on how to get the "Starting distance for sales trip" and "Reduced distance for sales trip"

[treenef]

The travelling salesman problem concerns itself with the efficiency of algorithms.

A brute force solution would work however, would be regarded as being horribly inefficient.

If there are N locations to visit, the there are N! possible itineraries. (N! is pronounced N factorial which means if N was '5' then 5! would be 5x4x3x2x1.)

You can imagine how long it would take to compute a problem where N was greater than 10.

Anyway, you need to find a more efficient solution. One such solution would be Djikstra's algo. However, there is no guarantee that it will find the shortest path.

[Axel]

ok, with the algorithm i'm trying to develop N wont be greater than 10 so thats fine. I'm just not sure how to compare each link list node's x and y coordinates

[treenef]

So your problem is with the linked list? Have you tried to obtain a solution without linked lists to ensure you get the same answer as given by your teacher?



One possible solution, is to implement a brute force algorithm:

For example find all the possible routes you can take and calculate their total distance...

ABCD = 17m
ABDC = 14m
ADBC = 12m
.
.
.
DCBA = 19m

Since there are only four locations you should have 4! possible itineraries. Which is (4x3x2x1=24) possibilities. Then it would be a simple case of looping through your list and identifying the shortest journey.

However, if your teacher wants you to work with linked lists only then this may not be an option.


Secondly, I noticed a flaw in your formula:

->> printf("%.2f", sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))* 2);

Should that be there? Hmm..

[Axel]

Should that be there? Hmm..

no it shouldn't but that's the only way i could get close to the answer, 3.11. I've tried many different ways, but i can get to the answer given.

I guess i could do it the way you said, i'll give it a go. Remember that the shortest path from a-d have to be swapped to.

I'm still stuck on http://cboard.cprogramming.com/showthread.php?t=71117 so i have to get that working first.

Thanks for your help

[Axel]

Have you tried to obtain a solution without linked lists

yes i've tried hard coding the variables and tried using the formula manually without a link list and i can't get the same result.

for example with the city 1 and city 2 example:

 double x1 = 4.40;
   double x2 = 3.30;
   double y1 = 7.70;
   double y2 = 8.80;
   double total = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));

doesn't give me 3.30

[quote]

this may not be an option.
[/code]

Is there a way of doing it through a linked list? That's the problem i'm having how can i compare, in a while loop 4 destinations when i only have a next a start pointer

i have to figure out how to calculate and get reduced sales/sales trip first and so far all my calculations don't get to the correct answer.

[treenef]

/* code tags used to keep table alignment */
City                 | x coord | y coord
---------------------+---------+---------
Elsewhere                22.22     11.11
Nowhere                  28.80     17.60
Somewhere                 5.60     79.12
Whoknows                 55.30     49.90


Starting distance for sales trip = 183.62

I don't know if I use my corrected formula I get the same result...
Here's my working....

First of all let us denote the following as such:

Elsewhere = A
Nowhere   = B
Somewhere=C
Whoknows= D

Then A to B to C to D to A...

A to B = √(22.22-28.80)²+(11.11-17.60)²  = 9.24
B to C = √(28.80-5.60)²+(17.60-79.12)²    = 65.75
C to D = √(5.60-55.30)²+(79.12-49.90)²   = 57.65
D to A = √(55.30-22.22)²+(49.90-11.11)² = 50.97

Then 9.24 + 65.75 + 57.65 + 50.97 = 183.62  QED

I think in the case you have given:

/* code tags used to keep table alignment */

Starting distance for sales trip = 3.11

City                 | x coord | y coord
---------------------+---------+---------
city1                     4.40      7.70
city2                     3.30      8.80


Reduced distance for sales trip  = 3.11

You have to remember the full tour goes from city 1 to city 2 and then BACK again to city 1.

Yes

[Axel]

Yes, thanks alot! i understand that bit now. Now time to get my linked list working.

Before the list is ordered:

Nowhere 28.80 17.60
Somewhere 5.60 79.12
Whoknows 55.30 49.90
Elsewhere 22.22 11.11

I just don't get the logic behind when it's ordered.

Going from A to B:

A to B = √(22.22-28.80)²+(11.11-17.60)² = 9.24

is the shortest

shouldn't D to A = √(55.30-22.22)²+(49.90-11.11)² = 50.97
come second because its the second shortest?

[Axel]

ok i just figured out the i have to start with the city that has the lowest alphabet and then apply the algorithm. I'm still having trouble figuring out the distance between the cities so i can reorder them.

[treenef]

shouldn't D to A = √(55.30-22.22)²+(49.90-11.11)² = 50.97
come second because its the second shortest?

No, it appears to me you don't really know what is going on do you? Let's be honest.

It doesn't matter what order the list is. In fact the only way to solve this would be to find all 24 possibilities and then calculate the TOTAL distance for the entire tour.

And of those 24 any one of them could yield the shortest distance. You just don't know until you have tried each one.

Do you understand on a visual level why you need to do:

D to A = √(55.30-22.22)²+(49.90-11.11)²

to find the ACTUAL distance between the coordinates?

Moreover, using 'linked lists', which in my mind is far from trivial, is asking a bit much if you don't really understand the basics?

Have you tried googling 'travelling salesman' to get a better idea of what is going on.

hmmm?

[Axel]

ok i understand now, so i have to go to all the cities and keep swapping till i have the shortest total route? and once re-ordered that should reflect the new citieis are that are being printed out?

I think the part where i was confused was, why are the cities reordered? Does it reflect the new order of the link list (i.e. after the finding the shortest total route)?

[Axel]

treenef, after reading various resources about the traveling sales man algorithm i don't understand why the list is reordered.

i was wondering if you could explain the logic behind why the list is re-ordered. I know how to calculate the total distance now, but i need to figure out why it's ordered that way in order to do the calculations through my code (i.e. i read the original text and if i do the formula i get the wrong answer, i need to find out why it's in that order then i can start applying the calculation).

if you could show a sample from how you got from the unordered list to the answer that would be great.

Another question, how is the Reduced distance for sales trip calculated?

this is driving me nuts

[Axel]

oh silly me, i didn't even post the original text before the algorithm is run:

City                 | x coord | y coord
---------------------+---------+---------
Nowhere                  28.80     17.60
Somewhere                 5.60     79.12
Whoknows                 55.30     49.90
Elsewhere                22.22     11.11

[Axel]

hmm this is strange, i just applied the forumla to the unsorted list and it give me the correct answer:

total += sqrt( ( pow( (28.80 - 5.60), 2) + pow( (17.60 - 79.12), 2) ));
      total += sqrt( ( pow( (5.60 - 55.30), 2) + pow( (79.12 -  49.90), 2) ));
      total += sqrt( ( pow( (55.30 -  22.22), 2) + pow( (49.90 -   11.11), 2) ));
      total += sqrt( ( pow( (22.22 - 28.80), 2) + pow( (11.11 -  17.60), 2) ));

= 183.62
even more confused :|