Using Python to Solve Computationally Hard Problems

Rachael Madsen (Optimal Design Software LLC)
Python
Location: D135
Average rating: **...
(2.67, 9 ratings)

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.

Rachael Madsen

Optimal Design Software LLC

Rachael has been using her mathematics degree in software development for more than 35 years. Her experience ranges from compiler design to terminal and computer emulation software, from database design and administration to medical diagnostic software, from nationwide order management and inventory control to workflow management for a web-based business. In the process, Rachael has helped many people understand the advantages of using mathematics in their software designs.

Comments on this page are now closed.

Comments

Picture of Alex Martelli
Alex Martelli
07/19/2012 9:23am PDT

good materials, presentation unfortunately not quite as smooth (maybe the lack of the “right algorithm for the job” earlier talk hampered the presentation flow a bit).

Sponsors

For information on exhibition and sponsorship opportunities at the conference, contact Sharon Cordesse at (707) 827-7065 or scordesse@oreilly.com.

View a complete list of OSCON contacts