ENG109 ASSIGNMENT DUE MONDAY WEEK 11 (October 7th 2013) In a previous workshop you wrote a program that could determine the air flight distances between pairs of cities. Your program only considered a single journey at a time, but air freight companies routinely need to plan a route for an aircraft so that it can deliver cargo to several different locations. This is a instance of a computer science puzzle referred to as the “Travelling Salesman Problem” (TSP). The problem is defined as follows: Given a set of cities (and the distances between them) the salesman has to plan a route (or tour) from his start city that visits each of the other cities once (but in any order) and returns to the starting point. The idea is to find the shortest possible route. (See the Wikipedia page for more information on this topic http://en.wikipedia.org/wiki/Travelling_salesman_problem.) TSP becomes a very difficult problem to solve with large sets of cities since the number of possible tour is given by ((N-1)!)/2 (the factorial ! grows very rapidly as N becomes large), where N is the number of cities. The figure on the right shows the shortest route between the 15 largest cities in Germany (Image source: TSP_Deutschland_3.png, from the Wikipedia page). This was selected by considering each of the 43 589 145 600 (43 billion) possible routes. To solve a similar problem for 100 cities would take a modern computer 10148 years (one followed by 147 zeros). Since the age of the universe is tiny in comparison at 14 billion years (about one followed by ten zeros) we are unlikely to build computer that can solve such a problem any time soon. The problem is considered very difficult since no one has ever found an effective short cut for solving this problem so I suggest you try to test every possible route, but over a much smaller set of cities. For instance consider the tour of Australian state and territory capital cities (along with a couple of extras cities to make the tour more…