The Travelling Salesman (or Saleswoman) Problem
Poor Willy Loman Imagine you're a sales rep who needs to visit several customers scattered across the country. You want to visit each city just once, in the shortest time or distance and return to your home base. This is a widely studied optimization problem that has many applications. It is "NP hard" meaning optimal solutions to real world (big) problems can be prohibitively expensive in terms of computer resources, As a result, much work has been done to develop algorithms that get near optimal solutions in a feasible amount of time. I will cover several approaches to this problem using an example from [1] where a prospective college student wants to visit several college campuses across the US before deciding which to attend. All of the Python scripts and supporting files used for this this post can be found here . The example forms a "complete graph" i.e. all colleges are connected to every other college. All of the Python ...