Advanced Mathematical Decision-Making Travelling Salesman Project Suppose a salesperson needs to travel to four different cities to promote a product for his company. His company is headquartered in Atlanta (A) so he'll need to begin and end his trip there. He also needs to visit Birmingham (B), Cincinnati (C), and Detroit (D). He wants to find the cheapest route that will allow him to visit all the cities and still return home. The prices of flights between each city are represented in the following graph: This problem is called the Travelling Salesman Problem (TSP) and has puzzled mathematicians for years. There is still no known algorithm that can be applied to solving every type of TSP, but there are some strategies that are commonly used. One way that we could solve this particular problem is with a tree diagram. We can start our tree at A and diagram all the possible routes from A back to A, visiting B, C, and D in between, as in the diagram below: Atlanta Birmingham ($135) Cincinnati ($245) Detroit ($225) Cincinnati ($210) Detroit ($200) Birmingham ($210) Detroit ($230) Birmingham ($200) Cincinnati ($230) Detroit ($230) Cininnati ($230) Detroit ($200) Birmingham ($200) Cincinnati ($210) Birmingham ($210) Atlanta ($225) Atlanta ($245) Atlanta ($225) Atlanta ($135) Atlanta ($245) Atlanta ($135) Find the total cost for each route by adding the costs of the individual flights under the tree diagram. Write the total cost under each route. According to the total cost you found above, what is the cheapest route(s)? Now suppose our salesperson needs to add another city, El Paso (E) to his route. Additionally, air fares have changed and are now represented in the following graph: Make a tree diagram to show all the possible routes that start and end in Atlanta (A). Remember, some routes may not be possible. Then find the cost of each route and use it to determine the route(s) he should take to visit each city as cheaply as possible