The traveling salesman problem is a classic in computer science. It sounds deceptively easy: given any number of cities, determine the shortest path a traveling salesman would have to travel to visit them all. This video shows how the "obvious" solution — "well, just start somewhere and always visit the next closest town!" — doesn't hold up well against other approaches. (via @coudal)