we will be looking at the travels of a fictional circus with just a single touring unit. This Atlanta-based circus plans to visit 24 cities, listed in the table below. After visiting all of the cities, the circus will return to Atlanta. The goal of the circus is to find a good tour of all the cities; that is, to find a path that visits each city and then returns to its starting point. Of course, some tours are shorter than others, and the optimal tour is the one which covers the least total distance. Atlanta, GA Detroit, MI Lincoln, NE Phoenix, AZ Boston, MA Indianapolis, IN Minneapolis, MN Pittsburgh, PA Buffalo, NY Jacksonville, FL Nashville, TN Portland, OR Charlotte, NC Kansas City, MO New Orleans, LA Salt Lake City, UT Chicago, IL Las Vegas, NV Oakland, CA San Antonio, TX Cleveland, OH Lexington, KY Oklahoma City, OK San Diego, CA The raw city-to-city distance data (HW2data.xls) can be found in an Excel spreadsheet on Canvas. All distances are symmetric; the distance from city A to city B is the same as the distance from city B to city A. 1. Use your own intuition to get the shortest-distance circus tour you can find. Do not use any of the algorithms from class - don't worry, you'll have plenty of opportunity for that in the rest of the homework, and your grades will not depend on the quality of the solution you find in this part. For now, just try using your intuition and logic. Draw your best answer clearly on a copy of the map (HW1map.pdf), and give the total distance. 2. Using the distances provided on Canvas (do not just go by eye, as the graphical plot is not to scale), use the traditional Nearest Neighbor heuristic from class to find the best route for the circus to take. Draw your answer clearly on a copy of the map, provide a list of the edges in the order that you choose them, and give the total distance.
we will be looking at the travels of a fictional circus with just a single
touring unit. This Atlanta-based circus plans to visit 24 cities, listed in the table below.
After visiting all of the cities, the circus will return to Atlanta.
The goal of the circus is to find a good tour of all the cities; that is, to find a path that visits
each city and then returns to its starting point. Of course, some tours are shorter than others,
and the optimal tour is the one which covers the least total distance.
Atlanta, GA Detroit, MI Lincoln, NE Phoenix, AZ
Boston, MA Indianapolis, IN Minneapolis, MN Pittsburgh, PA
Buffalo, NY Jacksonville, FL Nashville, TN Portland, OR
Charlotte, NC Kansas City, MO New Orleans, LA Salt Lake City, UT
Chicago, IL Las Vegas, NV Oakland, CA San Antonio, TX
Cleveland, OH Lexington, KY Oklahoma City, OK San Diego, CA
The raw city-to-city distance data (HW2data.xls) can be found in an Excel spreadsheet on
Canvas. All distances are symmetric; the distance from city A to city B is the same as
the distance from city B to city A.
1. Use your own intuition to get the shortest-distance circus tour you can find. Do
not use any of the algorithms from class - don't worry, you'll have plenty of
opportunity for that in the rest of the homework, and your grades will not depend
on the quality of the solution you find in this part. For now, just try using your
intuition and logic. Draw your best answer clearly on a copy of the map
(HW1map.pdf), and give the total distance.
2. Using the distances provided on Canvas (do not just go by eye, as the graphical
plot is not to scale), use the traditional Nearest Neighbor heuristic from class to
find the best route for the circus to take. Draw your answer clearly on a copy
of the map, provide a list of the edges in the order that you choose them, and give
the total distance.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images