Grokking Algorithms

Approximation algorithms
Greedy algorithms to the rescue! Here’s a greedy algorithm that comes 
pretty close:
1. Pick the station that covers the most states that haven’t been covered 
yet. It’s OK if the station covers some states that have been covered 
already.
2. Repeat until all the states are covered.
This is called an
 approximation algorithm.
When calculating the exact 
solution will take too much time, an approximation algorithm will 
work. Approximation algorithms are judged by
• How fast they are
• How close they are to the optimal solution
Greedy algorithms are a good choice because not only are they simple 
to come up with, but that simplicity means they usually run fast, too. 
In this case, the greedy algorithm runs in O(
n
^2) time, where 
n
is the 
number of radio stations.

---

148
Chapter 8
 
 
I
 
 
Greedy algorithms
Let’s see how this problem looks in code.
Code for setup
For this example, I’m going to use a subset of the states and the stations 
to keep things simple.
First, make a list of the states you want to cover:
states_needed = set([“mt”, “wa”, “or”, “id”, “nv”, “ut”, 
“ca”, “az”])
You pass an array in, and it gets converted to a set.
I used a set for this. A set is like a list, except that each item can show up 
only once in a set.
 Sets can’t have duplicates. 
For example, suppose you 
had this list: 
>>> arr = [1, 2, 2, 3, 3, 3]
And you converted it to a set:
>>> set(arr)
set([1, 2, 3])
1, 2, and 3 all show up just once in a set.
You also need the list of stations that you’re choosing from. I chose to 
use a hash for this:
stations = {}
stations[“kone”] = set([“id”, “nv”, “ut”])
stations[“ktwo”] = set([“wa”, “id”, “mt”])
stations[“kthree”] = set([“or”, “nv”, “ca”])
stations[“kfour”] = set([“nv”, “ut”])
stations[“kfive”] = set([“ca”, “az”])
The keys are station names, and the values are the states they cover. 
So in this example, the kone station covers Idaho, Nevada, and Utah. 
All the values are sets, too. Making everything a set will make your life 
easier, as you’ll see soon.
Finally, you need something to hold the final set of stations you’ll use:
final_stations = set()

---

149
The set-covering problem