Okay, can we change that? The answer is yes. We do depth first search, which is essentially

just treat the queue as a stack and then you get a different behavior which really drills

down instead of layer by layer, we just drill down here, come back and search systematically

that way. Okay, that is nice. Why? Well, because we at any time, we only have to care about

this many nodes. And if we have a branching factor of B and a depth of D, this here is

just B times D. Wonderful. I can search longer. Okay, much, much, much longer. Millions of

years, no problem anymore, even on a wimpy laptop. So, that is really only the way, the

only thing here is that we need to take care of is essentially that the fringe gets shorter.

And then the fringe is vertical instead of horizontal. And if you think of that picture,

this picture here, you understand why that is good. Of course, eventually time of reckoning

comes, right? Completeness goes down the drain because we can do infinite loops and not get

to the right solutions. At least if we have infinite depth, which in practice we usually

have. Time complexity, because we have to search the whole tree in the worst case, is

bad as always. BOD space complexity is essentially linear in both the branching factor and in

the depth. Okay? And optimality we are not getting. So, kind of the bad news is in different

places and we basically looked at a nice little fix for it. The idea is to make the search

spaces finite by just iteratively making them deeper. You just at some point say, well,

I'm bored now, I'll give up searching at depth two or in this case at depth zero and then

you kind of redo that increasing and increasing. And at some point here we have a depth four,

I'm sorry, depth three solution and after looking at all depth zero trees, all depth

one trees, all depth two trees, all depth three trees, we find the solution. The somewhat

surprising fact here is that if we go down step by step by step by step, just step size

one, then we're almost losing nothing. If you think about the numbers, you can already

see it, right? There's a lot of work to do at depth three. So, this plus that plus that

is actually less work by one than what we're doing here. So, even though we're redoing

all the stuff we had already done, we're not losing much. Okay, so iterative deepening

search is actually the go-to method typically if you have uninformed search strategies because

it essentially behaves like breadth-first search time-wise, not much worse, but it actually

does the, has the nice space complexity that depth-first search has. And now from this

idea we can build more interesting things. We could do things like instead of cutting

it off at a level, we could cut it off at a cost and so on, then we'd get say uniform

cost like search and you can imagine starting your engineering career with those kind of

ideas which is exactly what happened in the 50s. People discovered these algorithms, applied

them to a bunch of problems and said, ah, that's AI. We can find solutions to general

problems. Wow. Give me millions. So, but once you think about it, it's all exponential.

This is going nowhere essentially, except if you cheat. Okay? And that's what we want

to do. We want to actually use stuff that's outside the problem to do better than we could

otherwise. And we humans are really, really, really good at this. And that's what we want

to look at next. Oh yeah, that's the optimality picture if you don't do step size one iterative

deepening. And we briefly talked about graph search, only to say that we're not doing it.

Okay? So, the main thing here, the intuition I would like you to have is that we can actually

do things like solve the infinite path problem, right, going from ARRA to CBU to ARRA to CBU

and so on, by basically checking for repeated states. The problem with this is you have

to remember all the states you've been to. Obviously, otherwise you can't compare. Right?

And that means you're losing space. And then you have to really carefully think, is it

worth it? What is my problem space like if it has lots of infinite loops but a few nodes

that might pay off if I have lots of nodes but very few connections between them, it

might not pay off and so on. So, that's where engineering starts then. Repeated state checking

very often pays off. But there are better ways and so we look at heuristic search now.

That's under the heading of informed search strategies and it already sounds much better