Thread: greedy algorithm for TSP

1. Member
Join Date
Dec 2009
Posts
59
Rep Power
0

greedy algorithm for TSP

Hello
I want to implement greedy algorithm for solving travelling salesman problem and really I face problem in implementing this in java I want to find all suboptimal solutions I mean if two cities(a, b) have the same distance the first suboptimal must take city a and from city a taking the next near city and the second optimal solution is taking city b and then taking near city to b and so on

I have tried for about 3 days and I really feel upset:(
I have made the solution that just take one solution and ignore the remaining but really I want to find all optimal solutions

I really need your advice how to do it

thanks alot

2. By definition a greedy algorithm will not always find an optimal solution if the search space isn't convex; you have to supply more details w.r.t. the problems you're experiencing. An example of a greedy TSP finder runs as follows: for the current last point in the tour find a city closest to this point and not yet visited and add it to the route. If the new city equals the starting point and all cities are visited then stop. An obvious example why a greedy algorithm fails is this:

Java Code:
```from to   cost
---- ---- ----
A    B      10
A    C     100
B    D    1000
C    D       1
D    A       0```
A -> B -> D -> A turns out to be much more expensive than A -> C -> D -> A

kind regards,

Jos

3. Member
Join Date
Dec 2009
Posts
59
Rep Power
0
ok thanks for the reply
as you said greedy algorithm is not always find the optimal solution
but I want to find all sub solutions
for example
if the man in city a:
from to cost
---- ---- ----
A B 10
A C 10
B D 50
C D 1
B A 30
As you can see distance between A and B is the same as distance between A and C so in that case
the first solution is:
A->B->D->C->A
the second solution will be:
A->C->D->B->A
I mean if there is two cities with the same distance first I find the solution 1 with the first city , then find the second solution with second city
As I said before I can only find the one solution, unfortunately I'm not able to find all solutions
I really appreciate any help
thanks alot

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•