Section 16.2 Chapter 16 Exercises
Subsection 16.2.1 Section 16.1 Exercises
1. A company needs to deliver product to each of their 5 stores around the Dallas, TX area. Driving distances between the stores are shown below. Find a route for the driver to follow, returning to the distribution center in Fort Worth: (a) using the Nearest Neighbor algorithm starting in Fort Worth, and (b) using the Repeated Nearest Neighbor algorithm; (c) then implement the result from (b) beginning at Arlington.
2. Apply the repeated nearest neighbor algorithm to the graph below to find a Hamilton circuit. After you find the circuit, implement it starting at vertex C.
3. When installing fiber optics, some companies will install a sonet ring; a full loop of cable connecting multiple locations. This is used so that if any part of the cable is damaged it does not interrupt service, since there is a second connection to the hub. A company has 5 buildings. Costs (in thousands of dollars) to lay cables between pairs of buildings are shown below. Find the circuit that will minimize cost: (a) using Nearest Neighbor from building A, and (b) using Repeated Nearest Neighbor, then implemented beginning from building E.
Subsection 16.2.2 Section 16.2 Exercises
4. Use the Cheapest Link (or sorted-edges) Algorithm on problem 1 above.
5. Use the Cheapest Link (or sorted-edges) Algorithm on problem 2 above.
6. Use the Cheapest Link (or sorted-edges) Algorithm on problem 3 above.
