DOC PREVIEW
UK MA 111 - The Mathematics of Touring

This preview shows page 1-2-3-4-5-6-42-43-44-45-46-47-85-86-87-88-89-90 out of 90 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 90 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

InfoTraveling Salesman ProblemsGraphsHamilton Paths and CircuitsComplete GraphsAlgorithms for the TSPInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPThe Mathematics of TouringBeth Kirby and Carl LeeUniversity of KentuckyMA 111Fall 2009Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPInfoTraveling Salesman ProblemsGraphsHamilton Paths and CircuitsComplete GraphsAlgorithms for the TSPTouring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPCourse InformationText: 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.htmlTouring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSP6.3 Traveling Salesman ProblemsTouring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPPlanning a Road TripUse the worksheet to plan a road trip through six cities inKentucky.The chart below contains the driving distances (in miles)among six cities in Kentucky.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPPlanning a Road TripLex Lou Eliz Cor Owens PadLexington 74 85 92 175 256Louisville 74 45 158 109 218Elizabethtown 85 45 143 94 175Corbin 92 158 143 234 315Owensboro 175 109 94 234 130Paducah 256 218 175 315 1301. Plan a trip that starts in Lexington, visits the other fivecities, and then returns to Lexington, with the leastamount of driving. Try to develop a strategy that willresult in the shortest trip.2. Do the same as in (1), but now suppose your trip muststart and end in Louisville. Does your route change?Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPThe Traveling Salesman ProblemYou have just encountered a traveling salesman problem.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPThe Traveling Salesman ProblemYou have just encountered a traveling salesman problem.Characteristics oftraveling salesman problems (TSPs):◮The tour passes through several sites (cities), starting andending at the same site.◮Each site (other than the starting/ending one) is visitedexactly once.◮A cost (distance) is associated to each leg of the tour.◮The goal is to find an optimal tour. We wanted tominimize the total distance.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPAlgorithmsAn algorithm is a problem-solving tool made up of proceduralrules that result in some kind of solution to the problem.The algorithm must have clearly defined rules that eventuallycome to an end.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPAlgorithmsAn algorithm is a problem-solving tool made up of proceduralrules that result in some kind of solution to the problem.The algorithm must have clearly defined rules that eventuallycome to an end.For example, each voting method we discussed was a type ofalgorithm. After a certain number of steps, a winner of theelection was determined.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPAlgorithms for Solving the KY Road Trip Problem◮If you list out all of the possible routes and calculate eachof their total distances, you can pick the shortest route.This is called theBrute Force Algorithm.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPAlgorithms for Solving the KY Road Trip Problem◮If you list out all of the possible routes and calculate eachof their total distances, you can pick the shortest route.This is called theBrute Force Algorithm.◮From the starting city, you can choose to go to theclosest city. Repeat this idea, so that from each city, youchoose to go to the closest city that has not yet beenvisited. This is called theNearest Neighbor Algorithm.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPApplications: Other Examples of TSPMr. Loman is a traveling salesman. He must start and end inhis hometown and then visit five other cities once. He knowsthe cost of a one-way plane ticket between each of the cities.What is the cheapest route for Mr. Loman?Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPApplications: Other Examples of TSPMr. Loman is a traveling salesman. He must start and end inhis hometown and then visit five other cities once. He knowsthe 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 UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPApplications: Other Examples of TSPA school bus must drop off children at twenty different stopsaround town. Each child must be dropped off, and then thebus driver must return the bus to the school. The estimatedtime between stops is known. What is the fastest route?Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPApplications: Other Examples of TSPA school bus must drop off children at twenty different stopsaround town. Each child must be dropped off, and then thebus driver must return the bus to the school. The estimatedtime between stops is known. What is the fastest route?Sites: Bus stops.Cost: Time between stops.Optimal Tour: Fastest route.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPApplications: Other Examples of TSPNASA’s StarLight program uses a pair of satellites to imagecelestial objects. Each object should be imaged once. Topreserve fuel, NASA must minimize the amount of fuel neededto reposition the satellites in order to take the next picture.Touring UKInfo Traveling Salesman Problems Graphs Hamilton Paths and Circuits Complete Graphs Algorithms for the TSPApplications: Other


View Full Document
Download The Mathematics of Touring
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view The Mathematics of Touring and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Mathematics of Touring 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?