Question 2.76

46. An organization that delivers meals to the needy elderly must deliver food to three clients and wants to keep down its costs. Typical times to get between its home site H and the clients are given in the accompanying graph.

image
  1. What route is selected using the nearest-neighbor algorithm starting at H?
  2. What route is selected using the sorted-edges algorithm?
  3. Use “brute force” to determine whether the solution in either part (a) or (b) yields an optimal solution.
  4. Compare the times in the diagrams in this excercise and Exercise 45. How do they differ? Can you state a general result about solving TSPs based on what you notice?

73