Results 1 to 3 of 3
  1. #1
    sara12345 is offline Member
    Join Date
    Dec 2009
    Posts
    59
    Rep Power
    0

    Default 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. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,302
    Blog Entries
    7
    Rep Power
    20

    Default

    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. #3
    sara12345 is offline Member
    Join Date
    Dec 2009
    Posts
    59
    Rep Power
    0

    Default

    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

Similar Threads

  1. Help with an Algorithm
    By Manfizy in forum New To Java
    Replies: 22
    Last Post: 07-03-2009, 07:16 AM
  2. O(log n) algorithm help !!!!!!
    By itseeker87 in forum New To Java
    Replies: 8
    Last Post: 09-09-2008, 05:12 PM
  3. Help with algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 10:26 PM
  4. Help me with this algorithm
    By Marcus in forum Advanced Java
    Replies: 3
    Last Post: 07-02-2007, 01:30 PM
  5. Help with Algorithm
    By Daniel in forum Advanced Java
    Replies: 2
    Last Post: 07-02-2007, 05:51 AM

Posting Permissions

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