Imagine a salesman who has a list of towns he needs to visit.  He would like to find the shortest route by which he can visit each town exactly once and end up in the town he started with. 

This is the famous Travelling Salesman Problem (TSP).  The towns can be represented by vertices and lines (edges) joining the towns represent a direct link between the towns. 

The distance (or time taken to travel) between the towns is given by a weight associated with each edge.  We call this a network.  The diagrams show a simple four-town scenario, with different weights.

A simple way of solving this is to always choose the shortest route from the current town to a new town.  This is the Nearest Neighbour Algorithm.  In the network P, the salesman will go from A to B, B to D, D to C and C to A, for a total weight of 18, which is the shortest possible route.  If we look at the network Q, the algorithm would choose the route ACBDA, giving a total weight of 15.  But the optimal route ABCDA has total weight 14, so it is a shorter route.  Hence the algorithm has failed.

This algorithm is an example of a greedy algorithm, one which makes the optimal choice at each step while trying to find an overall optimal solution. 

The distance (or time taken to travel) between the towns is given by a weight associated with each edge

Unfortunately, in this case, it does not always provide an optimal solution.

Another method would be to use simple brute force - we calculate the weight of each possible route and select the shortest one. 

For our four-town example, if the salesman starts at A, there are three towns to choose from at the first step, then two and finally one, giving 3 x 2 x 1 = 3! = six possible routes.  But each route appears in two orders, for example ABCDA and ADCBA, thus we can divide by two. In general, if we have n towns, the number of routes to check is (n-1)! divided by two. 

Now if we consider an example with 15 towns, the number of routes to test is over 43 billion.  If a computer checks this at a rate of one million routes per second, it would take over 12 hours.  For the case with 20 cities, such a computer would take 1,928 years! No efficient algorithm is known to solve TSP.

Christina Zarb is subject coordinator for Mathematics at the University of Malta Junior College.

Sound Bites

•        If we settle for near optimal tours for TSP, polynomial-time algorithms exist.  The Christofides algorithm is an approximation algorithm that guarantees that its solutions will be within a factor of 1.5 of the optimal solution.  It is considered the best polynomial time approximation for TSP and is based on known graph theoretic concepts including the minimum spanning tree, matchings and Eulerian cycles. 

•        In June 2021, Karlin, Klein and Gharan published an article in which they introduced a new algorithm that improved on the Christofides algorithm. Their method follows similar principles to Christofides algorithm, but uses a particularly selected tree in place of the minimum spanning tree.

For more science news, listen to Radio Mocha on www.fb.com/RadioMochaMalta/.

DID YOU KNOW?

•        In mathematics/computer science, problems are divided into classes known as complexity classes.  P is the set of decision problems that can be solved efficiently in polynomial time.  NP is the set of decision problems whose solutions can be verified in polynomial time, but for some of these problems no polynomial algorithm is known.  A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem. TSP is an NP-hard optimisation problem

•        A question that has fascinated many computer scientists is whether or not all algorithms in NP belong to P, that is, whether P = NP or not.  It is one of the Millennium Prize Problems for which there is a $1,000,000 prize. 

•        If P = NP is proven, transportation and logistics would be optimised across the world.  Scientists would potentially be able to understand and predict how a given sequence of amino acids will fold up to form its 3D shape, contributing to improving drug design and cures for diseases. 

•        On the other hand, if P = NP, then cracking nearly every kind of encryption code would suddenly become much easier.

For more trivia see: www.um.edu.mt/think.