Given a list of cities, what is the shortest route to visiting them all just once and returning to the starting point?
Seems like a simple enough issue, right? Yeah, the problem itself is simple. Easy to explain and all that. The solution, however, is a different story. While, of course, you can easily write a program that goes through all possibilities and then picks the one with the shortest route, it’ll be far from efficient. Especially once you get to larger lists of locations, the time it’ll take your program to run through all the options will increase dramatically.
I won’t bore you with the math behind it all, but there’s already been a lot of research done on this. May seem a bit odd at first, but this problem (rather, its solution) has a very broad range of applications, such as logistics, the manufacture of microchips, or even DNA sequencing. It doesn’t have to be salesmen and cities, it could be electricity and solder points, for example.
There’s actually a couple of prizes floating around for whoever can come up with an algorithm more efficient at solving this problem than the current “best” one. It isn’t exactly my domain, but I’d like to give it a shot sometime! Not expecting to make a breakthrough or anything, but it may be cool as an educational project.
And I may already have a “mathematician” in reach to collaborate with.