Okay, we're going to look at two kinds of search strategies. One of them we call

uninformed because they only have what is in the problem formulation. They only

look at the problem formulation. And then we have informed search strategies

that have something we call heuristics which is kind of a sense of smell which

guides the search and they will behave quite differently. I'm assuming that you

know uninformed search strategies already. Who of you has looked at and maybe

forgotten breadth-first search? The majority. How about depth-first search?

Yeah I expected that. Uniform cost search? Excellent. So we can go over this very

quickly. If you want to stop me you can do that by asking questions. Okay if you

don't stop me I'm going to assume you either already know, I'll only need to be

reminded, or you have the iron will to look at the slides after the course. Okay

so breadth-first search, very simple, is essentially we treat the fringe as a

first in first out queue. Okay and here's an example. We start out with the root

node. We go we expand and get two nodes. In this case we have a fringe and it has

two nodes in it. We pick the older one of those, B we expand giving us two more

nodes. We pick C because it's older than D and E. We expand C. The oldest one now

is D. The next one we'll pick is E. And you can see that what we're doing is

essentially, and that's where the name comes from, we're exploring the tree

layer for layer for layer for layer. Okay very simple and the way is we treat the

fringe as a queue, i.e. the node that is oldest in the queue gets taken out next.

Also called a FIFO queue is first in first out, which is essentially take

the oldest one. It's like the queue you use when you're queuing up for the

menza. Who comes first gets served first. So if we go to look at this in Romania,

this is very simple. If we go to, and we do get into loops potentially okay but

of course Arad gives us something like this but we will get a whole layer in

the graph of a layer, a new layer in the graph which we will work out bit by bit

and eventually we will reach... okay good. Remember four properties. First one was

completeness. Is this thing, is breadth first complete? No, I hear. Can you so

can you please say why? Because the depth are different, the depths of the trees are

different. The branches I mean the some branches are going further down but some

of them not. Yes. Another answer? This is not correct. We'll find out why. Yes.

If infinite time you get through all the layers and you will definitely find a

solution. Right so breadth first search is essentially this and eventually

since every solution has finite depth you will get there. The question is after

how long? Well let's look at this example. This is a nice tree because the

branching factor is two. Okay essentially the worst case is if O is

the only goal, right? The only solution. Now we have depth one, two, three. We need

in this case eight plus four plus two plus one nodes we're going to look at.

Okay so if we have a depth M of the... no. How do I call it? D, right D for

depth. Yes of the solution. We have depth D then we have two to the three plus

right and we essentially what we have the time complexity of breadth first

search is big O of two to the D plus one.

Every lower layer has two to the D in this case two to the two to the three

layers and if you sum up everything on top of it you actually get the number

two to the D plus one minus one. Okay we can erase the sum and we can actually

erase that because that's just a constant factor which we can also get

rid of. Okay so we have exponential time that we need in the worst case which is

if the solution is down here. Okay good. Big O complexity is just counting okay

and in trees you always want to remember that you have two to the two to the D

nodes in here. Okay now what's the space complexity? How big can the fringe get?