This week we will be finishing up most of the graph theory material. We will start by discussing Hamiltonian paths and circuits and weighted graphs. A weighted graph is just a graph with numbers (weights) on the edges. Our goal will be to use weighted graphs and Hamiltonian circuits to solve the Traveling Salesman Problem that we discussed last week. We will see three algorithms for solving this: The Nearest Neighbor Algorithm, The Side-Sorted (or Best Edge) Algorithm, and the Repetitive Nearest Neighbor Algorithm. We will also discuss how to solve this using Brute Force. You will need to memorize each of these algorithms. We will end the week with a discussion of trees and spanning trees.
Don't forget to keep up with the homework on WebWork. The first two assignments are due this week.
Challenge Problem: Suppose your favorite presidential candidate is planning a tour of campaign talks in Missouri. He (or she) will visit Kansas City, St. Louis, St. Joseph, Columbia, Springfield, and Jefferson City. Using maps.google.com, find the distance between each of these cities. Using your favorite method from this week, find an optimal route for the candidate to travel, visiting each city once and returning to where he starts. Describe the method you used and provide all details. Your solution should also include a picture of an appropriate weighted graph.
No comments:
Post a Comment