Grokking Algorithms

Same route or different?
You may think this should be the same route. After all, isn’t SF > Marin 
the same distance as Marin > SF? Not necessarily. Some cities (like San 
Francisco) have a lot of one-way streets, so you can’t go back the way you 
came. You might also have to go 1 or 2 miles out of the way to find an on-
ramp to a highway. So these two routes aren’t necessarily the same.

---

155
NP-complete problems
There are six total routes, two for each city you can start at.
So three cities = six possible routes.
4 cities
Let’s add another city, Fremont. Now suppose you start at Fremont.

---

156
Chapter 8
 
 
I
 
 
Greedy algorithms
There are six possible routes starting from Fremont. And hey! They 
look a lot like the six routes you calculated earlier, when you had only 
three cities. Except now all the routes have an additional city, Fremont! 
There’s a pattern here. Suppose you have four cities, and you pick a start 
city, Fremont. There are three cities left. And you know that if there are 
three cities, there are six different routes for getting between those cities. 
If you start at Fremont, there are six possible routes. You could also start 
at one of the other cities.
Four possible start cities, with six possible routes for each start city =
4 * 6 = 24 possible routes.
Do you see a pattern? Every time you add a new city, you’re increasing 
the number of routes you have to calculate.
How many possible routes are there for six cities? If you guessed 720, 
you’re right. 5,040 for 7 cities, 40,320 for 8 cities.
This is called the 
factorial function
(remember reading about this in 
chapter 3?). So 5! = 120. Suppose you have 10 cities. How many possible 
routes are there? 10! = 3,628,800. You have to calculate over 3 
million 
possible routes for 10 cities. As you can see, the number of possible 

---

157
NP-complete problems
routes becomes big very fast! This is why it’s impossible to compute the 
“correct” solution for the traveling-salesperson problem if you have a 
large number of cities.
The traveling-salesperson problem and the set-covering problem both 
have something in common: you calculate every possible solution and 
pick the smallest/shortest one. Both of these problems are 
NP-complete
.
Here’s the short explanation of NP-completeness: some problems are 
famously hard to solve. The traveling salesperson and the set-covering 
problem are two examples. A lot of smart people think that it’s not 
possible to write an algorithm that will solve these problems quickly.
Approximating
What’s a good approximation algorithm for the traveling salesperson? 
Something simple that finds a short path. See if you can come up with an 
answer before reading on.
Here’s how I would do it: arbitrarily pick a start city. Then, each time the
salesperson has to pick the next city to visit, they pick the closest unvisited 
city. Suppose they start in Marin.
Total distance: 71 miles. Maybe it’s not the shortest path, but it’s still
pretty short.

---

158