The Traveling Salesman Problem

Today I gave a brief talk at work describing the traveling salesman problem and its relation to NP-Hard and NP-Complete problems. Surprisingly, there weren’t too many code samples on the internets which actually demonstrated this fairly straightforward problem.

As such, I took a few minutes to go ahead and write a quick python script that demonstrates the problem and how quickly the complexity grows with the number of inputs.

I was going to write a mathematical proof that demonstrated that NP did in fact equal P, but there wasn’t a white board in the living room, so I couldn’t do the proof.