Grokking Algorithms

Chapter 8
 
 
I
 
 
Greedy algorithms
Finally, you can print 
final_stations
, and you should see this:
>>> print final_stations
set([‘ktwo’, ‘kthree’, ‘kone’, ‘kfive’])
Is that what you expected? Instead of stations 1, 2, 3, and 5, you could 
have chosen stations 2, 3, 4, and 5. Let’s compare the run time of the 
greedy algorithm to the exact algorithm.
EXERCISES
For each of these algorithms, say whether it’s a greedy algorithm or not.
8.3
Quicksort
8.4
Breadth-first search
8.5
Dijkstra’s algorithm
NP-complete problems
To solve the set-covering problem, you had to calculate every
possible set.

---

153
NP-complete problems
Maybe you were reminded of the traveling salesperson problem from 
chapter 1. In this problem, a salesperson has to visit five different cities.
And he’s trying to figure out the shortest route that will take him to all 
five cities. To find the shortest route, you first have to calculate every 
possible route.
How many routes do you have to calculate for five cities?
Traveling salesperson, step by step
Let’s start small. Suppose you only have two cities. There are two routes 
to choose from.

---

154
Chapter 8
 
 
I
 
 
Greedy algorithms
You may be wondering, “In the traveling salesperson problem, is there 
a specific city you need to start from?” For example, let’s say I’m the 
traveling salesperson. I live in San Francisco, and I need to go to four 
other cities. San Francisco would be my start city.
But sometimes the start city isn’t set. Suppose you’re FedEx, trying 
to deliver a package to the Bay Area. The package is being flown in 
from Chicago to one of 50 FedEx locations in the Bay Area. Then 
that package will go on a truck that will travel to different locations 
delivering packages. Which location should it get flown to? Here the 
start location is unknown. It’s up to you to compute the optimal path 
and start location for the traveling salesperson.
The running time for both versions is the same. But it’s an easier 
example if there’s no defined start city, so I’ll go with that version.
Two cities = two possible routes.
3 cities
Now suppose you add one more city. How many possible routes
are there?
If you start at Berkeley, you have two more cities to visit.