Traveling Salesman Problem

A couple of weeks ago, I heard about a mathematical problem, which is unsolvable. It peaked my interest. I researched about it and here's what I found out. This blog post is dedicated to all the math nerds out there.

Since the Renaissance, every century has seen the solution of more mathematical problems than the century before, yet many mathematical problems, both major and minor, still remain unsolved. Traveling salesman problem is one of those classic algorithm problems from the class of hard optimisation problems, which has been marked as unsolvable for over two centuries.

• Problem Statement 📜

Given a n number of cities, what is the most efficient route you can take to visit each city and come back where you started

• Sounds simple, why is it unsolvable 🤔

It sounds so easy, especially if you're working with computers. all you gotta do is check the distance of every round trip and shortest one is your answer. If you have n cities, you will have (n-1)! possibilities. We only count half since each route has an equal route in reverse with the same length or cost. so it's (n-1)!/2. So there you go! we cracked it?

Well that is not good enough. For obvious reasons, that way of solving the problem is known as the naive solution.

• The big WHY??

Throughout the years, scientists have come up with newer algorithms to solve the problem. In the early days of computer science, people figured out solutions to scenarios involving a specific number of cities, but a way to solve every traveling salesman problem with a single algorithm (that is, a single list of rules a computer can follow to find the solution) still remains hard to achieve. In the 1970s, mathematician Richard Karp published a paper that suggested we might never find the solution. He showed that the problem is NP-hard, which means that there will never be an algorithm to solve it 😲

Photo by Charles Forerunner on Unsplash