2

This is my first time learning data structure and algorithms. I am stuck in the Grokking Algorithm Chapter 8 Greedy Algorithms, where there is a simple Set Covering Problem given to the readers.

Is there a simpler example of source code which I can refer to understand the concept behind this example?

Can somebody explain how set intersection helps to get the ultimate result of {'k4', 'k5'} in plain English? How is the array of states_needed passed in to a hash and gets converted to a set?

states_needed = set(["a", "b", "c", "d", "e", "f", "g", "h"])

stations = {}

stations["k1"] = set(["a", "b", "c"])
stations["k2"] = set(["c", "d", "e"])
stations["k3"] = set(["f", "g", "h"])
stations["k4"] = set(["a", "b", "c", "d"])
stations["k5"] = set(["e", "f", "g", "h"])

final_stations = set()

while states_needed:
  best_station = None
  states_not_covered = set()
  
  for station, states_for_station in stations.items():
    covered = states_needed & states_for_station
    if len(covered) > len(states_not_covered):
      best_station = station
      states_not_covered = covered

  states_needed -= states_not_covered
  final_stations.add(best_station)

print(final_stations)
z2typ
  • 3
  • 2
daiman00
  • 25
  • 2
  • It is a greedy algorithm, set intersection enables being the "greediest" at each step, by picking the set that covers the most (i.e. has the largest intersection) of the elements of the set that have not been covered. In the formal proof of the cost of this greedy approximation algorithm vs. the optimal (brute-force) algorithm, set intersection is used to relate the "price" paid for each element in the sets picked to the number of sets picked. – zr0gravity7 Dec 22 '21 at 06:36

0 Answers0