Okay, so next strategy. The next strategy is what we call depth first search. The only

thing we have to choose is to order this fringe differently. Either you think of this as last

in first out or as a stack essentially. Instead of taking out the oldest one, we take out

the youngest one. And what do we get? Well, we start with A. What's happening here? Okay.

My animation has somehow gone wrong. Let's see. Oh yeah. Well, from here, say we start

in the middle. I'm sorry. Right? So the idea is, let me play this by finger. Okay, so we

start in A, we expand A, we get two nodes, and the youngest one is B. Right? Then we

expand B, we get two nodes, the youngest one is D. Okay? We expand D, the youngest one

is H. Say H, say we only have a finite depth here to make things easy. Say H is not a goal,

so we fail here, so we actually choose the youngest one after that, that's I. Say this

fails, then we know this whole subtree fails, so we choose E, we get a J, this fails, that

fails, the whole subtree fails, and then we go through the whole thing. And in this case,

we've ended up in O, which is the worst case, and we've found the solution. Yes?

No, because under A, there is a solution. I'm randomly making these inner nodes red

if they only have red underneath them. Okay? Nothing really hinges on that.

Do we check A in the beginning, or do we not check?

We do check A when we, all in the beginning, yes, but it's not a goal node, and I'm not

making it red because it does have either a potential solution or an actual solution

under it somewhere, which means it's not itself the solution, but it could lead to a solution.

Good. Yeah, sorry.

What does it mean, youngest node?

The last one in the expansion. So say we're somewhere there, then if you look at the order

we've expanded them, A, B, D, H, I, E, J, and we've expanded E, and we have two nodes

in the fringe, and I'm assuming that the left ones are younger. It doesn't really matter.

The trees aren't really ordered. There was a question back there? Okay, good. Okay. Yes.

Excellent. Sorry.

I have a question to the uniform cost search again. So could you maybe open the example

with the cities? Back. Here, okay, stop. So, okay. And the next one? Could you go? Yes,

here. Okay. Why do we expand this node with costs 118? Why don't we expand the node with

costs? Because you have to sum them up? Least cost is somewhat sloppy. You should probably

say least path cost. Okay. And here we have 75 plus 71. Okay. And 75 plus 75, which makes

Téméchoir look good. Okay. I'm known for my bad catching skills, and I'm feeling proud

of myself today. Okay. So depth first search. Now, is this optimal? No, why not? Because

if there are multiple times O industry, you may find another O, and it could be... I

meant actually complete. It's not complete. Why? If there is an infinite branch there,

but because it's the first search, that should not be. So... If this M, this overall depth

of the tree is finite, then as we've seen, in this case we have depth three, then we

will eventually reach the solution here, and we're complete. Okay. Yes. Next one. How about

time complexity? It's again two to the D. In the worst case, we're searching every node,

and it's the same. Exactly. Now comes the interesting question. How about space complexity?

Yeah. Good. It's O of D, because we only have to save the path. The path, yes. We look very

carefully though. Here we have a fringe. Minus one we'd never care about. Okay. So that was

exactly the correct answer. If we look at this, say we have a path down to a goal here,

then the fringe, in the worst case, would say we have a branching factor of four. We

might actually have three nodes left over still. So we're in O of, we would expect something

like time complexity of D times B. In other words, not exponential. Okay. Something happened.

This is something that behaves completely differently. You may still have to wait almost

arbitrarily long, but we can do that on a small computer. Okay. What are we losing?

Oh yeah. You can do it in Romania as well. Here you can actually see the B times D. You

can already see that depth-first search in Romania will very happily loop between ARAD