Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Google Businesses The Internet

Where's the Traveling Salesman for Google Maps? 125

Posted by samzenpus from the waffle-house-mod-soon-to-come dept.
Komi writes "Has anyone tackled the Traveling Salesman Problem with Google Maps or any other online mapping tool? I've searched, but can't find anything. To me this seems like such an obviously cool function. I'm not up to date on algorithms, so perhaps this isn't really tractable for large values of n. But for small numbers (maybe up to 5), this could at least be brute-forced. I would love to use this when I have errands to run, and I want an overall optimal route. So if this hasn't been done, someone please do it!"
This discussion has been archived. No new comments can be posted.

Where's the Traveling Salesman for Google Maps? More

Where's the Traveling Salesman for Google Maps?

Comments Filter:

  • He is out, travelling? (Score:4, Funny)

    by G3ckoG33k ( 647276 ) on Thursday January 10, 2008 @05:00AM (#21981296)
    He is out, travelling? Or just too small to be seen in that resolution?

    I have no idea.
  • Yahoo's map service has some sort of multiple destination feature... might be what your looking for.
  • By "tackle the problem", do you mean "make it not NP-hard anymore"? If so then, no, it has not been "tackled". However, algorithms exist that approximate a solution to the problem, as is the case with many NP-hard/NP-complete problems.

    • Re:"tackel the problem" == "make it not NP-hard"? (Score:4, Informative)

      by dintech ( 998802 ) on Thursday January 10, 2008 @06:18AM (#21981654)
      He's clearly aware of the intractability. From the summary, "This isn't really tractable for large values of n. But for small numbers (maybe up to 5), this could at least be brute-forced."

      And he's right. If you remember your computability and intractability lessons at Uni then you'll rember that TSP is quickly solvable for small values of n. Just like the summary states. Approximations are only required for larger values of n where the solution takes much longer to arrive at.

      • Re: (Score:1, Interesting)

        by wbren ( 682133 )
        Agreed about approximation methods only being necessary for large values of n. I took it for granted that n was large, as it's not very interesting for n=5, for example. Furthermore, I think the summary was poorly phrased. I interpreted it as primarily asking, "Can the TSP (general form) be solved with the help of Google Maps?", not "Why isn't feature in Google Maps?". I suppose the latter is what the original submitter was really asking, but in that case, it really should not have been on /. to begin with

        • Re: (Score:2)

          by dintech ( 998802 )
          I'm not sure why your comment has been moderated into oblivion but I understand what you mean. The general case is more interesting.

          • Re: (Score:2)

            by wbren ( 682133 )
            Regarding my posts being modded into oblivion, I think some people got offended by a comment I made regarding the Obama/Clinton story, and they decided to mod other of my posts down as some kind of petty revenge. The post was about Obama's strength with black voters and what that had to do with the outcome in New Hampshire (NH being overwhelmingly white). Since my original post kept getting modded back to +5 Insightful after they modded it down, they moved on to other posts by me... Just a theory, but that'

            • Re: (Score:2)

              by dintech ( 998802 )
              You should know better than to anger the 'hive mind'. :P
            • Downmodding should at least require the downmodder to answer an automated question about the downmodded post, like "which 5 words are missing from this sentence from the post...". It would probably discourage a lot of idiots.
        • I would bet that when running around most people visit 5 or less destinations. Therefore, the feature would be very helpful for a lot of people.

          • Re: (Score:2)

            by unitron ( 5733 )

            I would bet that when running around most people visit 5 or less destinations.

            And I would bet that they visit 5 or fewer.

      • Re: (Score:3, Interesting)

        by CastrTroy ( 595695 )
        I remember that they had heuristics to give very close to the best path with a lot less computation for figuring out the actual correct solution. They used it for figuring out paths for things such as machines assembling circuit boards. Following the shortest path means they can produce them faster.

        • Re: (Score:2)

          by rjh ( 40933 )
          ObDisclosure: I am a graduate student doing research into heuristic approximation algorithms. I'm more the implementation side of the crew than the research side of the crew, but hey. :)

          For a very large portion of the problem space, TSP is really quite tractable once you use a proper heuristic. I've seen damn near perfect approximations to a 100-city TSP problem computed in under ten seconds.

          Good heuristics are just frighteningly good.

          If you want to see an example of this, take a look at Djinni [uiowa.edu], which imp
      • Well where's the fun in that? Someone should implement a genetic algorithm to find route. Input the points today, then come back tomorrow to see what it comes up with :)

        • Someone should implement a genetic algorithm to find route. Input the points today, then come back tomorrow to see what it comes up with :)

          Actually, we did exactly that in the AI class I took last semester. My GA implementation was still able to find optimal solutions for 49 cities (a 7x7 grid) in about 3 minutes fairly regularly.

          • How did you know it was optimal?

            • For convenience, we used a special case of the TSP, where all cities are considered to be in an NxN grid with uniform spacing (of 1 unit) and the cost to move from one city to another is the Euclidean distance between the two. This makes the optimal cost quite easy to calculate by hand, especially since it follows an obvious pattern (9.414, 16, 25,414, 36, ...).

    • Comment removed based on user account deletion

      • Re: (Score:2)

        by fyonn ( 115426 )
        My GPS handles this whole problem for me, I just feed it a few waypoints and it figures out some nifty turn by turn navigation to calculate the shortest distance or fastest travel time depending on traffic congestion, speed traps and limits, and so forth.

        ahh, but I'm guessing you feed it waypoints in the order you want them, the GPS doesn't tell you the best order for the waypoints?

        the travelling salesman problem here would be where you could enter in say 5 desintations and your starting point, and the appl

      • Re: (Score:2)

        by Andy Dodd ( 701 )
        Different problem.

        Routing through point A to point B in a directed graph is a solved problem - Dijkstra's algorithm isn't that bad computationally, and there are others that have the same worst-case performance as Dijkstra but better average performance (such as I believe A*).

        What your GPS supports is just applying the same problem sequentially. Given points A,B,C,D,..., visit them in the user-specified order. A to B, B to C, ...

        What the article poster wants is:

        Given starting point A, what is the best way

      • Re: (Score:2)

        by harrkev ( 623093 )
        Which GPS's have this? I got a Garmin StreetPilot 530 (around $400 a year ago), and it does NOT do anything like this.

  • Do it the old way (Score:4, Funny)

    by KiloByte ( 825081 ) on Thursday January 10, 2008 @05:11AM (#21981346)
    Well, I haven't heard about any Nobel prizes or Fields medals awarded to Google's employees recently.

    So, because of network latency, the best you can do is:
    1. run Google queries for n^2 routes for all node pairs
    2. solve the Travelling Salesman problem yourself

    Because there is no way to go A->B->C faster than A->B + B->C if you want to visit B on the way, asking Google/Yahoo/etc for A->B->C routes is pointless.

    Of course, step 2. is left as an exercise to the reader.

    • Re: (Score:3, Insightful)

      by voss ( 52565 )
      The problem with simple math solutions like this one is that they make assumptions such as all else being equal.
      In the real world it doesnt function like that. A mathematically optimal route may not work because of real world
      conditions(traffic, construction, everybody else trying that same route) or it may work somedays but not others
      or some times of the day but not others.

      • Re: (Score:1, Insightful)

        by Anonymous Coward
        dude, you just need to include those circumstances into the distance function! Route planners routinely do this, where the actual distance function is really more like a function of the actual distance travelled and the time it takes to travel down that road (according to a typically simple model of the possible travelling speed).
    • I think you've probably struck on the real reason no-one has been doing this...

      According to the Google Maps API Terms of use, you're limited to 15,000 queries per day.

      So if you're doing even 5 nodes, then that's you down to 600 users per day (15000/(5^2)).
      10 nodes, and you're only going to be able to process 150 users per day!

      • It's also not the sort of thing you normally plan multi-node trips around. If you have to pick someone up on the way to the airport, you can't visit the airport first then pick the person up - these sorts of things are just shortest-path problems, rather than TSPs.

        Although this would be a nifty feature for the few times that the order doesn't matter.

      • Traveling salesman is (n - 1)! / 2, so you could do 1,250 users with 5 nodes. Of course, with 10, it would take you a little over 12 days to complete a query.

  • Acceptable solutions (Score:3, Interesting)

    by Wiseman1024 ( 993899 ) on Thursday January 10, 2008 @05:16AM (#21981360)
    Given a reasonable number of points, say, 300, You can't easily find the best solution, but you can find a "good enough" solution that'll be little worse than the best possible solution. One way to do so is to keep a list of the points in any order, calculate the length of visiting them in that order, and choose random portions of the list to try in inverse order and see if you're saving distance. After many iterations of trying that without getting an improvement, you consider the solution good enough.

    • Re:Acceptable solutions (Score:5, Informative)

      by jiushao ( 898575 ) on Thursday January 10, 2008 @06:05AM (#21981596)
      Interestingly this is not really the case in the general problem. Notably the travelling salesman problem is not in APX unless the hamiltonian path problem is in P. That is, unless P=NP, there exists no algorithm which can give an approximation of the solution to the travelling salesman problem which is guaranteed to be within a constant factor c of the correct answer.

      However, in graphs upholding the triangle inequality (that is, if the distance A->C is d then the distance A->B plus B->C is at least d) there are algorithms that do give guaranteed good approximations. So in the real world you are correct.

      As an example of how approximations tend to fail we can look at a case where the greedy inversions of pairs you suggest breaks down (the lameness filter screws up my fine ASCII art. The numbers now signify nodes and the initial path runs in number order):

      | 0 3 4 7 8
      |
      |
      |
      |
      | 1 2 5 6 9
      Now, this is not a good path through all the points on this map, but flipping the order of any pair will only make the path worse. The correct solution would be much shorter, just going straight through the top and bottom rows. But that path cannot be reached by greedingly inverting the order of pairs.

      • Re: (Score:2, Insightful)

        by TheRequiem13 ( 978749 )
        Not that I'm saying his method is foolproof, but your example does not show its failure. You say any pair will make the path worse (true) but gp is saying portion, which can be as little as a single pair or as much as the entire path less an endpoint.

        In your example, if you reversed the visitation order of the sub-path 0-1-2 you would remove one vertical jump, thereby improving the path.

        | 2 3 4 7 8
        |
        |
        | 1 0 5 6 9

        is obviously better than

        | 0 3 4 7 8
        |
        |
        | 1 2 5 6 9

        Genetic algorithms improve this type

        • Re: (Score:2)

          by jiushao ( 898575 )
          True enough, but if we let the algorithm look at any subsequence of at most n elements we can still trip it up in exactly the same way as long as we know what n is. It is in fact a simple generalization of the previous example, lets just instead rearrange it as:

          | A C E G
          |
          |
          |
          | B D F H

          where we say that A is a cluster containing points 0 and 1 close together, B is the cluster of point 2 and 3 close together and so on. This is still the same problem as before, but now we can generalize the key point in it.

          I

          • Of course this only works if n is restricted to be less than the size of the problem. Otherwise the original criticism still stands that this doesn't disprove the original post. I'd stop digging there if I were you as trying to prove anything about this problem / solutions tends to get difficult quickly :)

            • Re: (Score:2)

              by jiushao ( 898575 )
              Hehe, but if you take n to be the size of the problem then the originally suggested algorithm collapses into being "look at all nodes in a path and reorder them in some way". I already let slide the fact that once we have more than a pair we need a way to pick how to reorder the nodes. First and foremost though; I think that if you intend to be on the side that suggests way to approximate and/or solve a problem that has proven to be NP-hard to solve and approximate you are the ones that should stop digging.
      • The GP suggested reversing the order of portions, not pairs. Now, whether that distinction is enough to make the algorithm "good enough" I don't know.
      • Back when I was in grad school ~30 years ago, Christofides's algorithm could get you within 3/2 of the optimum distance on graphs where triangle-inequality holds, and it's interesting to see that that's still basically the optimum. (I forget what speed the matching-problem part looks like; a brief Wikipedia scan looks like it's something like N**2*logN or N**2.5? And of course you only run the match on the odd-order vertices in the spanning tree, so that's going to be a lot smaller than the ones in the or
  • Oh, it's easy to solve the traveling salesman problem: you just need to prove that P=NP.

    Until that, since TSP is NP-Complete, there's no way to do deterministically on large data sets: it's computationally intractable (and, i guess, Google Maps data set it's *definitely* huge :-) )

    • Re: (Score:3, Informative)

      by sigmoid_balance ( 777560 )
      First of all TSP is not NP-Complete it is NP-hard. This means we couldn't find a polynomial algorithm that reduces TSP to a NP-Complete problem: it either exists, but it wasn't found, or it doesn't exist and then it's even harder than NP-Complete. Second, intractable means "unsolvable by a Turing Machine in a finite time", which is not true, since you can find a naive algorithm that takes a lot of time, but finishes. The algorithm is like this: generate all possible paths in the graph and test if it's a mi

      • Re: (Score:3, Informative)

        by psmears ( 629712 )

        Second, intractable means "unsolvable by a Turing Machine in a finite time"
        No, intractable usually means not solvable with the resources that are available in practice [wikipedia.org]. Your definition corresponds more closely to undecidable [wikipedia.org].
      • TSP is most assuredly an NP-complete problem.

        The definition of NP-completeness--or at least one of them, you can define it in several different (but all equivalent) ways--is a problem which exists in NP, but is also NP-HARD.

        You appear to not understand complexity theory. I would suggest brushing up on it.

        (ObDisclosure: I am a graduate student in CompSci. One of my research areas involves the TSP. I have spoken at CodeCon 2006 and OSCON 2006 on new approaches in heuristic approximators for NP-complete alg
  • I don't see the point at all.

    Maybe I misunderstand the question.

    If you want to select some number of real cities, just go ahead and select them and figure out the distances from each city to each other city. Google Maps might help figuring out the distance, but that's about it.

    It seems rather pointless, though. How many salesmen do you know who travel in the manner in the problem? The problem is important, but not for real life traveling salesmen.

    • Re:What's the point? (Score:5, Insightful)

      by etymxris ( 121288 ) on Thursday January 10, 2008 @05:50AM (#21981522)
      Well salesmen rarely do this. However, imagine a UPS driver delivering 40 different packages to various parts of a city. It would be quite useful to automatically determine the order of delivery ahead of time in such a way as to minimize time and distance. As indicated in other replies to this thread, good solutions are much easier to come by than perfect solutions. The difference between the two solutions is probably not great enough to justify the immense computation power required to churn out the perfect solution. The perfect solution would probably end up costing more since you have to figure in the cost of energy used to compute it.

      The submitter just wanted to be able to use google maps to find the optimal route between points on an errand run. If you limit the number of nodes to 10, then perfect solutions remain tractable. And I doubt most people would have more than 10 errands to run at once.

      On a related note, I just had a Mormon missionary knocking on my door last night. Perhaps we could rename this the traveling Mormon problem. I'm sure they would appreciate automated itineraries that minimize the burden on their poor soles.
      • I thought part of the reason Mormons knocked door to door was to test the faith of their members. So in their case you should look for a route that increases the burden on their soles.

      • Re:What's the point? (Score:4, Insightful)

        by TheLink ( 130905 ) on Thursday January 10, 2008 @07:24AM (#21981926) Journal
        I believe in the USA, UPS picks routes which reduce left hand turns.

        Delivery people would rather have the fastest time rather than the shortest distance.

        Or at least one that makes them more money in the long run (which is slightly different from "saves them more money" ).

        • Re: (Score:2)

          by Goaway ( 82658 )
          That is just a change of metric. The problem is still the exact same travelling salesman problem.
        • Yes, like what goaway said, that's the same problem, just assigning a higher penalty ("distance") to parts of the graph ("edges") involving a left turn. Same problem, different numbers.

        • Re: (Score:2)

          by SQLGuru ( 980662 )
          TSP deals with weighted edges. Edge weights can be determined by any means appropriate for your problem. For example, the travelling UPS driver would be looking at shortest time....the travelling consultant would be looking for shortest flight durations.....the travelling small business owner would be looking for cheapest flights......the travelling grandma with her turn signal on would be looking for the highest annoyance factor. Just devise a formula that computes a value that represents the goal. Dis
      • Actually, this is a very real problem, with very real applications.

        Consider:
        My flatmate (translation: person I share a flat with) was at one time a courier. When he arrived at work (at 5 am) he'd be given a number of packages to be dropped off. Usually around 40, all within his "patch", a postcode based area. He'd usually then spend the next hour in the back of his van grouping them together into groups. Given that he was expected to come back for a second load in the early afternoon, this meant he usually

        • Re: (Score:2)

          by fbjon ( 692006 )
          Pretty good, except you'll have a guaranteed long ride back home every time.
          • I can see how you would think that.

            On reflection, I may have missed a few points out.

            The starting linked lists consists of the depot as both the origin and the final destination. It may be worth preparing a few core stops, say 2 or 3 stops that are furthest from the average / centre.

            Bear in mind that this was a courier, operating in a postcode / suburb based area, and returning to base, the local airport.

            While not being a perfect solution, it's much better than the one in place, which is very random - possi

      • Well salesmen rarely do this. However, imagine a UPS driver delivering 40 different packages to various parts of a city. It would be quite useful to automatically determine the order of delivery ahead of time in such a way as to minimize time and distance. As indicated in other replies to this thread, good solutions are much easier to come by than perfect solutions. The difference between the two solutions is probably not great enough to justify the immense computation power required to churn out the perfect solution. The perfect solution would probably end up costing more since you have to figure in the cost of energy used to compute it.

        I'd suggest a variant, the "real-time travelling salesman problem": You have a computer in your car, and you enter all the destinations into your computer. Then it starts calculating, and as soon as it spits out the first destination, you go there. Once it gives you the second destination and you have reached the first one, you go to the second destination. The goal is to minimise the total time.

        Here the software would have to take into account not only the driving time, but also the calculation time. It

      • Actually, UPS *does* do route-planning using a sophisticated algorithm. It even tries to minimize left turns:

        http://slashdot.org/article.pl?sid=07/12/12/1355219&from=rss [slashdot.org]
      • "The difference between the two solutions is probably not great enough to justify the immense computation power required to churn out the perfect solution"

        The problem with the salesmen problem is that even if you did have the time, real-time events would eventually fuck with teh solution anyway, at some point there is such a thing as "good enough" until we get a computer that is equal to a god in intelligence and computational power.

    • I don't see the point at all.

      Maybe I misunderstand the question.

      Here's a good example. Let's say you're hired by a company to market to beer breweries and brewpubs, and you were arranging personal visits in order to demonstrate your new beer widget to them. Take a look at this map:

      http://beermapping.com/maps/maps.php?m=northcentral [beermapping.com]

      Now quickly find the most optimal route to visit all those locations in the least amount of time. The number of permutations are basically n! (that's n factorial: n * n-1 * n-2 * ... * 3 * 2 * 1) where n is the number of locations. Basica

      • Re: (Score:2)

        by eric76 ( 679787 )
        I assume that you tell them you are coming and have appointments set up based on what is convenient to you and to the customers. In that case, the ordering is determined more by the appointments than whether or not you can save a few miles overall.

        You might also have preferred places to spend the night. How about if you have a favorite restaurant along the way and you want to order your visits so that you can go there for supper one night of the trip? How about if an old friend lives near one brewery and

        • In other words, in real life, the most optimal route is rarely going to be the shortest route except in the simplest of cases.
          Very true. For a traveling cold call salesman who has no life, this could be applicable. More suitable examples might be the traveling archaeologist looking at potential dig sites, or a contest where someone had to visit 200 pubs and collect coasters from each in the least amount of time possible... the traveling drunkard perhaps.
           

          • Re: (Score:2)

            by eric76 ( 679787 )

            the traveling drunkard perhaps.

            I like that. It made me laugh pretty good.

            However, his best path might still be suboptimal.

  • Just use a neural net in conjunction with Gmaps. Hook up the system to a GPS tracker and train it for a few weeks. Then link up GMaps and you get a pretty damn accurate system to suggest routes and points to the salesman.

    • Re: (Score:2)

      by eric76 ( 679787 )
      Neural nets are useful for the proper application, but I don't see how this could be anything close to being able to use a neural net.

      But since you suggested it, I'm willing to give you the benefit of the doubt.

      Please fill in a few details such as the number of inputs and their form, the number of levels, how the output will be interpreted, ... .

    • Re:Use a neural net (Score:4, Interesting)

      by arivanov ( 12034 ) on Thursday January 10, 2008 @06:10AM (#21981618) Homepage
      As the saying goes artificial intelligence is no replacement for natural stupidity.

      My old Advanced CS professor in high school gave an even better explanation to one geek who was trying to use a similar approach to minimise his search field in a classic travelling salesman problem: "Dear, you cannot have your dick in both hands or your soul in paradise, you have to chose: it is either a full enumeration or you can express it as a sorting problem".

      If you deal with the original travelling salesman problem, neural net will not help you by any means. If you modify the problem so it can be solved by means different from brute force you might as well solve it properly. In that case it is no longer the classic "travelling salesman" though.
    • Although it can be considered a branch of AI (at least it was in my University), what you want for this kind of problem is Simulated Annealing [wikipedia.org], not necessarily a full Neural Network.

      Bob

    • Just use a neural net in conjunction with Gmaps. Hook up the system to a GPS tracker and train it for a few weeks. Then link up GMaps and you get a pretty damn accurate system to suggest routes and points to the salesman.

      Well, I suppose an experienced salesman can plan pretty good routes, but I thought that the question was about using a computer for this ;).

  • We can do much better than that solving TSP nowadays. While NP--complete it doesn't mean that you're reduced to 5 cities problems:

    1) You can use Heuristic Search to look for solutions of quite big TSPs. One very simple heuristic is the Maximum Spanning Tree heuristic. Not so simple is the AP heuristic. Do a search on scholar.google.com with the terms "TSP" "Heuristic" "Search" for the state-of-the-art. Note that this approach allows you to find the optimal tour.

    2) For a practical application I doubt you'll

  • Scientific American Article on this (Score:3, Insightful)

    by Precipitous ( 586992 ) on Thursday January 10, 2008 @05:51AM (#21981524) Journal
    The Fastest Way to Get There [sciam.com].

    The approach discussed works on "... a simple premise: driving somewhere usually requires crossing major intersections that are sparsely interconnected. "

    • Re: (Score:2)

      by mdfst13 ( 664665 )
      That's not the Traveling Salesman problem (TSP); that's just route finding. Google maps already supports route finding between two points (which is what the Scientific American article is discussing; cheaper/better route finding). What the submitter wants is destination ordering. Given a list of n destinations (where the submitter is limiting n to five or less), in what order should you go to the destinations to minimize the overall driving distance (or whatever metric). Route finding can be part of the

  • Interesting question.. But sorry no answer from me (Score:3, Interesting)

    by tanveer1979 ( 530624 ) on Thursday January 10, 2008 @06:04AM (#21981586) Homepage Journal
    When I went to see Yosemite, and had just a day(half actually), I could not figure out in what sequence to follow so that I see most of the spots. such a application for google maps will be just great!

    • Re: (Score:2)

      by 12357bd ( 686909 )
      The problem is that for real uses distance alone is not the sole/main factor, route quality, trafic conditions, horaries, etc are other factors to weight in if you really want to make or plan a real travel.

  • Right here... (Score:5, Insightful)

    by jberryman ( 1175517 ) on Thursday January 10, 2008 @06:08AM (#21981606)
    No, I won't link you to the site. It's the first hit when you google: travelling salesman google maps You fail at the internet.
  • You don't need to traverse every road connecting your errands, since you're not selling door to door along the way.

    • Re:NOT a travelling salesman problem. (Score:4, Insightful)

      by cnettel ( 836611 ) on Thursday January 10, 2008 @06:43AM (#21981744)

      You don't need to traverse every road connecting your errands, since you're not selling door to door along the way.
      TSP is not a filling problem. You only need to traverse every road when doing a brute-force TSP search for an arbitrary graph, since you cannot assume any specific distance constraints (like the triangle inequality or a close-to-planar structure). The problem itself is just about getting a(n optimal) permutation of the nodes. I can't imagine why you were modded insightful.

    • Re: (Score:1, Informative)

      by Anonymous Coward
      to clarify: what's called the travelling salesman problem [google.com] is not the travelling salesman's problem. math should call the former the visiters' problem (or something), though this is your problem as well (with errands). there's no efficient algorithm for it.

      real travelling salesman have a solved problem [wolfram.com]: walking along each road once, selling to each house along the way.

    • Re: (Score:3, Insightful)

      by david_thornley ( 598059 )

      No, that would be the Chinese Postman Problem, which is solved (provided you have a good linear programming engine available). There are variants that at least weren't solved when I was working on it ten years ago, such as the Windy Postman Problem (where the cost to go from A to B isn't necessarily the same as that to go from B to A), which I was attacking with simulated annealing. Awful slow to run, though. I haven't heard of problems in that family being classified as NP, but as I said I've been out

  • You could even try and make the process fun making it visual and have swarms of ants running round your neighbourhood spreading virtual pheromones over your neighbours' garden all in the name of finding a good route to use!

  • Huh??? I don't get it (Score:3, Informative)

    by zappepcs ( 820751 ) on Thursday January 10, 2008 @09:08AM (#21982430) Journal
    The submitter obviously understands Google... first link if you search Google for "map 'traveling salesman'" gives you http://gebweb.net/optimap/ [gebweb.net] ... is that what you mean?

  • J.F.G.I. (Score:4, Informative)

    by portnoy ( 16520 ) on Thursday January 10, 2008 @09:40AM (#21982662) Homepage
    "Sure I could just google it myself, but if I post to Slashdot I waste *everyone's* time!"

    http://gebweb.net/optimap [gebweb.net]
  • About 20 years ago, I had an IBM PC compatible computer, which ran at a whopping 10MHz, instead of the standard 4.77 MHz.

    Innocent as I was, I thought the traveling salesman problem could easily be solved by a computer. I wrote the code, and gave it a "standard" traveling salesman problem from a book. 60 CPU-seconds later, I got the optimal answer. It was a 100 city (or was it 133?) problem.

    The book said that a pruning brute force algorithm had been run on a CRAY supercomputer. It had come to the same solut

    • Re: (Score:2)

      by cnettel ( 836611 )
      The problem of TSP is not the n^2 aspect, but the 2^n aspect. While searching, you might have done 50 errands of the total 100. You need to know what those 50 are, as the number in itself doesn't tell what parts are left. Consider errands placed in a downtown area and some suburbs. A greedy method may tick off all errands in the center and then start zigzagging to the outside malls, rather than going in some radial/spiral manner that would be more efficient in total.

      In real-life problems, you can make some

      • Re: (Score:2)

        by rew ( 6140 )
        How many paths did you end up testing?
        I really don't remember.

        Thinking about it some more, some heuristics that I used depend on the problem being planar. This is an assumption that goes out the door once you have the route planner give the "cost" of each of the n^2 combinations of places.

        Some people "give up" the moment a problem has been proven NP-complete/intractible.

        In practise, someone running a couple of errands or delivering 10 or 20 club-newsletters, the n^2 part as well as the 2^n TSP problem is so

        • Re: (Score:2)

          by rew ( 6140 )
          Thinking about this some more. I used two "hill climbing" heuristics. For large problems you might need to start with several different random solutions to see if you achieve different end solutions. In practise, these heuristics converged on the one and only solution every time for the "small" (100 city) problem I tested.

          First, in your path, remove one city, and try plugging it in the route at another spot. This is n^2.

          Second, in the path, take two edges, AB and CD. See if the path with AC and BD is shorte

Slashdot Top Deals

I tell them to turn to the study of mathematics, for it is only there that they might escape the lusts of the flesh. -- Thomas Mann, "The Magic Mountain"

Close