Thread: Efficient TSP

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    Efficient TSP

    I want to modify my current TSP program to be able to handle more vertices. Currently, I use a slightly modified Depth-first search to find the shortest path(s). It currently works, but it can only handle around 20-25 vertices. Any more than that, and the program takes too long to run.

    I recently learned about a technique where you do the following:
    1) Find any valid path.
    2) Switch two nodes in the path.
    3) Check to see if path is valid and is less costly than the previous.
    4) Repeat steps 2-3 until every switch has been tested.

    I tried this out on paper, and it seemed to work well. However, it would seem that in order to find an initial valid path, I would have to run my Depth-first search anyways. Once it found a path it could stop. However, if it never found one (no valid path exists), or if it found one on the next to last run through, it could take too long to run with many vertices. It also seems that since you are testing/switching for every permutation, that this algorithm would not be efficient (maybe i'm wrong?).

    I would appreciate any suggestions. I'm just looking for a way (as simple as possible) to solve a TSP with a large amount of vertices (hundreds/thousands).
    I've read that the only way to solve a TSP with a large number of vertices is to use an algorithm that finds a near optimal solution. If this is the case, any recommendations for an algorithm?

    Thanks.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    There is an article here: http://www.ias.ac.in/currsci/nov251998/articles22.htm
    I have no idea if it's any good or not - as I've not studied the subject (and I expect that TSP -> Traveling Salesman Problem).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Cpro View Post
    I've read that the only way to solve a TSP with a large number of vertices is to use an algorithm that finds a near optimal solution. If this is the case, any recommendations for an algorithm?
    Simulated annealing tends to do well on this problem.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Most Efficient Way to Check a Variable Is A Whole Number
    By bengreenwood in forum C++ Programming
    Replies: 29
    Last Post: 05-28-2009, 01:33 PM
  2. Is std::map efficient for this problem?
    By dudeomanodude in forum C++ Programming
    Replies: 12
    Last Post: 04-10-2008, 02:15 PM
  3. What is more efficient?
    By swgh in forum C++ Programming
    Replies: 11
    Last Post: 10-18-2007, 04:03 AM
  4. Efficient Algorithm
    By purple in forum C Programming
    Replies: 10
    Last Post: 02-05-2003, 03:01 PM
  5. How do I write more efficient code?
    By minesweeper in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 11:08 AM