But to be entitled to this discount, the Railways stipulates that you must visit the cities using the shortest possible train route. (I wonder who came up with this.) Many of you will immediately recognize this as an instance of the famous Travelling Salesman Problem.
TSP is a classic NP-complete problem, which means that it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities. Interestingly, when the number of cities is relatively small, humans are able to produce good quality solutions quickly. The solution of this particular TSP is therefore left as an exercise to the reader. The answer will be provided in the next post.
Letters have been assigned to the cities merely for convenience and have no bearing on the solution. The actual distance between the cities by rail is longer than the Euclidean distances. But the solution comes out to be the same in both cases. If you are freakishly particular, you can contact me for a table of the rail route distances between all the cities and I will happily oblige.
The first solution to intuitively strike you will very probably be the correct one. However, if you are interested in delving deeper, some hints are provided below.
- My starting point will be Calcutta (B), but that is irrelevant to the solution of the problem.
- The nearest neighbour heuristic, which may seem like the most obvious approach, goes as follows: start at some city and then visit the city nearest to the starting city. From there visit the nearest city that was not visited so far, etc., until all cities are visited, and you return to the start. But this heuristic often produces the wrong answer.
- A better approach is to start with a subtour, i.e. a tour on small subsets of nodes, and then extend this tour by inserting the remaining nodes one after the other until all nodes have been inserted. A good starting tour is the tour that follows the convex hull of all nodes. This is a reasonable choice since the sequence of nodes from the convex hull tour is respected in any optimal tour.
- If you want to write a program in Java to compute an approximate solution, you can find some useful pointers here.
13 comments:
Accha, how are the railway people going to verify whether or not the the route you've come up with is the shortest? How do they usually work this out? Maximum kota city-r jonye ei scheme valid? :)
B-C-F-I-H-G-E-D-A-B? Hah, puro random.
Seattle has just the hotel for traveling salesmen.
Haha, Tommy.
OH MY GOD!!!!! This is what happens to a man who is ENTIRELY Jobless. Thanks for letting me know. I shall guard myself against this! :-P
P.S: - But actually if I had the time / internet connection during the times that I do have time, I might have attempted to understnd what you are saying and maybe even attempt an answer. Who knows - I am constantly surprised by myself.
This is very Sinister. I thought you were writing about travelling but you're actually writing about MATHS (I'm guessing it's Math, couldnt read it, was it Physics instead? =P)
Yay, I'm in the blog! (sticks out tongue at rik, relegated to second place)
But this is fun. I think people should be jobless more often.
Also, http://xkcd.com/399/
@Opaline: It's more of a Computer Science, or rather computing problem, I would say.
@Shrabasti: I don't think they verify at all (see July 6 post). The scheme is valid for at most 8 break journeys, so I am just within the limit.
Thanks for trying to solve the problem. Looks like you were the only one who did. In the solution you proposed, B-C and D-A cross each other. But a route with crossed paths can never be the shortest route in a TSP. If you want, you can try to figure out why.
Hint: BC and AD are diagonals of the quadrilateral ABDC.
@IP: You could have tried to solve it intuitively. It hardly takes a few seconds, and the probability of guessing right is very high.
@scheherazade: Anasua, you appear before Rik because your names are in alphabetical order.
whoh....heard of the travellin salesman problem, my old math teacher mentioned it ...along with the four colour theorem, which is, informally speakin, "if you want fill the countries in a map so no two adjacent countries will have the same colour, then four colours is enough"
I just loved these stuff.
Oh yess, zey cross. Haha, I think the reason I suggested B-C was that I subconsciously remembered your first stop was supposed to be Bombay. :)
This is totally unrelated but it seems like Shrabasti has an interesting habit of spelling "th" with a "ze" (Ze Jhor, case in point). Are you Mexican? Que pasa?
Sigh. Must I be denied all of life's pleasures? :(
@ Lahiri-da: Lol, Mexican? I always thought "ze" sounded French. I like "ze'. I think it sounds cute, but not a lot of people would agree :S, haha.
Post a Comment