Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP The Mathematics of Touring Beth Kirby and Carl Lee University of Kentucky MA 111 Fall 2009 Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Course Information Text Peter Tannenbaum Excursions in Modern Mathematics second custom edition for the University of Kentucky Pearson Course Website http www ms uky edu lee ma111fa09 ma111fa09 html Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP 6 3 Traveling Salesman Problems Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Planning a Road Trip Use the worksheet to plan a road trip through six cities in Kentucky The chart below contains the driving distances in miles among six cities in Kentucky Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Planning a Road Trip Lex Lou Eliz Cor Owens Pad Lexington 74 85 92 175 256 Louisville 74 45 158 109 218 Elizabethtown 85 45 143 94 175 Corbin 92 158 143 234 315 Owensboro 175 109 94 234 130 Paducah 256 218 175 315 130 1 Plan a trip that starts in Lexington visits the other five cities and then returns to Lexington with the least amount of driving Try to develop a strategy that will result in the shortest trip 2 Do the same as in 1 but now suppose your trip must start and end in Louisville Does your route change Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP The Traveling Salesman Problem You have just encountered a traveling salesman problem Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP The Traveling Salesman Problem You have just encountered a traveling salesman problem Characteristics of traveling salesman problems TSPs The tour passes through several sites cities starting and ending at the same site Each site other than the starting ending one is visited exactly once A cost distance is associated to each leg of the tour The goal is to find an optimal tour We wanted to minimize the total distance Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Algorithms An algorithm is a problem solving tool made up of procedural rules that result in some kind of solution to the problem The algorithm must have clearly defined rules that eventually come to an end Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Algorithms An algorithm is a problem solving tool made up of procedural rules that result in some kind of solution to the problem The algorithm must have clearly defined rules that eventually come to an end For example each voting method we discussed was a type of algorithm After a certain number of steps a winner of the election was determined Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Algorithms for Solving the KY Road Trip Problem Touring If you list out all of the possible routes and calculate each of their total distances you can pick the shortest route This is called the Brute Force Algorithm UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Algorithms for Solving the KY Road Trip Problem Touring If you list out all of the possible routes and calculate each of their total distances you can pick the shortest route This is called the Brute Force Algorithm From the starting city you can choose to go to the closest city Repeat this idea so that from each city you choose to go to the closest city that has not yet been visited This is called the Nearest Neighbor Algorithm UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Applications Other Examples of TSP Mr Loman is a traveling salesman He must start and end in his hometown and then visit five other cities once He knows the cost of a one way plane ticket between each of the cities What is the cheapest route for Mr Loman Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Applications Other Examples of TSP Mr Loman is a traveling salesman He must start and end in his hometown and then visit five other cities once He knows the cost of a one way plane ticket between each of the cities What is the cheapest route for Mr Loman Sites Cities Cost Cost of a one way plane ticket Optimal Tour Cheapest route Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Applications Other Examples of TSP A school bus must drop off children at twenty different stops around town Each child must be dropped off and then the bus driver must return the bus to the school The estimated time between stops is known What is the fastest route Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Applications Other Examples of TSP A school bus must drop off children at twenty different stops around town Each child must be dropped off and then the bus driver must return the bus to the school The estimated time between stops is known What is the fastest route Sites Bus stops Cost Time between stops Optimal Tour Fastest route Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Applications Other Examples of TSP NASA s StarLight program uses a pair of satellites to image celestial objects Each object should be imaged once To preserve fuel NASA must minimize the amount of fuel needed to reposition the satellites in order to take the next picture Touring UK Info Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP Applications Other Examples of TSP NASA s StarLight program uses a pair of satellites to image celestial objects
View Full Document
Unlocking...