What we've looked at is basically describing the problem.

Now we want to look at algorithms.

What kind of algorithms do we have?

Well, the only thing we really have is search algorithms.

That's essentially what we do is we develop the search tree.

We prune some of them out with a heuristic saying,

they're so bad, we're not going to look at them.

Then you basically expand further and further until you find a solution.

That's really looking at the state space.

If you think about it,

and especially if you have planning-like problems,

like planning your day or something like this,

then you'll see that there's quite a lot of redundancy.

You can do things in multiple orders.

You remember you could first go to Brisbane and then to,

what was it, Darwin or the other way around.

It didn't really matter that much.

We have huge branching factors so that we need very good heuristics.

That's really what I want to show you today.

The idea here is that you develop the search space,

and you're given a sense of direction by this heuristics.

The heuristic is nothing more but a cost estimate to the goal.

The effect of following least cost,

greedy search, is actually that it focuses the search towards the goal,

because we know where at least the costs look good.

That's exactly what we want to do today.

We have two algorithms we saw with heuristics.

We saw greedy search.

Greedy search is essentially satisfying planning.

You follow your nose without being optimal,

but it gets you there fast.

Then you have A star,

which finds optimal solutions at the cost of searching bigger search spaces.

If you remember Romania,

we had the following situations.

We started out in Arad and we wanted to go to Budapest.

We had a situation like this,

where we had a three hop,

optimal solution, four hop,

optimal solution, and this one being slightly longer.

Greedy search will find the solution with least hops first.

Whereas by just following the heuristics,

greedy search has problems that can get stuck in loops.

Remember the chicken,

and it doesn't find optimal solutions.

But if you're interested in finding

satisfiable plans fast,

it might just be what you go for.

So this is a good way of doing things,

and if you want to be sure that you are either fast or optimal enough,