So we wanna get from point A to point B as quickly as possible. And, um, to organize how we think about that, to organize the options, the routes, uh, let's think about a network. So let me draw an example network here on the whiteboard. The origin is A, you wanna get to B. Okay?
Let's have a very simple model of travel times in this network. Uh, let's just say that I'm gonna annotate each of these edges with a number representing the travel time along that road in minutes to get from the start of the road to the end of the road. So let's say this one takes three minutes, this one takes four minutes, this one takes one minute, um, this one takes five minutes, and this one takes two minutes. Okay? And these are one-way streets, so you can only drive on the street in the direction of the, of the arrow in this example.
Okay? So you wanna get from A to B, you wanna get there as quickly as possible. So how would you do that? Well, this is not a hard problem to solve just by inspection. If you look at it, there's only three ways to get from A to B that respects kind of the one-wayness of all the streets.
You can go over the top, you can go the northern route. Okay? So that would take three minutes plus four minutes, so that's seven minutes to go the northern route. You could go the southern route, so that would be five minutes plus two minutes. So that would be, again, seven minutes.
So northern and southern routes are tied at seven minutes. And then there's the zigzag path, which, um, has more hops, right? So there's more kind of, you know, the list of the driving directions is one step longer. But in terms of the travel time, actually, you'll get there in three plus one plus two, or six minutes. Okay?
So the zigzag path is the quickest route from A to B, taking six minutes. So what we just did, the way we determined the quickest or shortest path from A to B in this example, is something known as exhaustive search, which is if you have a whole bunch of options, like routes from A to B, and you wanna find the best option, like the one with the smallest travel time, one way you can solve that problem is by just going option by option and remembering the best one. That's what we just did. There were only three paths from A to B. We checked them all.
The zigzag one was the best, so we were confident in proclaiming that the shortest route from A to B. So exhaustive search, you can think of as an algorithm. It's a pretty straightforward algorithm. Examine every option, remember the best one. And if there aren't that many options, right, like in this network, there were three options, that's actually simple enough for just humans to do by hand or by inspection.
Okay? And so you could do this manually for, I don't know, dozens of options, maybe hundreds of options. But of course then, if you think about carrying out exhaustive search by computers, well, you know, modern-day computers, you know, looking through billions of options is generally not a big deal. So you might think then, you're like, "Okay, well, exhaustive search, straightforward algorithm, computers can do billions of operations," like, probably we're just done, right? I mean, probably just, like, whatever problem that comes up, you know, in practice, like for example, you know, driving from, you know, to your, to your relative's place in a different state, whatever.
Just use a computer, look at all the options, remember the best one. End of story. But is that true? Can we be sure that actually in the problems that we sort of solve in day-to-day life, like again, just how to drive to our relative's house, are we sure that there's only billions of options? Are we sure that there aren't, like, maybe much, much, much more than, than that?
So to see what I mean, let me show you another example of a network, and it's a simple network. It's not gonna be hard to figure out the best way to go from point A to point B, but it is going to suggest the limitations of the specific approach of exhaustive search. Okay. So we again wanna go from A to B. And let's assume that in choosing a route from A to B, you just make four...
Is this four? Yes, four choices where you either take the northern route or the southern route, and each time you wind up back at the same place. Okay? So to get to the next stop, you can go north, you can go south. And there's just four consecutive decisions where you just choose whether to go the northern route or the southern route.
Okay? And for example, maybe these are the travel times. Okay. Now, you look at this network, and just like here, you're like, "I don't need a computer to figure out the shortest path from A to B," here you're saying, "I still don't need a computer to figure out the shortest path from A to B." Right? You're like, "Obviously, I go north, and then south, and then north, and then south again." Okay?
For a total travel time of, what is it? I guess sixteen minutes. Okay? Obviously, this is the best thing. Any deviation from the red route would just substitute a worse road for one of the ones you're already taking.
Okay? Obvious. However, let me point out, when you reasoned through this problem, you took advantage of an algorithmic shortcut. You did not reason about it through exhaustive search. Okay?
In the network on the left, there were only three paths, three possible options. Okay? How many options are there to go from A to B? Well, two options for the first hop, multiplied by two options for the second hop, times two again, times two again. Okay, so number of paths from A to B, two times two times two times two.
Also known as two raised to the fourth power, also known as sixteen. Okay? That is how many different options you have. Okay? Because you have an independent binary choice four different times.
All right? Now, you took a shortcut. You were like, I don't even need to think about any path that uses the two because I would just substitute the one and it would be better. Okay, so you just sort of pruned in your mind anything that used the two. Similarly, you pruned in your mind anything that uses the four or the six or the eight, leaving you with the one, three, five, seven red path.
Okay, but in your mind, you did an algorithmic shortcut. You did not do exhaustive search through the sixteen options. Okay? That's the first thing that I want you to notice. All right?
Your response might be like, okay, but so what? Like it's a computer. So it goes through the sixteen options. That's trivial for any modern computer to do. What's the big deal?
So it's a little bit wasteful, right? It's still going to complete in the blink of an eye. Okay? All right. Well, imagine we had a longer whiteboard.
We had one of those long rolls of tape we were talking about with Turing machines in episode number one. And I replicated these binary decisions a few more times. Okay? So in this network, the number of options was two to the four or sixteen. Okay?
So imagine you had ten of these. And again, think about driving like to your relatives in a different state. Okay? There actually are potentially a large number of decision points en route from, I don't know, you know, New York City to Cape Cod or something like that. So imagine there are not just four of these, but there were ten binary decisions you had to make in a row.
So now you wouldn't just have two, four twos multiplied against each other. You wouldn't have two to the four. You'd have two to the sixteen. Okay? Which is a thousand twenty-four.
It's always the, you know you're talking to a computer scientist when they just have all the powers of two like automatically memorized. Definitely means it's a computer scientist. Among friends, thousand twenty-four, let's call this a thousand. Okay? That would be a pain as a human to go through.
Obviously, we could do it. A computer could definitely do it. Sorry, this is a ten. Two to the ten. Looks like a sixteen, not a sixteen.
And that's also a zero. Okay. What if it was twenty? And again, it would not be that hard. I could literally, if I decreased my font size, I could write down this network on this whiteboard.
Okay? It is not like a big network. Okay? It's a relatively small network. Two to the twenty.
Well, that's like a thousand squared or a million. Okay? If you had thirty decisions to make, we're talking about a billion. Forty decisions to make, talking about a trillion. And a trillion starts getting significant even for computers to do.
I'm not saying it's impossible, but that you start feeling the pain a little bit at a trillion for sure. Imagine you're driving from the West Coast to the East Coast, right? Imagine you have, I don't know, let's say at least two hundred and sixty-five different decisions to make going from, I don't know, Burlington to La Jolla. Okay? Two to the two sixty-five.
Two to the two sixty-five. So exponential growth is a wild, wild thing, right? So many of us kind of are first taught this lesson through the power of compounding, right? And this is sort of another version of it. Exponential growth is really, really, really, really fast.
Really fast. Really fast. So much so that it defies human intuition. Two sixty-five. And again, you can imagine writing down a network like this with two hundred and sixty-five choices, right?
It would not be hard. Okay? We could write it down. We could have it on this table. No problem.
The number of different routes in that network, the number of options you would have to check if you were carrying out exhaustive search is, I'm not kidding, basically the number of estimated atoms in the known universe. Two to the two sixty-five is the estimate for the number of atoms in the known universe. Okay? So while exhaustive search would still be an algorithm in the sense of Turing, it would still be a recipe that if carried out to completion would indeed identify the shortest path, it is one that would defy our understanding of physical limitations. It is one that would not complete an hour or anybody else's lifetime.