Heres another famous problem we used to solve in college :)
Travelling salesman problem - Problem Statement:
Given a number of cities and the costs of travelling from any city to any
other city, what is the least-cost round-trip route that visits each city
exactly once and then returns to the starting city?
How would you solve this in your favorite programming language?
IIRC, it's not the problem isn't solvable. It's that the complete solution has a largish big O value. But if you further define the problem such that you don't have to arrive at the optimum solution but can stop once you find a solution that's close enough, it's no big deal any more.
You used to solve the TSP in college?
EDIT: Since you mention you went to school in India I'll add that we only study the TSP here in the US. We've made some progress, as you point out, but we haven't quite solved it yet. :)
If you solved TSP in college, you'd be living the life in some sunny island right now. No, scratch that - you'd own some sunny island. TSP is NP-complete, which means we can only approach the optimal result in acceptable time for bigger problems.
The challenge isn't solving it, but it's solving it in less than exponential time. If that was what you used to do that college then publish your results and prepare for a nobel prize :-)
The easy solution is to find all the possible routes and then pick the shortest one. I've seen all kinds of other solutions, from neural networks to genetic algorithms. But those just get a good solution, not the best.
Use DNA. These guys used the fact that DNA can be replicated exponentially to solve an NP-complete problem in polynomial time. For a sufficiently large number of cities, this technique would be faster than any approach on a deterministic computer.
I agree with Bill here. In the wikipedia article you quoted is the answer to your Question Or so sum it up: If you have to solve the problem for any size of map, any layout of map - Dont bother. You will be dead before the calculation is done.
For specific sizes of maps and/or specific layouts it may be solvable.
But I'd like to see the collage where you "solve" TSP.
I agree that this is a bit of a silly question, there is no good programmatic implementation of a solution that would be short enough to throw up here.
That being said, I HAVE seen some pretty neat good-enough solutions using neural networks and genetic algorithms, here's an example.
Notwithstanding, if you get asked to solve TSP in an interview and you are not Alan Turing or Van Neuremburg resurrected you should probably run run run.
Well, i agree to the point that we didnt really SOLVE
But comeon guys, have you not done this exercise in college?
FYI: I studied in india, and this will be one of the exercises in CS major in any college.
What sort of answer are you looking for in an interview when you ask this question? From the perspective of an interviewee my first response would be to ask what sort of solution are you looking for, what size the input set would be, and what type of running time are you looking for?
If the response was that you wanted the running time to be to be O(n^2) with no restriction on the input set size then as an interviewee I would likely wonder if it is a trick question or not.
However, if we are talking about a restricted set size, for example no more than 10 cities, then the simplest one to demonstrate during an interview would be to use a combinadic algorithm to generate the possibilities and then run through them to find the one that is the smallest. It's not going to win any awards for speed. But if the size of the input set is limited then even an inefficient algorithm is going to seem "fast" due to the speed at which modern computer operate. Another justification for this is that if the input set is limited then there is no point in spending a significant amount of time to research a faster solution when the problem is known to be NP-Complete.