A planner cannot afford to try every order of 60 stops, but still wants to know how good a proposed loop is. For that she needs a number that no closed loop through all the stops can beat. She builds it like this.
Pick one stop v. Take away v and connect all the other stops with a network of straight
roads of the smallest possible total length (any two remaining stops must be joined through the
network). Add the two shortest distances from v to other stops. Call the result bound(v).
Every closed loop, with the two legs at v removed, is a path joining all the other stops, so it is
at least as long as that cheapest network, and its two legs at v are at least the two shortest
ones. So every bound(v) is a guaranteed lower bound on the shortest loop.
Write loop_lower_bound(stops) that returns the largest bound(v) over all stops v, rounded to
2 decimals. stops is a list of (x, y) points; distances are straight-line distances.
Examples
Input: stops = [(0, 0), (0, 3), (4, 3), (4, 0)]
Output: 14.0
Explanation: for v = 0 the other three stops are joined by roads of length 4 and 3 (total 7),
and the two shortest legs from (0, 0) are 3 and 4: 7 + 3 + 4 = 14.
Every stop gives 14, and here the bound equals the best loop.
Input: stops = [(0, 0), (1, 0), (2, 0), (3, 0)]
Output: 5.0
Explanation: for v = 1 the network 0-2-3 has length 2 + 1 = 3 and the legs are 1 and 1.
Every stop gives 5, while the best loop has length 6: a bound need not be reached.
Input: stops = [(0, 0), (2, 0), (1, 5)]
Output: 12.2
Constraints
3 <= len(stops) <= 60- coordinates are integers between
-1000and1000; stops may coincide
Goals
- Prove a quality guarantee without finding the best loop
- Grow a cheapest connecting network over a set of points
- Strengthen a bound by trying every choice and keeping the largest