Then you have this total cost But as you see, Dijkstra's algorithm not only expands towards the goal But it also expands of course the same amount in every direction And so if I put an obstacle here This will not change anything regarding the total cost

It changes the search expansion down here of course But if you watched here, this frontier didn't actually change Now this changes when I start to force the minimum path to get longer Then not only this path is longer but also as you have seen if you watched carefully The set of visited nodes expands in all directions

And so this means it gets very costly If the path to the goal gets longer Especially say you have a kind of a dead end road Then you see search space expands so that for this slight detour here

We have to expand the huge number of cells in this left area here Also let me show something else which is quite interesting Say our goal is here

Then we get this path Now if I block this path You would assume that the set of visited cells gets larger in all directions But it doesn't This is because Due to our distance measure All those paths have exactly the same distance Until we hit this upper bound here

In which case the set of visited cells expands again Now just for fun let's do our maze again

And indeed as you see The algorithm works And shows us the shortest path From start to the goal Now let's come back to this situation Where we go from the start to the goal

And we see that the algorithm expands all the nodes Not only in the direction towards the goal But also in the opposite direction So this seems somehow strange Because by the very moment you are almost here You also look at nodes which are for example here And so it seems not possible that when you are almost at the goal here

That then another node which is expanded at the same time back here Will still have a chance to come up with a path that reaches the goal When this node is so far away In fact the direct distance from here to here Would be about two times the distance from start to goal

So how can we improve our search so that Nodes are expanded in the direction to the goal And not so much in the direction away from the goal Let's have a look Let's first have a look at the Dijkstra algorithm once more So at a certain point in time When we started at the start node

We arrived at a situation like this Where this is the set of visited nodes And all the nodes which are close to the boundary Have a similar cost And now if we ask ourselves if we should add this node next To the set of visited nodes We check for the minimum cost Where the cost in this case is the path from that node to the start

So using Dijkstra's criteria We will have a cost of this node Which we will call Chi for the moment Which is the cost from start to end And this is kind of backwards looking Because if this is the goal Then obviously the algorithm is expanding in the wrong direction

Which is due to the fact that any distance to the goal Is not part of our computation here But it makes sense to use this cost Because this is actually computed by the algorithm And it is exactly known Whereas I don't have any information Regarding how far it is from this node

To get to this goal Because I didn't see the goal yet So now let's think about a different solution Let's say we'll make a greedy solution So say I start here And my goal is to get here With nodes and edges being around here everywhere So what about the following? When looking at the direct neighbors of S

I pick the one which gets me closest to G And then starting from that node I'll check the neighbors And again I pick the one that gets me closest towards G Again I check the neighbors Pick the closest one And again pick the closest one And I reach my goal Now if you look at the boundary of my set of nodes in visited

You see that we expanded far less nodes Than we would have expanded in the case When we had used the Dijkstra algorithm So in the greedy case We use the following cost We'll just say this is H Well that's the distance to the goal But we don't know the distance to the goal So an estimate distance to the goal

And what we used here is The direct line Without knowing how the underlying graph actually looks like Now we expanded far less nodes here But on the other hand Is the result still optimal?