Question 2.75

45. A religious charity arranges free pickups for donated goods to encourage such donations but would like to keep its pickup costs low. The accompanying diagram shows the estimated amounts of time to get between the charity () and the locations of the three pickups scheduled for Wednesday.

image
  1. What route is selected using the nearest-neighbor algorithm starting at ?
  2. What route is selected using the sorted-edges algorithm?
  3. Use “brute force” to determine if the solution in either (a) or (b) yields an optimal solution.

45.

(a)

(b)

(c) The cheapest route costs 132 and coincides with the nearest-neighbor solution from H and the sorted-edges solution.