Discussion prompt. Hopefully I’ll get to the real post tomorrow.
(And no bonus points for nit-picking my geography.)
June 19, 2008
5 Comments »
RSS feed for comments on this post. TrackBack URI
Discussion prompt. Hopefully I’ll get to the real post tomorrow.
(And no bonus points for nit-picking my geography.)
RSS feed for comments on this post. TrackBack URI
Back when I was a bike messenger I had never heard of the traveling salesman problem. I did spend many a spare moment trying to solve permutations of it over the drowsy streets of Ottawa.
Only later would I find how difficult the solution really is. My personal solution was generally divide and conquer: do clusters and then make a big jump to the next cluster.
I have no idea of how optimal this is.
Comment by Ben — June 19, 2008 @ 2:14 pm
I really couldn’t say how optimal that is : ) It would depend a lot on the structure of the map, certainly, but you’d think you could reduce it into clusters, when *BAMF* the optimal solutions actually take one stop from each cluster at a time. But then, the only experience I have with the problem were stumbling attempts at writing genetic problem solvers. Very stumbling, and only occasionally solvers.
Though … now that I think about it, the crux of the issue is really how you divide into clusters. Just taking groups locally close nodes is one thing, but there may be some kind of graph theoretic property that would allow you to partition the nodes in such a way as to make analyzing clusters, then the whole, yield more optimal solutions. Hmmm.
Anyway, good guess, but that’s not the problem at hand : )
Comment by Fox — June 19, 2008 @ 4:42 pm
“Though … now that I think about it, the crux of the issue is really how you divide into clusters. Just taking groups locally close nodes is one thing, but there may be some kind of graph theoretic property that would allow you to partition the nodes in such a way as to make analyzing clusters, then the whole, yield more optimal solutions. Hmmm.”
I’m reminded of Minimum Spanning Tree solvers for matroidal graphs. If such an algorithm had a provably correct way of doing so, then it would probably be somewhere in the ballpark of the P versus NP problem, likely on the side of the unexpected solution (i.e., that P does equal NP and that there are efficient solutions to all NPC problems).
Looking forward to the post. BTW, we haven’t had a heart to heart in a while, so we should probably hook up.
Comment by Tyler DiPietro — June 21, 2008 @ 2:11 am
Seattle and Portland are much too large, Miami much too small. And how about Helena? The view from Narita today…
Comment by Dad Fox — June 21, 2008 @ 6:02 am
[...] prompt I left the other day is the graph representation of the lower 48 United States (47, actually. I [...]
Pingback by Four Colors and a Theorem « Foxmaths! 2.0 — June 24, 2008 @ 6:05 am