Try It Now

Printed by:	Guest user
Date:	Tuesday, May 7, 2024, 9:53 PM

Description

Work these exercises to see how well you understand this material.

Find the closest neighbor circuit through the six capitals of New England starting at Boston. If you start at a different city, will you get a different circuit?
Given the following sets of points in the unit square, find the shortest circuit that visits all the points, and find the circuit that is obtained with the strip algorithm.
1. {(0.1k, 0.1k) : k = 0, 1, 2, ..., 10}
2. {(0.1, 0.3), (0.3, 0.8), (0.5, 0.3), (0.7, 0.9), (0.9, 0.1)}
3. {(0.0, 0.5), (0.5, 0.0), (0.5, 1.0), (1.0, 0.5)}
4. {(0, 0), (0.2, 0.6), (0.4, 0.1), (0.6, 0.8), (0.7, 0.5)}
Consider the network whose maximum capacities are shown on the following graph.
1. A function f is partially defined on the edges of this network by: f(Source, c) = 2, f (Source, b) = 2, f (Source, a) = 2, and f (a, d) = 1. Define f on the rest of the other edges so that f is a flow. What is the value of f?
2. Find a flow augmenting path with respect to f for this network. What is the value of the augmented flow?
3. Is the augmented flow a maximum flow? Explain.
Find maximal flows for the following networks.
Discuss the reasons that the closest neighbor algorithm is not used in the unit square version of the Traveling Salesman Problem. Hint. Count the number of comparisons of distances that must be done.

Answer: The circuit would be Boston, Providence, Hartford, Concord, Montpelier, Augusta, Boston. It does matter where you start. If you start in Concord, for example, your mileage will be higher.
Answer:
1. Optimal cost = $2 \sqrt 2$ . Phase 1 cost = $2.4 \sqrt 2$ . Phase 2 cost = $2.6 \sqrt 2$ .
2. Optimal cost = 2.60. Phase 1 cost = 3.00. Phase 2 cost $2 \sqrt 2$ .
3. A = (0.0, 0.5), B = (0.5, 0.0), C = (0.5, 1.0), D = (1.0, 0.5)
  
  There are 4 points; so we will divide the unit square into two strips.
  - Optimal Path: (B, A, C, D) Distance = $2 \sqrt 2$
  - Phase I Path: (B, A, C, D) Distance = $2 \sqrt 2$
  - Phase II Path: ( A, C, B, D) Distance = $2 + \sqrt 2$
4. A = (0, 0), B = (0.2, 0.6), C = (0.4, 0.1), D = (0.6, 0.8), E = (0.7, 0.5)
  
  There are 5 points; so we will divide the unit square into three strips.
  - Optimal Path: (A, B, D, E, C) Distance = 2.31
  - Phase I Path: (A, C, B, C, E) Distance = 2.57
  - Phase II Path: (A, B, D, E, C) Distance = 2.31
Answer:
1. f (c, d) = 2, f(b, d) = 2, f(d, k) = 5, f(a, g) = 1, and f (g,k) = 1.
2. There are three possible flow-augmenting paths. s, b, d, k with flow increase of 1. s, a, d, k with flow increase of 1, and s, a, g, k with flow increase of 2.
3. The new flow is never maximal, since another flow-augmenting path will always exist. For example, if s, b, d, k is used above, the new flow can be augmented by 2 units with s, a, g, k.

Answer:

Value of maximal flow = 14.

Step 1	Flow-augmenting path Source,A, Sink	Flow added 2
2	Source,C, B, Sink	3
3	Source,E, D, Sink	4
4	Source,A, B, Sink	1
5	Source,C, D, Sink	2
6	Source,A, B, C, D, Sink	2

Hint: Count the number of comparisons of distances that must be done.

Answer: To locate the closest neighbor among the list of k other points on the unit square requires a time proportional to k. Therefore the time required for the closest-neighbor algorithm with n points is proportional to (n − 1) + (n − 2) + · · · + 2 + 1, which is proportional to n2 . Since the strip algorithm takes a time proportional to n(log n), it is much faster for large values of n.