Hi there, i need some help for the traveling salesman prob in C
I have an array with distances to cities
A B C D E
A 0 5 7 1 9
B 5 0
C 7 0
D 1 0
E 9 0
etc.................................
With a brute force i get all combinations ABCDE ABDCE ABCED ...........
I guess i have to use 5 for loops. Not sure how to do that.
In a corresponding array i store the distances by claculating with the
help of the table look up.
SOS....HELP URGENT
THANKING YOU ALL IN ADVANCE
CLUESSSSS????????
If you want to do this brute force in the program you can. Just do it the
same way you did in your head or on paper and pencil. There are better
algorithms out there, better being faster, in that they don't try every
possible combination. They don't neccessarily produce the shortest
distance, but one that okay. They can be tuned to be better than okay or
worst than okay.
Now, lets go back to your problem, which I suspect is a homework problem.
Think about how you did it using brute force. I suspect your howework
question is something along the lines of, You have a table with distance
between cities. Find the shortest possible path to visit every city once.
How can you produce something that lists every way to travel the 5 cities?
Each entry in this list would have 5 elements, one for each city. The list
would have some number of entries. First think about what you want each
entry to be. It could be an array of 5 chars ('A', 'B', 'C', 'D', 'E') or 5
numbers (A = 1, B=2, C=3, E=4, F=5) or you could make it a structure, or a
std::vector. For simplicity I would probably go with an array of 5 chars
and probably encapsulate it in a class. Then I would make a std::vector of
this class, then start populating it.
That is the real root of your homework, how do you populate it? How do you
come up with a list of each possible combination of visiting cities? You
have to make sure not to have duplicates, 'A', 'B', 'A', 'D', 'E' is invalid
because it has 'A' twice. Your 5 for loops is one way to do it, and is
probably the way I would do it for simplicity.
Pseudo code which will not compile, which is brute force and slow:
for ( FirstCity = 'A' to 'E' )
for ( SecondCity = 'A' to 'E' )
if ( SecondCity != FirstCity )
for ( ThirdCity = 'A' to 'E' )
if ( ThirdCity != FirstCity && ThirdCity != SecondCity )
for ( ForthCity = 'A' to 'E' )
if ( ForthCity != ThirdCity && ... )
for ( FifthCity = 'A' to 'E' )
if ( FifthCity != FirstCity && ... )
Add Element FirstCity + SecondCity + ThirdCity
+ ForthCity + FifthCity
The iterations can reach 5^5 = 3125
If there were 6 cities it would be 6^6 or 46656
7 would be 823543
As you can see it grows exponentionally.
But, in reality, we won't iterate though 3125 because if FirstCity == 'A'
and SecondCity == 'A' we won't iterate though the rest. It is an excersice
for the reader to determine how many iterations there would actually be if
they care.