Post by xcessive on Nov 3, 2012 9:13:54 GMT -5
This problem is not for the faint of heart. I put it up here because I think the answer is hilarious. I highly doubt anyone will actually find an answer. Feel free to discuss the solution or yell expletives at me while claiming it can't be done. It can.
Mike is a traveling salesman who wants to visit a series of towns in an efficient manner before returning home. He doesn't mind if his path is sub-optimal, as long as it is 'good enough'.
Say we have a map of towns. Mike wants to visit each of these towns and come back to his home town in a single trip. He will be traveling cross country so the distance between towns is the straight line distance. Mike is happy as long as the total distance of his overall path is no greater than 2 times the optimal trip distance. He also never wants to visit any town more than once.
The input for the problem will be a series of positive integer points representing town locations as (x, y) coordinates. Obviously one can go from any town to any other town and the distance of the edge is the euclidean distance. So all graph edges are implicit.
eg.
2 4
123 56
342 12
The algorithm should be able to compute an answer for graphs with 10000s of nodes in a reasonable time--I don't want to be waiting all day. As such it is recommended to look for a polynomial time or better solution. As you can see this isn't the conventional NP-Complete traveling salesman problem.
Mike is a traveling salesman who wants to visit a series of towns in an efficient manner before returning home. He doesn't mind if his path is sub-optimal, as long as it is 'good enough'.
Say we have a map of towns. Mike wants to visit each of these towns and come back to his home town in a single trip. He will be traveling cross country so the distance between towns is the straight line distance. Mike is happy as long as the total distance of his overall path is no greater than 2 times the optimal trip distance. He also never wants to visit any town more than once.
The input for the problem will be a series of positive integer points representing town locations as (x, y) coordinates. Obviously one can go from any town to any other town and the distance of the edge is the euclidean distance. So all graph edges are implicit.
eg.
2 4
123 56
342 12
The algorithm should be able to compute an answer for graphs with 10000s of nodes in a reasonable time--I don't want to be waiting all day. As such it is recommended to look for a polynomial time or better solution. As you can see this isn't the conventional NP-Complete traveling salesman problem.