Results 1 to 3 of 3

Math Help - Any progresses in solving TPS?

  1. #1
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1

    Any progresses in solving TPS?

    What is the best algorithm for solving a general TPS problem these days? I've heard they've solved the problem with finding the shortest path through all villages in Sweden or something like that. Anyone who knows if that is possible with today's techniques?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by TriKri View Post
    What is the best algorithm for solving a general TPS problem these days? I've heard they've solved the problem with finding the shortest path through all villages in Sweden or something like that. Anyone who knows if that is possible with today's techniques?
    Do you mean the "Traveling Salesman Problem"?

    This is an example of an NP-complete problem.
    Thus algorithms are inefficient.

    Here are two.
    Dijkstra's Algorithm.

    Floyd-Warshall Algorithm
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by TriKri View Post
    What is the best algorithm for solving a general TPS problem these days? I've heard they've solved the problem with finding the shortest path through all villages in Sweden or something like that. Anyone who knows if that is possible with today's techniques?
    Simulated annealing will give a "solution" good enough for practical
    purposes. Otherwise as ImPerfectHacker said.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Solving for x: A/sin(x)=B/sin(C-x)
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: May 1st 2011, 07:07 AM
  2. Solving for X
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 27th 2011, 10:44 PM
  3. [SOLVED] Solving a DE
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: January 6th 2011, 07:41 AM
  4. Need help solving for x
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: January 22nd 2008, 01:12 PM
  5. Replies: 3
    Last Post: October 11th 2006, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum