Using Python to Solve Computationally Hard Problems

The Traveling Salesman Problem, an example of an NP-Complete task that is much more difficult than it seems on the surface, can be used to model such tasks as Printed Circuit Board design, job sequencing, and aircraft routing. This session will use the TSP to demonstrate Python’s capabilities in mathematical computation.

First, we will select a few of the algorithms available for solving it. We will then examine options within Python for implementing them, and discuss what makes a given solution best for the specific algorithm. Evaluation criteria will include runtime and the quality of the solution given.

An in-depth examination of the process of researching algorithms will be presented in the earlier session, Finding the Right Algorithm for the Job: Math Research for Non-Mathematicians.