Python Programming for Biology: Bioinformatics and Beyond

The travelling salesman problem

The  Python  examples  now  move  on  from  Monte  Carlo  optimisation  of  a  mathematical

function to combinatorics: the travelling salesman problem. Specifically, we will show an

example that can determine the best route between 15 of the largest cities in France (see

Figure 25.1

).  There  are  a  total  of  1,307,674,368,000  possible  ways  of  ordering  the  cities

into a route, although our solution will search only a fraction of these to come up with the

optimum answer. We don’t mean to suggest that Monte Carlo is the best way to solve this

particular  problem,  but  it  gives  a  clear  example  to  work  with.  Likewise,  we  could  also

choose to solve a different problem, but hopefully by keeping things simple you will see

how analogous situations that involve the ordering of data items can be solved.